Abstract
The notion of “important separators” and bounding the number of such separators turned out to be a very useful technique in the design of fixed-parameter tractable algorithms for multi(way) cut problems. For example, the recent breakthrough result of Chen et al.[3] on the Directed Feedback Vertex Set problem can be also explained using this notion. In my talk, I will overview combinatorial and algorithmic results that can be obtained by studying such separators.
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
Bousquet, N., Daligault, J., Thomassé, S.: Multicut is FPT. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, pp. 459–468 (2011)
Chen, J., Liu, Y., Lu, S.: An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 495–506. Springer, Heidelberg (2007)
Chen, J., Liu, Y., Lu, S., O’Sullivan, B., Razgon, I.: A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM 55(5) (2008)
Chitnis, R., Hajiaghayi, M., Marx, D.: Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. Accepted to SODA (2012)
Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.: On multiway cut parameterized above lower bounds. Accepted to IPEC (2011)
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.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)
Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)
Heggernes, P.: van ’t Hof, P., Lokshtanov, D., Paul, C.: Obtaining a bipartite graph by contracting few edges. CoRR abs/1102.5441 (2011)
Lokshtanov, D., Marx, D.: Clustering with Local Restrictions. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 785–797. Springer, Heidelberg (2011)
Marx, D.: Parameterized graph separation problems. Theoret. Comput. Sci. 351(3), 394–406 (2006)
Marx, D., Razgon, I.: Fixed-parameter tractability of multicut parameterized by the size of the cutset. In: Proceedings of the 43nd ACM Symposium on Theory of Computing, pp. 469–478 (2011)
Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford Lecture Series in Mathematics and its Applications, vol. 31. Oxford University Press, Oxford (2006)
Reed, B., Smith, K., Vetta, A.: Finding odd cycle transversals. Operations Research Letters 32(4), 299–301 (2004)
Xiao, M.: Algorithms for Multiterminal Cuts. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) CSR 2008. LNCS, vol. 5010, pp. 314–325. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Marx, D. (2011). Important Separators and Parameterized Algorithms. In: Kolman, P., Kratochvíl, J. (eds) Graph-Theoretic Concepts in Computer Science. WG 2011. Lecture Notes in Computer Science, vol 6986. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-25870-1_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-25870-1_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-25869-5
Online ISBN: 978-3-642-25870-1
eBook Packages: Computer ScienceComputer Science (R0)