[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Document Open Access Logo

Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems

Authors Lawqueen Kanesh, Jayakrishnan Madathil, Sanjukta Roy, Abhishek Sahu, Saket Saurabh

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.39.pdf
  • Filesize: 0.81 MB
  • 20 pages

Document Identifiers

Author Details

Lawqueen Kanesh
  • National University of Singapore, Singapore
Jayakrishnan Madathil
  • Chennai Mathematical Institute, India
Sanjukta Roy
  • Algorithms and Complexity Group, TU Wien, Austria
Abhishek Sahu
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Saket Saurabh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
  • University of Bergen, Norway

Funding

  • Kanesh, Lawqueen: Supported in part by NRF Fellowship for AI grant [R-252-000-B14-281] and by Defense Service Organization, Singapore.
  • Madathil, Jayakrishnan: Supported by Chennai Mathematical Institute and the Infosys Foundation.
  • Roy, Sanjukta: Supported by the WWTF research grant VRG18012.
  • Saurabh, Saket: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant no. 819416), and Swarnajayanti Fellowship grant DST/SJF/MSA-01/2017-18.

Acknowledgements

We thank two anonymous reviewers for their suggestions that helped improve the presentation of this article.

Cite As Get BibTex

Lawqueen Kanesh, Jayakrishnan Madathil, Sanjukta Roy, Abhishek Sahu, and Saket Saurabh. Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.STACS.2022.39

Abstract

For a positive integer c, a graph G is said to be c-closed if every pair of non-adjacent vertices in G have at most c-1 neighbours in common. The closure of a graph G, denoted by cl(G), is the least positive integer c for which G is c-closed. The class of c-closed graphs was introduced by Fox et al. [ICALP `18 and SICOMP `20]. Koana et al. [ESA `20] started the study of using cl(G) as an additional structural parameter to design kernels for problems that are W-hard under standard parameterizations. In particular, they studied problems such as Independent Set, Induced Matching, Irredundant Set and (Threshold) Dominating Set, and showed that each of these problems admits a polynomial kernel, either w.r.t. the parameter k+c or w.r.t. the parameter k for each fixed value of c. Here, k is the solution size and c = cl(G). The work of Koana et al. left several questions open, one of which was whether the Perfect Code problem admits a fixed-parameter tractable (FPT) algorithm and a polynomial kernel on c-closed graphs. In this paper, among other results, we answer this question in the affirmative. Inspired by the FPT algorithm for Perfect Code, we further explore two more domination problems on the graphs of bounded closure. The other problems that we study are Connected Dominating Set and Partial Dominating Set. We show that Perfect Code and Connected Dominating Set are fixed-parameter tractable w.r.t. the parameter k+cl(G), whereas Partial Dominating Set, parameterized by k is W[1]-hard even when cl(G) = 2. We also show that for each fixed c, Perfect Code admits a polynomial kernel on the class of c-closed graphs. And we observe that Connected Dominating Set has no polynomial kernel even on 2-closed graphs, unless NP ⊆ co-NP/poly.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • c-closed graphs
  • domination problems
  • perfect code
  • connected dominating set
  • fixed-parameter tractable
  • polynomial kernel

Metrics

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

References

  1. Jochen Alber, Hans L. Bodlaender, Henning Fernau, Ton Kloks, and Rolf Niedermeier. Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica, 33(4):461-493, 2002. URL: https://doi.org/10.1007/s00453-001-0116-5.
  2. Jochen Alber, Hongbing Fan, Michael R. Fellows, Henning Fernau, Rolf Niedermeier, Frances A. Rosamond, and Ulrike Stege. A refined search tree technique for dominating set on planar graphs. J. Comput. Syst. Sci., 71(4):385-405, 2005. URL: https://doi.org/10.1016/j.jcss.2004.03.007.
  3. Noga Alon and Shai Gutner. Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica, 54(4):544-556, 2009. URL: https://doi.org/10.1007/s00453-008-9204-0.
  4. Omid Amini, Fedor V. Fomin, and Saket Saurabh. Implicit branching and parameterized partial cover problems. J. Comput. Syst. Sci., 77(6):1159-1171, 2011. URL: https://doi.org/10.1016/j.jcss.2010.12.002.
  5. Nicola Apollonio and Bruno Simeone. The maximum vertex coverage problem on bipartite graphs. Discret. Appl. Math., 165:37-48, 2014. URL: https://doi.org/10.1016/j.dam.2013.05.015.
  6. Markus Bläser. Computing small partial coverings. Inf. Process. Lett., 85(6):327-331, 2003. URL: https://doi.org/10.1016/S0020-0190(02)00434-9.
  7. J. Adrian Bondy and Vasek Chvátal. A method in graph theory. Discret. Math., 15(2):111-135, 1976. URL: https://doi.org/10.1016/0012-365X(76)90078-9.
  8. J. Adrian Bondy and Uppaluri S. R. Murty. Graph Theory. Graduate Texts in Mathematics. Springer, 2008. URL: https://doi.org/10.1007/978-1-84628-970-5.
  9. Jonathan F. Buss and Judy Goldsmith. Nondeterminism within P. SIAM J. Comput., 22(3):560-572, 1993. URL: https://doi.org/10.1137/0222038.
  10. Leizhen Cai. Parameterized complexity of cardinality constrained optimization problems. Comput. J., 51(1):102-121, 2008. URL: https://doi.org/10.1093/comjnl/bxm086.
  11. Leizhen Cai, Siu Man Chan, and Siu On Chan. Random separation: A new method for solving fixed-cardinality optimization problems. In Hans L. Bodlaender and Michael A. Langston, editors, Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings, volume 4169 of Lecture Notes in Computer Science, pages 239-250. Springer, 2006. URL: https://doi.org/10.1007/11847250_22.
  12. Marco Cesati. Perfect code is W[1]-complete. Inf. Process. Lett., 81(3):163-168, 2002. URL: https://doi.org/10.1016/S0020-0190(01)00207-1.
  13. Deepayan Chakrabarti and Christos Faloutsos. Graph mining: Laws, generators, and algorithms. ACM Comput. Surv., 38(1):2, 2006. URL: https://doi.org/10.1145/1132952.1132954.
  14. Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk, and Jakub Onufry Wojtaszczyk. Kernelization hardness of connectivity problems in d-degenerate graphs. Discret. Appl. Math., 160(15):2131-2141, 2012. URL: https://doi.org/10.1016/j.dam.2012.05.016.
  15. Anuj Dawar and Stephan Kreutzer. Domination problems in nowhere-dense classes. In Ravi Kannan and K. Narayan Kumar, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, December 15-17, 2009, IIT Kanpur, India, volume 4 of LIPIcs, pages 157-168. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2009. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2315.
  16. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs. ACM Trans. Algorithms, 1(1):33-47, 2005. URL: https://doi.org/10.1145/1077464.1077468.
  17. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM, 52(6):866-893, 2005. URL: https://doi.org/10.1145/1101821.1101823.
  18. Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor. Comput. Sci., 141(1&2):109-131, 1995. URL: https://doi.org/10.1016/0304-3975(94)00097-3.
  19. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0515-9.
  20. John A. Ellis, Hongbing Fan, and Michael R. Fellows. The dominating set problem is fixed parameter tractable for graphs of bounded genus. J. Algorithms, 52(2):152-168, 2004. URL: https://doi.org/10.1016/j.jalgor.2004.02.001.
  21. Michael R. Fellows and Mark N. Hoover. Perfect domination. Australas. J Comb., 3:141-150, 1991. URL: http://ajc.maths.uq.edu.au/pdf/3/ocr-ajc-v3-p141.pdf.
  22. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 503-510. SIAM, 2010. URL: https://doi.org/10.1137/1.9781611973075.43.
  23. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Kernels for (connected) dominating set on graphs with excluded topological minors. ACM Trans. Algorithms, 14(1):6:1-6:31, 2018. URL: https://doi.org/10.1145/3155298.
  24. Fedor V. Fomin and Dimitrios M. Thilikos. Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM J. Comput., 36(2):281-309, 2006. URL: https://doi.org/10.1137/S0097539702419649.
  25. Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein. Finding cliques in social networks: A new distribution-free model. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 55:1-55:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.55.
  26. Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein. Finding cliques in social networks: A new distribution-free model. SIAM J. Comput., 49(2):448-464, 2020. URL: https://doi.org/10.1137/18M1210459.
  27. Michael R. Garey and David S. Johnson. Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, New York, 1979. Google Scholar
  28. Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs. Theor. Comput. Sci., 689:67-95, 2017. URL: https://doi.org/10.1016/j.tcs.2017.05.017.
  29. Petr A. Golovach and Yngve Villanger. Parameterized complexity for domination problems on degenerate graphs. In Hajo Broersma, Thomas Erlebach, Tom Friedetzky, and Daniël Paulusma, editors, Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30 - July 2, 2008. Revised Papers, volume 5344 of Lecture Notes in Computer Science, pages 195-205, 2008. URL: https://doi.org/10.1007/978-3-540-92248-3_18.
  30. Qianping Gu and Navid Imani. Connectivity is not a limit for kernelization: Planar connected dominating set. In Alejandro López-Ortiz, editor, LATIN 2010: Theoretical Informatics, 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010. Proceedings, volume 6034 of Lecture Notes in Computer Science, pages 26-37. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-12200-2_4.
  31. Jiong Guo and Rolf Niedermeier. Linear problem kernels for NP-hard problems on planar graphs. In Lars Arge, Christian Cachin, Tomasz Jurdzinski, and Andrzej Tarlecki, editors, Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings, volume 4596 of Lecture Notes in Computer Science, pages 375-386. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-73420-8_34.
  32. Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke. Parameterized complexity of vertex cover variants. Theory Comput. Syst., 41(3):501-520, 2007. URL: https://doi.org/10.1007/s00224-007-1309-3.
  33. Edin Husic and Tim Roughgarden. FPT algorithms for finding dense subgraphs in c-closed graphs. CoRR, abs/2007.09768, 2020. URL: http://arxiv.org/abs/2007.09768.
  34. Minghui Jiang and Yong Zhang. Perfect domination and small cycles. Discret. Math. Algorithms Appl., 9(3):1750030:1-1750030:11, 2017. URL: https://doi.org/10.1142/S1793830917500306.
  35. Iyad A. Kanj and Ljubomir Perkovic. Improved parameterized algorithms for planar dominating set. In Krzysztof Diks and Wojciech Rytter, editors, Mathematical Foundations of Computer Science 2002, 27th International Symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002, Proceedings, volume 2420 of Lecture Notes in Computer Science, pages 399-410. Springer, 2002. URL: https://doi.org/10.1007/3-540-45687-2_33.
  36. Joachim Kneis, Daniel Mölle, Stefan Richter, and Peter Rossmanith. Intuitive algorithms and t-vertex cover. In Tetsuo Asano, editor, Algorithms and Computation, 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings, volume 4288 of Lecture Notes in Computer Science, pages 598-607. Springer, 2006. URL: https://doi.org/10.1007/11940128_60.
  37. Joachim Kneis, Daniel Mölle, and Peter Rossmanith. Partial vs. complete domination: t-dominating set. In Jan van Leeuwen, Giuseppe F. Italiano, Wiebe van der Hoek, Christoph Meinel, Harald Sack, and Frantisek Plasil, editors, SOFSEM 2007: Theory and Practice of Computer Science, 33rd Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 20-26, 2007, Proceedings, volume 4362 of Lecture Notes in Computer Science, pages 367-376. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-69507-3_31.
  38. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Computing dense and sparse subgraphs of weakly closed graphs. In Yixin Cao, Siu-Wing Cheng, and Minming Li, editors, 31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 181 of LIPIcs, pages 20:1-20:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.20.
  39. Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Exploiting c-closure in kernelization algorithms for graph problems. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 65:1-65:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.65.
  40. Tomohiro Koana and André Nichterlein. Detecting and enumerating small induced subgraphs in c-closed graphs. CoRR, abs/2007.12077, 2020. URL: http://arxiv.org/abs/2007.12077.
  41. Daniel Lokshtanov, Matthias Mnich, and Saket Saurabh. Linear kernel for planar connected dominating set. In Jianer Chen and S. Barry Cooper, editors, Theory and Applications of Models of Computation, 6th Annual Conference, TAMC 2009, Changsha, China, May 18-22, 2009. Proceedings, volume 5532 of Lecture Notes in Computer Science, pages 281-290. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02017-9_31.
  42. Daniel Lokshtanov and Vaishali Surianarayanan. Dominating set in weakly closed graphs is fixed parameter tractable. In Mikolaj Bojanczyk and Chandra Chekuri, editors, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021, December 15-17, 2021, Virtual Conference, volume 213 of LIPIcs, pages 29:1-29:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2021.29.
  43. Chin Lung Lu and Chuan Yi Tang. Weighted efficient domination problem on some perfect graphs. Discret. Appl. Math., 117(1-3):163-182, 2002. URL: https://doi.org/10.1016/S0166-218X(01)00184-6.
  44. Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, and Saket Saurabh. The kernelization complexity of connected domination in graphs with (no) small cycles. Algorithmica, 68(2):504-530, 2014. URL: https://doi.org/10.1007/s00453-012-9681-z.
  45. Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. FPT algorithms for connected feedback vertex set. J. Comb. Optim., 24(2):131-146, 2012. URL: https://doi.org/10.1007/s10878-011-9394-2.
  46. Daniel Mölle, Stefan Richter, and Peter Rossmanith. Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. Theory Comput. Syst., 43(2):234-253, 2008. URL: https://doi.org/10.1007/s00224-007-9089-3.
  47. John W Moon and Leo Moser. On cliques in graphs. Israel journal of Mathematics, 3(1):23-28, 1965. Google Scholar
  48. Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Trans. Algorithms, 9(1):11:1-11:23, 2012. URL: https://doi.org/10.1145/2390176.2390187.
  49. Venkatesh Raman and Saket Saurabh. Short cycles make W -hard problems hard: FPT algorithms for W -hard problems in graphs with no short cycles. Algorithmica, 52(2):203-225, 2008. URL: https://doi.org/10.1007/s00453-007-9148-9.
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