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

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

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, December). Parameterizing cut sets in a graph by the number of their components. Presented at 20th International Symposium on Algorithms and Computation (ISAAC 2009), Honolulu, Hawaii, United States

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 20th International Symposium on Algorithms and Computation (ISAAC 2009)
• Start Date: Dec 16, 2009
• End Date: Dec 18, 2009
• Publication Date: Dec 1, 2009
• Deposit Date: Dec 15, 2009
• Print ISSN: 0302-9743
• 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/