Document Open Access Logo

A 2lk Kernel for l-Component Order Connectivity

Authors Mithilesh Kumar, Daniel Lokshtanov

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2016.20.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Mithilesh Kumar
Daniel Lokshtanov

Cite As Get BibTex

Mithilesh Kumar and Daniel Lokshtanov. A 2lk Kernel for l-Component Order Connectivity. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.IPEC.2016.20

Abstract

In the l-Component Order Connectivity problem (l in N), we are given a graph G on n vertices, m edges and a non-negative integer k and asks whether there exists a set of vertices S subseteq V(G) such that |S| <= k and the size of the largest connected component in G-S is at most l. In this paper, we give a kernel for l-Component Order Connectivity with at most 2*l*k vertices that takes n^{O(l)} time for every constant l. On the way to obtaining our kernel, we prove a generalization of the q-Expansion Lemma to weighted graphs. This generalization may be of independent interest.

Subject Classification

Keywords
  • Parameterized algorithms
  • Kernel
  • Component Order Connectivity
  • Max-min allocation
  • Weighted expansion

Metrics

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

References

  1. Ivona Bezáková and Varsha Dani. Allocating indivisible goods. SIGecom Exchanges, 5(3):11-18, 2005. Google Scholar
  2. Maw-Shang Chang, Li-Hsuan Chen, Ling-Ju Hung, Peter Rossmanith, and Ping-Chen Su. Fixed-parameter algorithms for vertex cover p3. Discrete Optimization, 19:12-22, 2016. URL: http://dx.doi.org/10.1016/j.disopt.2015.11.003.
  3. Jianer Chen, Iyad A. Kanj, and Weijia Jia. Vertex cover: Further observations and further improvements. J. Algorithms, 41(2):280-301, 2001. URL: http://dx.doi.org/10.1006/jagm.2001.1186.
  4. Jianer Chen, Iyad A. Kanj, and Ge Xia. Improved upper bounds for vertex cover. Theor. Comput. Sci., 411(40-42):3736-3756, 2010. Google Scholar
  5. 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
  6. Irit Dinur and Samuel Safra. On the hardness of approximating minimum vertex cover. Annals of mathematics, pages 439-485, 2005. Google Scholar
  7. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. Google Scholar
  8. 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 Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings, pages 285-297, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13075-0_23.
  9. Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, and Saket Saurabh. Iterative compression and exact algorithms. Theor. Comput. Sci., 411(7-9):1045-1053, 2010. Google Scholar
  10. Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch. A measure & conquer approach for the analysis of exact algorithms. J. ACM, 56(5), 2009. Google Scholar
  11. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010. Google Scholar
  12. D. Gross, M. Heinig, L. Iswara, W. Kazmierczak, K. Luttrell, J. T. Saccoman, and C. Suffel. A survey of component order connectivity models of graph theoretic networks. WSEAS Transactions on Mathematics, 12:895–910, 2013. Google Scholar
  13. Frantisek Kardos, Ján Katrenic, and Ingo Schiermeyer. On computing the minimum 3-path vertex cover and dissociation number of graphs. Theor. Comput. Sci., 412(50):7009-7017, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.09.009.
  14. Stefan Kratsch. Recent developments in kernelization: A survey. Bulletin of the EATCS, 113, 2014. Google Scholar
  15. Jan Karel Lenstra, David B. Shmoys, and Éva Tardos. Approximation algorithms for scheduling unrelated parallel machines. Math. Program., 46:259-271, 1990. Google Scholar
  16. John M. Lewis and Mihalis Yannakakis. The node-deletion problem for hereditary properties is np-complete. J. Comput. Syst. Sci., 20(2):219-230, 1980. URL: http://dx.doi.org/10.1016/0022-0000(80)90060-4.
  17. Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Kernelization-preprocessing with a guarantee. In The Multivariate Algorithmic Revolution and Beyond, pages 129-161. Springer, 2012. Google Scholar
  18. George L. Nemhauser and Leslie E. Trotter Jr. Properties of vertex packing and independence system polyhedra. Math. Program., 6(1):48-61, 1974. URL: http://dx.doi.org/10.1007/BF01580222.
  19. J. M. Robson. Algorithms for maximum independent sets. J. Algorithms, 7(3):425-440, 1986. Google Scholar
  20. Jianhua Tu. A fixed-parameter algorithm for the vertex cover p_3 problem. Inf. Process. Lett., 115(2):96-99, 2015. Google Scholar
  21. Jianhua Tu and Wenli Zhou. A factor 2 approximation algorithm for the vertex cover p3 problem. Inf. Process. Lett., 111(14):683-686, July 2011. URL: http://dx.doi.org/10.1016/j.ipl.2011.04.009.
  22. David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. Google Scholar
  23. Mingyu Xiao and Shaowei Kou. Faster computation of the maximum dissociation set and minimum 3-path vertex cover in graphs. In Frontiers in Algorithmics - 9th International Workshop, FAW 2015, Guilin, China, July 3-5, 2015, Proceedings, pages 282-293, 2015. URL: http://dx.doi.org/10.1007/978-3-319-19647-3_26.
  24. Mingyu Xiao and Hiroshi Nagamochi. Exact algorithms for maximum independent set. In Algorithms and Computation - 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings, pages 328-338, 2013. Google Scholar
  25. Mihalis Yannakakis. Node-deletion problems on bipartite graphs. SIAM J. Comput., 10(2):310-327, 1981. URL: http://dx.doi.org/10.1137/0210022.
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