Document Open Access Logo

Parameterized Complexity of Critical Node Cuts

Authors Danny Hermelin, Moshe Kaspi, Christian Komusiewicz, Barak Navon

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2015.343.pdf
  • Filesize: 0.5 MB
  • 12 pages

Document Identifiers

Author Details

Danny Hermelin
Moshe Kaspi
Christian Komusiewicz
Barak Navon

Cite As Get BibTex

Danny Hermelin, Moshe Kaspi, Christian Komusiewicz, and Barak Navon. Parameterized Complexity of Critical Node Cuts. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 343-354, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.IPEC.2015.343

Abstract

We consider the following graph cut problem called Critical Node Cut (CNC): Given a graph G on n vertices, and two positive integers k and x, determine whether G has a set of k vertices whose removal leaves G with at most x connected pairs of vertices. We analyze this problem in the framework of parameterized complexity. That is, we are interested in whether or not this problem is solvable in f(kappa) * n^{O(1)} time  (i.e., whether or not it is fixed-parameter tractable), for various natural parameters kappa. We consider four such parameters:
- The size k of the required cut.
- The upper bound x on the number of remaining connected pairs.
- The lower bound y on the number of connected pairs to be removed.
- The treewidth w of G.

We determine whether or not CNC is fixed-parameter tractable for each of these parameters. We determine this also for all possible aggregations of these four parameters, apart from w+k. Moreover, we also determine whether or not CNC admits a polynomial kernel for all these parameterizations. That is, whether or not there is an algorithm that reduces each instance of CNC in polynomial time to an equivalent instance of size kappa^{O(1)}, where kappa is the given parameter.

Subject Classification

Keywords
  • graph cut problem
  • NP-hard problem
  • treewidth

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Bernardetta Addis, Marco Di Summa, and Andrea Grosso. Removing critical nodes from a graph: complexity results and polynomial algorithms for the case of bounded treewidth. Optimization online (www.optimization-online.org), 2011. Google Scholar
  2. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. Journal of Algorithms, 12(2):308-340, 1991. Google Scholar
  3. Ashwin Arulselvan, Clayton W Commander, Lily Elefteriadou, and Panos M Pardalos. Detecting critical nodes in sparse graphs. Computers & Operations Research, 36(7):2193-2200, 2009. Google Scholar
  4. Hans L Bodlaender. A tourist guide through treewidth. Acta Cybernetica, 11(1-2):1, 1994. Google Scholar
  5. Hans L Bodlaender, Rodney G Downey, Michael R Fellows, and Danny Hermelin. On problems without polynomial kernels. Journal of Computer and System Sciences, 75(8):423-434, 2009. Google Scholar
  6. Vladimir Boginski and Clayton W Commander. Identifying critical nodes in protein-protein interaction networks. Clustering challenges in biological networks, pages 153-167, 2009. Google Scholar
  7. Nicolas Bousquet, Jean Daligault, and Stéphan Thomassé. Multicut is FPT. In Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC), pages 459-468. ACM, 2011. Google Scholar
  8. Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen. Parameterized complexity dichotomy for steiner multicut. In Proceedings of the 32nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), pages 157-170, 2015. Google Scholar
  9. Yixin Cao, Jianer Chen, and Jia-Hao Fan. An O(1.84^k) parameterized algorithm for the multiterminal cut problem. In Proceedings of the 19th Annual Symposium on Fundamentals of Computation Theory (FCT), pages 84-94, 2013. Google Scholar
  10. Jianer Chen, Yang Liu, and Songjian Lu. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica, 55(1):1-13, 2009. Google Scholar
  11. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. On multiway cut parameterized above lower bounds. ACM Transactions on Computation Theory, 5(1):3, 2013. Google Scholar
  12. Marco Di Summa, Andrea Grosso, and Marco Locatelli. Complexity of the critical node problem over trees. Computers & Operations Research, 38(12):1766-1774, 2011. Google Scholar
  13. Rodney G Downey and Michael R Fellows. Parameterized Complexity. Springer-Verlag, 1999. Google Scholar
  14. Pål Grønås Drange, Markus Sortland Dregi, and Pim van't Hof. On the computational complexity of vertex integrity and component order connectivity. In Proceedings of the 25th Annual International Symposium on Algorithms and Computation (ISAAC), pages 285-297, 2014. Google Scholar
  15. Andrew Drucker. New limits to classical and quantum instance compression. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2012. Google Scholar
  16. Jessica Enright and Kitty Meeks. Deleting edges to restrict the size of an epidemic. CoRR, abs/1504.05773, 2015. Google Scholar
  17. Michael R Fellows, Danny Hermelin, Frances A Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1):53-61, 2009. Google Scholar
  18. Michael R Fellows and Sam Stueckle. The immersion order, forbidden subgraphs and the complexity of network integrity. Journal of Combinatorial Mathematics and Combinatorial Computing, 6(1):23-32, 1989. Google Scholar
  19. Michael R Garey and David S Johnson. Computers and intractability; a guide to the theory of NP-completeness. San Francisco, LA: Freeman, 1979. Google Scholar
  20. Sylvain Guillemot. FPT algorithms for path-transversal and cycle-transversal problems. Discrete Optimization, 8(1):61-71, 2011. Google Scholar
  21. Karen E Joyce, Paul J Laurienti, Jonathan H Burdette, and Satoru Hayasaka. A new measure of centrality for brain networks. PLoS One, 5(8):e12200, 2010. Google Scholar
  22. Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Magnus Wahlström. Fixed-parameter tractability of multicut in directed acyclic graphs. SIAM Journal on Discrete Mathematics, 29(1):122-144, 2015. Google Scholar
  23. Vito Latora and Massimo Marchiori. How the science of complex networks can help developing strategies against terrorism. Chaos, solitons & fractals, 20(1):69-75, 2004. Google Scholar
  24. Dániel Marx. Parameterized graph separation problems. Theoretical Computer Science, 351(3):394-406, 2006. Google Scholar
  25. Dániel Marx, Barry O'Sullivan, and Igor Razgon. Finding small separators in linear time via treewidth reduction. ACM Transaction on Algorithms, 9(4):1-30, 2013. Google Scholar
  26. Dániel Marx and Igor Razgon. Fixed-parameter tractability of multicut parameterized by the size of the cutset. In Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC), pages 469-478, 2011. Google Scholar
  27. Cullen M Taniguchi, Brice Emanuelli, and C Ronald Kahn. Critical nodes in signalling pathways: insights into insulin action. Nature Reviews Molecular Cell Biology, 7(2):85-96, 2006. Google Scholar
  28. Mario Ventresca. Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem. Computers & Operations Research, 39(11):2763-2775, 2012. Google Scholar
  29. Mario Ventresca and Dionne Aleman. A derandomized approximation algorithm for the critical node detection problem. Computers & Operations Research, 43:261-270, 2014. Google Scholar
  30. Mingyu Xiao. Simple and improved parameterized algorithms for multiterminal cuts. Theory of Computing Systems, 46(4):723-736, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact