Document Open Access Logo

On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem

Authors Robert Ganian, Fabian Klute, Sebastian Ordyniak

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.33.pdf
  • Filesize: 0.67 MB
  • 14 pages

Document Identifiers

Author Details

Robert Ganian
Fabian Klute
Sebastian Ordyniak

Cite As Get BibTex

Robert Ganian, Fabian Klute, and Sebastian Ordyniak. On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.33

Abstract

We study the parameterized complexity of the Bounded-Degree Vertex Deletion problem (BDD), where the aim is to find a maximum induced subgraph whose maximum degree is below a given degree bound. Our focus lies on parameters that measure the structural properties of the input instance. We first show that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, treedepth, and even the size of a minimum vertex deletion set into graphs of pathwidth and treedepth at most three. We thereby resolve the main open question stated in Betzler, Bredereck, Niedermeier and Uhlmann (2012) concerning the complexity of BDD parameterized by the feedback vertex set number. On the positive side, we obtain fixed-parameter algorithms for the problem with respect to the decompositional parameter treecut width and a novel problem-specific parameter called the core fracture number.

Subject Classification

Keywords
  • bounded-degree vertex deletion
  • feedback vertex set
  • parameterized algorithms
  • treecut width

Metrics

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

References

  1. Martin Aigner and Günter M. Ziegler. Proofs from the Book (3. ed.). Springer, 2004. Google Scholar
  2. Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, and Stefan Szeider. A complete parameterized complexity analysis of bounded planning. JCSS, 81(7):1311-1332, 2015. Google Scholar
  3. Balabhaskar Balasundaram, Sergiy Butenko, and Illya V. Hicks. Clique relaxations in social network analysis: The maximum k-plex problem. Operations Research, 59(1):133-142, 2011. Google Scholar
  4. Balabhaskar Balasundaram, Shyam Sundar Chandramouli, and Svyatoslav Trukhanov. Approximation algorithms for finding and partitioning unit-disk graphs into co-k-plexes. Optimization Letters, 4(3):311-320, 2010. Google Scholar
  5. Nadja Betzler, Robert Bredereck, Rolf Niedermeier, and Johannes Uhlmann. On bounded-degree vertex deletion parameterized by treewidth. Discrete Applied Mathematics, 160(1-2):53-60, 2012. Google Scholar
  6. Hans L. Bodlaender and Babette van Antwerpen-de Fluiter. Reduction algorithms for graphs of small treewidth. Inf. Comput., 167(2):86-119, 2001. Google Scholar
  7. Zhi-Zhong Chen, Michael R. Fellows, Bin Fu, Haitao Jiang, Yang Liu, Lusheng Wang, and Binhai Zhu. A linear kernel for co-path/cycle packing. In Proc. AAIM 2010, volume 6124 of LNCS, pages 90-102. Springer, 2010. Google Scholar
  8. Bruno Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. Google Scholar
  9. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  10. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  11. Anders Dessmark, Klaus Jansen, and Andrzej Lingas. The maximum k-dependent and f-dependent set problem. In Proc. ISAAC 1993, volume 762 of LNCS, pages 88-98. Springer, 1993. Google Scholar
  12. Reinhard Diestel. Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer Verlag, New York, 2nd edition, 2000. Google Scholar
  13. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  14. Eduard Eiben, Robert Ganian, and Stefan Szeider. Meta-kernelization using well-structured modulators. In Thore Husfeldt and Iyad A. Kanj, editors, Proc. IPEC 2015, volume 43 of LIPIcs, pages 114-126. Leibniz-Zentrum für Informatik, 2015. Google Scholar
  15. Eduard Eiben, Robert Ganian, and Stefan Szeider. Solving problems on graphs of high rank-width. In Proc. WADS 2015, volume 9214 of LNCS, pages 314-326. Springer, 2015. Google Scholar
  16. Paul Erdős and Paul Turán. On a problem of Sidon in additive number theory, and on some related problems. Journal of the London Mathematical Society, 1(4):212-215, 1941. Google Scholar
  17. Michael R. Fellows, Jiong Guo, Hannes Moser, and Rolf Niedermeier. A generalization of Nemhauser and Trotter’s local optimization theorem. J. Comput. Syst. Sci., 77(6):1141-1158, 2011. Google Scholar
  18. Arnaud Fréville. The multidimensional 0-1 knapsack problem: An overview. European Journal of Operational Research, 155(1):1-21, 2004. Google Scholar
  19. Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. Kernelization using structural parameters on sparse graph classes. J. Comput. Syst. Sci., 84:219-242, 2017. Google Scholar
  20. Robert Ganian, Eun Jung Kim, and Stefan Szeider. Algorithmic applications of tree-cut width. In Giuseppe F. Italiano, Giovanni Pighizzini, and Donald Sannella, editors, Proc. MFCS 2015, volume 9235 of LNCS, pages 348-360. Springer, 2015. Google Scholar
  21. Robert Ganian, Friedrich Slivovsky, and Stefan Szeider. Meta-kernelization with structural parameters. J. Comput. Syst. Sci., 82(2):333-346, 2016. Google Scholar
  22. Serge Gaspers, Neeldhara Misra, Sebastian Ordyniak, Stefan Szeider, and Stanislav Zivny. Backdoors into heterogeneous classes of SAT and CSP. J. Comput. Syst. Sci., 85:38-56, 2017. Google Scholar
  23. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  24. Eunjung Kim, Sang-il Oum, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos. An FPT 2-approximation for tree-cut decomposition. In Laura Sanità and Martin Skutella, editors, Proc. WAOA 2015, volume 9499 of LNCS, pages 35-46. Springer, 2015. Google Scholar
  25. Ton Kloks. Treewidth: Computations and Approximations, volume 842 of LNCS. Springer Verlag, Berlin, 1994. Google Scholar
  26. Christian Komusiewicz, Falk Hüffner, Hannes Moser, and Rolf Niedermeier. Isolation concepts for efficiently enumerating dense subgraphs. Theor. Comput. Sci., 410(38-40):3640-3654, 2009. Google Scholar
  27. Martin Kronegger, Sebastian Ordyniak, and Andreas Pfandler. Variable-deletion backdoors to planning. In Proc. AAAI 2015, pages 2300-2307. AAAI Press, 2014. Google Scholar
  28. H. W. Lenstra. Integer programming with a fixed number of variables. MATH. OPER. RES, 8(4):538-548, 1983. Google Scholar
  29. Dániel Marx and Paul Wollan. Immersions in highly edge connected graphs. SIAM J. Discrete Math., 28(1):503-520, 2014. Google Scholar
  30. Benjamin McClosky and Illya V. Hicks. Combinatorial algorithms for the maximum k-plex problem. J. Comb. Optim., 23(1):29-49, 2012. Google Scholar
  31. Hannes Moser, Rolf Niedermeier, and Manuel Sorge. Exact combinatorial algorithms and experiments for finding maximum k-plexes. J. Comb. Optim., 24(3):347-373, 2012. Google Scholar
  32. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. Google Scholar
  33. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms, volume 31 of Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford, 2006. Google Scholar
  34. Naomi Nishimura, Prabhakar Ragde, and Dimitrios M. Thilikos. Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover. Discrete Applied Mathematics, 152(1-3):229-245, 2005. Google Scholar
  35. Stephen B Seidman and Brian L Foster. A graph-theoretic generalization of the clique concept. Journal of Mathematical sociology, 6(1):139-154, 1978. Google Scholar
  36. Paul Wollan. The structure of graphs not admitting a fixed immersion. J. Comb. Theory, Ser. B, 110:47-66, 2015. 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