Document Open Access Logo

Structural Parameterizations with Modulator Oblivion

Authors Ashwin Jacob, Fahad Panolan, Venkatesh Raman, Vibha Sahlot

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2020.19.pdf
  • Filesize: 0.61 MB
  • 18 pages

Document Identifiers

Author Details

Ashwin Jacob
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Fahad Panolan
  • Department of Computer Science and Engineering, IIT Hyderabad, India
Venkatesh Raman
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Vibha Sahlot
  • The Institute of Mathematical Sciences, HBNI, Chennai, India

Cite As Get BibTex

Ashwin Jacob, Fahad Panolan, Venkatesh Raman, and Vibha Sahlot. Structural Parameterizations with Modulator Oblivion. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.IPEC.2020.19

Abstract

It is known that problems like Vertex Cover, Feedback Vertex Set and Odd Cycle Transversal are polynomial time solvable in the class of chordal graphs. We consider these problems in a graph that has at most k vertices whose deletion results in a chordal graph, when parameterized by k. While this investigation fits naturally into the recent trend of what are called "structural parameterizations", here we assume that the deletion set is not given.
One method to solve them is to compute a k-sized or an approximate (f(k) sized, for a function f) chordal vertex deletion set and then use the structural properties of the graph to design an algorithm. This method leads to at least k^O(k)n^O(1) running time when we use the known parameterized or approximation algorithms for finding a k-sized chordal deletion set on an n vertex graph.
In this work, we design 2^O(k)n^O(1) time algorithms for these problems. Our algorithms do not compute a chordal vertex deletion set (or even an approximate solution). Instead, we construct a tree decomposition of the given graph in time 2^O(k)n^O(1) where each bag is a union of four cliques and O(k) vertices. We then apply standard dynamic programming algorithms over this special tree decomposition. This special tree decomposition can be of independent interest. 
Our algorithms are, what are sometimes called permissive in the sense that given an integer k, they detect whether the graph has no chordal vertex deletion set of size at most k or output the special tree decomposition and solve the problem. 
We also show lower bounds for the problems we deal with under the Strong Exponential Time Hypothesis (SETH).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Parameterized Complexity
  • Chordal Graph
  • Tree Decomposition
  • Strong Exponential Time Hypothesis

Metrics

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

Related Versions

References

  1. Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Polylogarithmic approximation algorithms for Weighted-F-Deletion Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA, pages 1:1-1:15, 2018. Google Scholar
  2. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on computing, 25(6):1305-1317, 1996. Google Scholar
  3. Hans L. Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Information and Computation, 243:86-111, 2015. Google Scholar
  4. Hans L. Bodlaender, Pål Gronås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk. A c^kn 5-approximation algorithm for treewidth. SIAM Journal on Computing, 45(2):317-378, 2016. Google Scholar
  5. Kellogg S. Booth and J. Howard Johnson. Dominating sets in chordal graphs. SIAM J. Comput., 11:191-199, 1982. Google Scholar
  6. Andreas Brandstädt. On robust algorithms for the maximum weight stable set problem. In International Symposium on Fundamentals of Computation Theory, pages 445-458. Springer, 2001. Google Scholar
  7. Heinz Breu and David G. Kirkpatrick. Unit disk graph recognition is NP-hard. Comput. Geom., 9(1-2):3-24, 1998. URL: https://doi.org/10.1016/S0925-7721(97)00014-X.
  8. Yixin Cao and Dániel Marx. Chordal editing is fixed-parameter tractable. Algorithmica, 75(1):118-137, 2016. Google Scholar
  9. Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs. Discrete Mathematics, 86(1-3):165-177, 1990. URL: https://doi.org/10.1016/0012-365X(90)90358-O.
  10. Derek G. Corneil and Jean Fonlupt. The complexity of generalized clique covering. Discrete Applied Mathematics, 22(2):109-118, 1988. Google Scholar
  11. Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On problems as hard as CNF-SAT. ACM Trans. Algorithms, 12(3):41:1-41:24, 2016. URL: https://doi.org/10.1145/2925416.
  12. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms, volume 3. Springer, 2015. Google Scholar
  13. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. On multiway cut parameterized above lower bounds. TOCT, 5(1):3:1-3:11, 2013. URL: https://doi.org/10.1145/2462896.2462899.
  14. R. Diestel. Graph Theory. Springer, 2006. Google Scholar
  15. Rodney G Downey and Michael R Fellows. Fundamentals of parameterized complexity, volume 4. Springer, 2013. Google Scholar
  16. Michael Fellows and Frances Rosamond. The complexity ecology of parameters: an illustration using bounded max leaf number. In Conference on Computability in Europe, pages 268-277. Springer, 2007. Google Scholar
  17. Michael R. Fellows, Bart M.P. Jansen, and Frances Rosamond. Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of computational complexity. European Journal of Combinatorics, 34(3):541-566, 2013. Google Scholar
  18. Fedor V. Fomin and Petr A. Golovach. Subexponential parameterized algorithms and kernelization on almost chordal graphs. arXiv preprint, 2020. URL: http://arxiv.org/abs/2002.08226.
  19. Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Parameterized single-exponential time polynomial space algorithm for steiner tree. In International Colloquium on Automata, Languages, and Programming, pages 494-505. Springer, 2015. Google Scholar
  20. Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM J. Comput., 44(1):54-87, 2015. URL: https://doi.org/10.1137/140964801.
  21. Serge Gaspers and Stefan Szeider. Backdoors to satisfaction. In Hans L. Bodlaender, Rod Downey, Fedor V. Fomin, and Dániel Marx, editors, The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, volume 7370 of Lecture Notes in Computer Science, pages 287-317. Springer, 2012. URL: https://doi.org/10.1007/978-3-642-30891-8_15.
  22. Martin Charles Golumbic. Algorithmic graph theory and perfect graphs, volume 57. Elsevier, 2004. Google Scholar
  23. Michel Habib and Christophe Paul. A simple linear time algorithm for cograph recognition. Discrete Applied Mathematics, 145(2):183-197, 2005. Google Scholar
  24. Pinar Heggernes, Pim van 't Hof, Bart M. P. Jansen, Stefan Kratsch, and Yngve Villanger. Parameterized complexity of vertex deletion into perfect graph classes. Theor. Comput. Sci., 511:172-180, 2013. URL: https://doi.org/10.1016/j.tcs.2012.03.013.
  25. Yoichi Iwata, Yutaro Yamaguchi, and Yuichi Yoshida. 0/1/all csps, half-integral a-path packing, and linear-time FPT algorithms. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 462-473. IEEE, 2018. Google Scholar
  26. Bart M.P. Jansen. The power of data reduction: Kernels for fundamental graph problems. PhD thesis, Utrecht University, 2013. Google Scholar
  27. Bart M.P. Jansen and Hans L. Bodlaender. Vertex cover kernelization revisited. Theory of Computing Systems, 53(2):263-299, 2013. Google Scholar
  28. Bart M.P. Jansen and Marcin Pilipczuk. Approximation and kernelization for chordal vertex deletion. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1399-1418. Society for Industrial and Applied Mathematics, 2017. Google Scholar
  29. Bart M.P. Jansen, Venkatesh Raman, and Martin Vatshelle. Parameter ecology for feedback vertex set. Tsinghua Science and Technology, 19(4):387-409, 2014. Google Scholar
  30. Eun Jung Kim and O-joung Kwon. Erdős-pósa property of chordless cycles and its applications. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1665-1684. SIAM, 2018. Google Scholar
  31. Mathieu Liedloff, Pedro Montealegre, and Ioan Todinca. Beyond classes of graphs with "few" minimal separators: FPT results through potential maximal cliques. Algorithmica, 81(3):986-1005, 2019. URL: https://doi.org/10.1007/s00453-018-0453-2.
  32. Daniel Lokshtanov, NS Narayanaswamy, Venkatesh Raman, M.S. Ramanujan, and Saket Saurabh. Faster parameterized algorithms using linear programming. ACM Transactions on Algorithms (TALG), 11(2):15, 2014. Google Scholar
  33. Diptapriyo Majumdar and Venkatesh Raman. Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization. Algorithmica, 80(9):2683-2724, 2018. Google Scholar
  34. Diptapriyo Majumdar, Venkatesh Raman, and Saket Saurabh. Polynomial kernels for vertex cover parameterized by small degree modulators. Theory Comput. Syst., 62(8):1910-1951, 2018. URL: https://doi.org/10.1007/s00224-018-9858-1.
  35. Kazuhisa Makino and Takeaki Uno. New algorithms for enumerating all maximal cliques. In Scandinavian Workshop on Algorithm Theory, pages 260-272. Springer, 2004. Google Scholar
  36. Vijay Raghavan and Jeremy P. Spinrad. Robust algorithms for restricted domains. J. Algorithms, 48(1):160-172, 2003. URL: https://doi.org/10.1016/S0196-6774(03)00048-8.
  37. Neil Robertson and Paul D. Seymour. Graph minors. xiii. the disjoint paths problem. Journal of combinatorial theory, Series B, 63(1):65-110, 1995. Google Scholar
  38. Jeremy P. Spinrad. Efficient graph representations. American Mathematical Society, 2003. 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