Lower bounds for protrusion replacement by counting equivalence classes

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)
51 Downloads (Pure)

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}.
Original languageEnglish
Title of host publication11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
EditorsJiong Guo, Danny Hermelin
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages1-12
Number of pages12
ISBN (Electronic)9783959770231
ISBN (Print)978-3-95977-023-1
DOIs
Publication statusPublished - 31 Jan 2017
Event11th International Symposium on Parameterized and Exact Computation (IPEC 2016) - Aarhus, Denmark
Duration: 24 Aug 201626 Aug 2016
Conference number: 11
http://conferences.au.dk/algo16/ipec

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume63
ISSN (Print)1868-8969

Conference

Conference11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Abbreviated titleIPEC 2016
CountryDenmark
CityAarhus
Period24/08/1626/08/16
Internet address

Keywords

  • Boundaried graphs
  • Equivalence classes
  • Finite integer index
  • Independent set
  • Protrusions

Fingerprint Dive into the research topics of 'Lower bounds for protrusion replacement by counting equivalence classes'. Together they form a unique fingerprint.

  • Cite this

    Jansen, B. M. P., & Wulms, J. J. H. M. (2017). Lower bounds for protrusion replacement by counting equivalence classes. In J. Guo, & D. Hermelin (Eds.), 11th International Symposium on Parameterized and Exact Computation (IPEC 2016) (pp. 1-12). [17] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 63). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2016.17