Document Open Access Logo

On Kernelization for Edge Dominating Set under Structural Parameters

Authors Eva-Maria C. Hols , Stefan Kratsch

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.36.pdf
  • Filesize: 0.55 MB
  • 18 pages

Document Identifiers

Author Details

Eva-Maria C. Hols
  • Department of Computer Science, Humboldt-Universität zu Berlin, Germany
Stefan Kratsch
  • Department of Computer Science, Humboldt-Universität zu Berlin, Germany

Funding

  • Hols, Eva-Maria C.: Supported by DFG Emmy Noether-grant (KR 4286/1).

Cite As Get BibTex

Eva-Maria C. Hols and Stefan Kratsch. On Kernelization for Edge Dominating Set under Structural Parameters. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.STACS.2019.36

Abstract

In the NP-hard Edge Dominating Set problem (EDS) we are given a graph G=(V,E) and an integer k, and need to determine whether there is a set F subseteq E of at most k edges that are incident with all (other) edges of G. It is known that this problem is fixed-parameter tractable and admits a polynomial kernelization when parameterized by k. A caveat for this parameter is that it needs to be large, i.e., at least equal to half the size of a maximum matching of G, for instances not to be trivially negative. Motivated by this, we study the existence of polynomial kernelizations for EDS when parameterized by structural parameters that may be much smaller than k.
Unfortunately, at first glance this looks rather hopeless: Even when parameterized by the deletion distance to a disjoint union of paths P_3 of length two there is no polynomial kernelization (under standard assumptions), ruling out polynomial kernelizations for many smaller parameters like the feedback vertex set size. In contrast, somewhat surprisingly, there is a polynomial kernelization for deletion distance to a disjoint union of paths P_5 of length four. As our main result, we fully classify for all finite sets H of graphs, whether a kernel size polynomial in |X| is possible when given X such that each connected component of G-X is isomorphic to a graph in H.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Edge dominating set
  • kernelization
  • structural parameters

Metrics

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

Related Versions

References

  1. Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci., 75(8):423-434, 2009. URL: http://dx.doi.org/10.1016/j.jcss.2009.04.001.
  2. Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization Lower Bounds by Cross-Composition. SIAM J. Discrete Math., 28(1):277-305, 2014. URL: http://dx.doi.org/10.1137/120880240.
  3. Jean Cardinal, Stefan Langerman, and Eythan Levy. Improved approximation bounds for edge dominating set in dense graphs. Theor. Comput. Sci., 410(8-10):949-957, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2008.12.036.
  4. Miroslav Chlebík and Janka Chlebíková. Approximation hardness of edge dominating set problems. J. Comb. Optim., 11(3):279-290, 2006. URL: http://dx.doi.org/10.1007/s10878-006-7908-0.
  5. 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: http://dx.doi.org/10.1145/2462896.2462899.
  6. Holger Dell and Dieter van Melkebeek. Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses. J. ACM, 61(4):23:1-23:27, 2014. URL: http://dx.doi.org/10.1145/2629620.
  7. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  8. Bruno Escoffier, Jérôme Monnot, Vangelis Th. Paschos, and Mingyu Xiao. New Results on Polynomial Inapproximabilityand Fixed Parameter Approximability of Edge Dominating Set. Theory Comput. Syst., 56(2):330-346, 2015. URL: http://dx.doi.org/10.1007/s00224-014-9549-5.
  9. Henning Fernau. Edge dominating set: Efficient Enumeration-Based Exact Algorithms. 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 142-153. Springer, 2006. URL: http://dx.doi.org/10.1007/11847250_13.
  10. Fedor V. Fomin, Serge Gaspers, Saket Saurabh, and Alexey A. Stepanov. On Two Techniques of Combining Branching and Treewidth. Algorithmica, 54(2):181-207, 2009. URL: http://dx.doi.org/10.1007/s00453-007-9133-3.
  11. Lance Fortnow and Rahul Santhanam. Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci., 77(1):91-106, 2011. URL: http://dx.doi.org/10.1016/j.jcss.2010.06.007.
  12. Toshihiro Fujito and Hiroshi Nagamochi. A 2-approximation algorithm for the minimum weight edge dominating set problem. Discrete Applied Mathematics, 118(3):199-207, 2002. URL: http://dx.doi.org/10.1016/S0166-218X(00)00383-8.
  13. Shivam Garg and Geevarghese Philip. Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above a Higher Guarantee. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1152-1166. SIAM, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch80.
  14. Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, and Yngve Villanger. An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets. Algorithmica, 72(3):836-859, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9875-7.
  15. Torben Hagerup. Kernels for Edge Dominating Set: Simpler or Smaller. In Branislav Rovan, Vladimiro Sassone, and Peter Widmayer, editors, Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings, volume 7464 of Lecture Notes in Computer Science, pages 491-502. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32589-2_44.
  16. Eva-Maria C. Hols and Stefan Kratsch. On Kernelization for Edge Dominating Set under Structural Parameters. CoRR, abs/1901.03582, 2019. URL: http://arxiv.org/abs/1901.03582.
  17. John E. Hopcroft and Richard M. Karp. An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput., 2(4):225-231, 1973. URL: http://dx.doi.org/10.1137/0202019.
  18. Ken Iwaide and Hiroshi Nagamochi. An Improved Algorithm for Parameterized Edge Dominating Set Problem. J. Graph Algorithms Appl., 20(1):23-58, 2016. URL: http://dx.doi.org/10.7155/jgaa.00383.
  19. Bart M. P. Jansen and Hans L. Bodlaender. Vertex Cover Kernelization Revisited - Upper and Lower Bounds for a Refined Parameter. Theory Comput. Syst., 53(2):263-299, 2013. URL: http://dx.doi.org/10.1007/s00224-012-9393-4.
  20. Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, and Lhouari Nourine. On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets. In Kun-Mao Chao, Tsan-sheng Hsu, and Der-Tsai Lee, editors, Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings, volume 7676 of Lecture Notes in Computer Science, pages 289-298. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-35261-4_32.
  21. Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, Lhouari Nourine, and Takeaki Uno. Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs. In Frank Dehne, Jörg-Rüdiger Sack, and Ulrike Stege, editors, Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, volume 9214 of Lecture Notes in Computer Science, pages 446-457. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21840-3_37.
  22. Daniel Kobler and Udi Rotics. Edge dominating set and colorings on graphs with fixed clique-width. Discrete Applied Mathematics, 126(2-3):197-221, 2003. URL: http://dx.doi.org/10.1016/S0166-218X(02)00198-1.
  23. Stefan Kratsch. A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 59:1-59:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.59.
  24. Stefan Kratsch and Magnus Wahlström. Representative Sets and Irrelevant Vertices: New Tools for Kernelization. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 450-459. IEEE Computer Society, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.46.
  25. Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Faster Parameterized Algorithms Using Linear Programming. ACM Trans. Algorithms, 11(2):15:1-15:31, 2014. URL: http://dx.doi.org/10.1145/2566616.
  26. Elena Prieto. Systematic kernelization in FPT algorithm design. PhD thesis, The University of Newcastle, Australia, 2005. Google Scholar
  27. Venkatesh Raman, M. S. Ramanujan, and Saket Saurabh. Paths, Flowers and Vertex Cover. In Camil Demetrescu and Magnús M. Halldórsson, editors, Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings, volume 6942 of Lecture Notes in Computer Science, pages 382-393. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-23719-5_33.
  28. Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques. Theory Comput. Syst., 41(3):563-587, 2007. URL: http://dx.doi.org/10.1007/s00224-007-1334-2.
  29. Richard Schmied and Claus Viehmann. Approximating edge dominating set in dense graphs. Theor. Comput. Sci., 414(1):92-99, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2011.10.001.
  30. Johan M. M. van Rooij and Hans L. Bodlaender. Exact Algorithms for Edge Domination. Algorithmica, 64(4):535-563, 2012. URL: http://dx.doi.org/10.1007/s00453-011-9546-x.
  31. Jianxin Wang, Beiwei Chen, Qilong Feng, and Jianer Chen. An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set. In Xiaotie Deng, John E. Hopcroft, and Jinyun Xue, editors, Frontiers in Algorithmics, Third International Workshop, FAW 2009, Hefei, China, June 20-23, 2009. Proceedings, volume 5598 of Lecture Notes in Computer Science, pages 237-250. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-02270-8_25.
  32. Mingyu Xiao. Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs. In Weili Wu and Ovidiu Daescu, editors, Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Proceedings, Part II, volume 6509 of Lecture Notes in Computer Science, pages 387-400. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-17461-2_31.
  33. Mingyu Xiao, Ton Kloks, and Sheung-Hung Poon. New parameterized algorithms for the edge dominating set problem. Theor. Comput. Sci., 511:147-158, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2012.06.022.
  34. Mingyu Xiao and Hiroshi Nagamochi. Parameterized edge dominating set in graphs with degree bounded by 3. Theor. Comput. Sci., 508:2-15, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2012.08.015.
  35. Mingyu Xiao and Hiroshi Nagamochi. A refined exact algorithm for Edge Dominating Set. Theor. Comput. Sci., 560:207-216, 2014. URL: http://dx.doi.org/10.1016/j.tcs.2014.07.019.
  36. Mihalis Yannakakis and Fanica Gavril. Edge dominating sets in graphs. SIAM Journal on Applied Mathematics, 38(3):364-372, 1980. 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