LIPIcs.IPEC.2016.17.pdf
- Filesize: 0.64 MB
- 12 pages
Document
Lower Bounds for Protrusion Replacement by Counting Equivalence Classes
Authors
-
Part of:
Volume:
11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Parameterized and Exact Computation (IPEC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-02-09
Cite As Get BibTex
Bart M. P. Jansen and Jules J. H. M. Wulms. Lower Bounds for Protrusion Replacement by Counting Equivalence Classes. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.IPEC.2016.17
Abstract
Garnero et al. [SIAM J. Discrete Math. 2015, 29(4):1864-1894] recently introduced a framework based on dynamic programming to make applications of the protrusion replacement technique constructive and to obtain explicit upper bounds on the involved constants. They show that for several graph problems, for every boundary size t one can find an explicit set R_t of representatives. Any subgraph H with a boundary of size t can be replaced with a representative H' in R_t such that the effect of this replacement on the optimum can be deduced from H and H' alone. Their upper bounds on the size of the graphs in R_t grow triple-exponentially with t. In this paper we complement their results by lower bounds on the sizes of representatives, in terms of the boundary size t. For example, we show that each set of planar representatives R_t for the Independent Set problem contains a graph with Omega(2^t / sqrt{4t}) vertices. This lower bound even holds for sets that only represent the planar subgraphs of bounded pathwidth. To obtain our results we provide a lower bound on the number of equivalence classes of the canonical equivalence relation for Independent Set on t-boundaried graphs. We also find an elegant characterization of the number of equivalence classes in general graphs, in terms of the number of monotone functions of a certain kind. Our results show that the number of equivalence classes is at most 2^{2^t}, improving on earlier bounds of the form (t+1)^{2^t}.
Subject Classification
Keywords
- protrusions
- boundaried graphs
- independent set
- equivalence classes
- finite integer index
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (Meta) Kernelization. In Proc. 50th FOCS, pages 629-638. IEEE Computer Society, 2009. URL: http://dx.doi.org/10.1109/FOCS.2009.46.
- Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos. (Meta) Kernelization. CoRR, 2013. URL: http://arxiv.org/abs/0904.0727.
- Hans L. Bodlaender and Babette van Antwerpen-de Fluiter. Reduction algorithms for graphs of small treewidth. Inf. Comput., 167(2):86-119, 2001. URL: http://dx.doi.org/10.1006/inco.2000.2958.
- 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.
-
Babette de Fluiter. Algorithms for Graphs of Small Treewidth. PhD thesis, Utrecht University, 1997.
- David Eppstein. Pathwidth of planarized drawing of K_3,n. TheoryCS StackExchange question, 2016. URL: http://cstheory.stackexchange.com/questions/35974/.
- Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, and Saket Saurabh. Hitting forbidden minors: Approximation and kernelization. SIAM J. Discrete Math., 30(1):383-410, 2016. URL: http://dx.doi.org/10.1137/140997889.
- Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar ℱ-deletion: Approximation, kernelization and optimal FPT algorithms. In Proc. 53rd FOCS, pages 470-479. IEEE Computer Society, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.62.
- Fedor V. Fomin and Torstein J. F. Strømme. Vertex cover structural parameterization revisited. CoRR, 2016. URL: http://arxiv.org/abs/1603.00770.
- Jakub Gajarský, Petr Hlinený, Jan Obdrzálek, Sebastian Ordyniak, Felix Reidl, Peter Rossmanith, Fernando Sanchez Villaamil, and Somnath Sikdar. Kernelization using structural parameters on sparse graph classes. In Proc. 21st ESA, pages 529-540. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40450-4_45.
- M. R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified NP-complete graph problems. Theor. Comput. Sci., 1(3):237-267, 1976. URL: http://dx.doi.org/10.1016/0304-3975(76)90059-1.
- Valentin Garnero, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos. Explicit linear kernels via dynamic programming. SIAM J. Discrete Math., 29(4):1864-1894, 2015. URL: http://dx.doi.org/10.1137/140968975.
- Bart M. P. Jansen. The Power of Data Reduction: Kernels for Fundamental Graph Problems. PhD thesis, Utrecht University, The Netherlands, 2013. URL: http://igitur-archive.library.uu.nl/dissertations/2013-0612-200803/UUindex.html.
- Bart M. P. Jansen and Jules J. H. M. Wulms. Lower bounds for protrusion replacement by counting equivalence classes. CoRR, 2016. URL: http://arxiv.org/abs/1609.09304.
- Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions. ACM Trans. Algorithms, 12(2):21, 2016. URL: http://dx.doi.org/10.1145/2797140.
- Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs on bounded treewidth are probably optimal. In Proc. 22nd SODA, pages 777-789. SIAM, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.61.