T. Ito
Parameterizing cut sets in a graph by the number of their components
Ito, T.; Kaminski, M.; Paulusma, D.; Thilikos, D. M.
Authors
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
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
An algorithmic framework for locally constrained homomorphisms
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search