Cutting up is hard to do: the parameterized complexity of k-Cut and related probelms | NOVA. The University of Newcastle's Digital Repository

Home

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/26583

Title: Cutting up is hard to do: the parameterized complexity of k-Cut and related probelms
Author/Creator: Downey, Rodney G.; Estivill-Castro, Vladimir; Fellows, Michael R.; Prieto, Elena; Rosamond, Frances A.
Description: 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(nk2) 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].
Relation: Electronic Notes in Theoretical Computer Science Vol. 78, p. 209-222
Publisher Link: http://dx.doi.org/10.1016/S1571-0661(04)81014-4
Date: 2003
Publisher: Elsevier
Keyword(s): k-Cut; edges; Goldschmidt; Hochbaum; W[1]
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/26583
Identifier: ISSN:1571-0661

12 Visitors

15 Hits

NOVA. The University of Newcastle's Digital Repository