Parameterized graph separation problems |
| |
Authors: | Dá niel Marx |
| |
Affiliation: | Department of Computer Science and Information Theory, Budapest University of Technology and Economics, H-1521 Budapest, Hungary |
| |
Abstract: | We consider parameterized problems where some separation property has to be achieved by deleting as few vertices as possible. The following five problems are studied: delete k vertices such that (a) each of the given ? terminals is separated from the others, (b) each of the given ? pairs of terminals is separated, (c) exactly ? vertices are cut away from the graph, (d) exactly ? connected vertices are cut away from the graph, (e) the graph is separated into at least ? components. We show that if both k and ? are parameters, then (a), (b) and (d) are fixed-parameter tractable, while (c) and (e) are W[1]-hard. |
| |
Keywords: | Parameterized complexity Separator Multicut Multiway cut |
本文献已被 ScienceDirect 等数据库收录! |
|