Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems. (English) Zbl 1270.68112
Harland, James (ed.), CATS’03. Computing: the Australasian theory symposium. Proceedings of the symposium, Monash, Australia, February 4–7, 2003. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 78, 209-222 (2003).
Summary: The Graph \(k\)-Cut problem is that of finding a set of edges of minimum total weight, in an edge-weighted graph, such that their removal from the graph results in a graph having at least \(k\) connected components. An algorithm with a running time of \(O(n^{k^{2}})\) for this problem has been known since 1988, due to Goldschmidt and Hochbaum. We show that the problem is hard for the parameterized complexity class W[1]. We also investigate the complexity of a related problem, Cutting A Few Vertices from a Graph, that asks for the minimum cost of separating at least \(k\) vertices from an edge-weighted connected graph. We show that this problem also is hard for W[1].
For the entire collection see [Zbl 1270.68028].
For the entire collection see [Zbl 1270.68028].
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 05C40 | Connectivity |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
