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 are 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 ℓ 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.
Research is supported in part by grants OTKA 44733, 42559 and 42706 of the Hungarian National Science Fund.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209–223 (1997)
Bui, T.N., Jones, C.: Finding good approximate vertex and edge partitions is NP-hard. Inform. Process. Lett. 42(3), 153–159 (1992)
Cunningham, W.H.: The optimal multiterminal cut problem. In: Reliability of computer and communication networks (New Brunswick, NJ, 1989). DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 5, pp. 105–120. Amer. Math. Soc., Providence (1991)
Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864–894 (1994)
Downey, R., Estivill-Castro, V., Fellows, M., Prieto, E., Rosamund, F.: Cutting up is hard to do. In: Harland, J. (ed.) Electronic Notes in Theoretical Computer Science, vol. 78, Elsevier, Amsterdam (2003)
Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999)
Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3–20 (1997)
Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in node weighted graphs. J. Algorithms 50(1), 49–61 (2004)
Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177–189 (1979)
Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615–627 (1980)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Marx, D. (2004). Parameterized Graph Separation Problems. In: Downey, R., Fellows, M., Dehne, F. (eds) Parameterized and Exact Computation. IWPEC 2004. Lecture Notes in Computer Science, vol 3162. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28639-4_7
Download citation
DOI: https://doi.org/10.1007/978-3-540-28639-4_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23071-7
Online ISBN: 978-3-540-28639-4
eBook Packages: Springer Book Archive