Skip to main content

Research Repository

Advanced Search

Parameterizing cut sets in a graph by the number of their components

Ito, T.; Kaminski, M.; Paulusma, D.; Thilikos, D. M.

Authors

T. Ito

M. Kaminski

D. M. Thilikos



Contributors

Y. Dong
Editor

D.-Z. Du
Editor

I. Ibarra
Editor

Abstract

For a connected graph G = (V,E), a subset U ⊆ V is called a k-cut if U disconnects G, and the subgraph induced by U contains exactly k ( ≥ 1) components. More specifically, a k-cut U is called a (k,ℓ)-cut if V \U induces a subgraph with exactly ℓ ( ≥ 2) components. We study two decision problems, called k-Cut and (k,ℓ)-Cut, which determine whether a graph G has a k-cut or (k,ℓ)-cut, respectively. By pinpointing a close relationship to graph contractibility problems we first show that (k,ℓ)-Cut is in P for k = 1 and any fixed constant ℓ ≥ 2, while the problem is NP-complete for any fixed pair k,ℓ ≥ 2. We then prove that k-Cut is in P for k = 1, and is NP-complete for any fixed k ≥ 2. On the other hand, we present an FPT algorithm that solves (k,ℓ)-Cut on apex-minor-free graphs when parameterized by k + ℓ. By modifying this algorithm we can also show that k-Cut is in FPT (with parameter k) and Disconnected Cut is solvable in polynomial time for apex-minor-free graphs. The latter problem asks if a graph has a k-cut for some k ≥ 2.

Citation

Ito, T., Kaminski, M., Paulusma, D., & Thilikos, D. M. (2009). Parameterizing cut sets in a graph by the number of their components. In Y. Dong, D. Du, & I. Ibarra (Eds.), Algorithms and computation : 20th International Symposium, ISAAC 2009, 16-18 December 2009, Honolulu, Hawaii, USA ; proceedings (605-615). https://doi.org/10.1007/978-3-642-10631-6_62

Conference Name 20th International Symposium on Algorithms and Computation (ISAAC 2009)
Conference Location Honolulu, Hawaii, United States
Start Date Dec 16, 2009
End Date Dec 18, 2009
Publication Date Dec 1, 2009
Deposit Date Dec 15, 2009
Publisher Springer Verlag
Pages 605-615
Series Title Lecture notes in computer science
Series Number 5878
Book Title Algorithms and computation : 20th International Symposium, ISAAC 2009, 16-18 December 2009, Honolulu, Hawaii, USA ; proceedings.
DOI https://doi.org/10.1007/978-3-642-10631-6_62
Public URL https://durham-repository.worktribe.com/output/1160780
Publisher URL http://www.springerlink.com/content/c648823163j3h834/


You might also like



Downloadable Citations