Lower bounds for protrusion replacement by counting equivalence classes

Bart M.P. Jansen (Corresponding author), Jules J.H.M. Wulms (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Garnero et al. (2015) 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 ∈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 INDEPENDENT SET or DOMINATING SET contains a graph with Ω(2 t ∕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
JournalDiscrete Applied Mathematics
DOIs
Publication statusAccepted/In press - 5 Mar 2019

Fingerprint

Equivalence classes
Equivalence class
Replacement
Counting
Lower bound
Graph in graph theory
Subgraph
Dynamic programming
Upper bound
Pathwidth
Monotone Function
Equivalence relation
Dynamic Programming
Complement

Keywords

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

Cite this

@article{8e30c51808334946b60ded11cd51e462,
title = "Lower bounds for protrusion replacement by counting equivalence classes",
abstract = "Garnero et al. (2015) 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 ′ ∈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 INDEPENDENT SET or DOMINATING SET contains a graph with Ω(2 t ∕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 .",
keywords = "Boundaried graphs, Equivalence classes, Finite integer index, Independent set, Protrusions",
author = "Jansen, {Bart M.P.} and Wulms, {Jules J.H.M.}",
year = "2019",
month = "3",
day = "5",
doi = "10.1016/j.dam.2019.02.024",
language = "English",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",

}

TY - JOUR

T1 - Lower bounds for protrusion replacement by counting equivalence classes

AU - Jansen, Bart M.P.

AU - Wulms, Jules J.H.M.

PY - 2019/3/5

Y1 - 2019/3/5

N2 - Garnero et al. (2015) 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 ′ ∈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 INDEPENDENT SET or DOMINATING SET contains a graph with Ω(2 t ∕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 .

AB - Garnero et al. (2015) 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 ′ ∈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 INDEPENDENT SET or DOMINATING SET contains a graph with Ω(2 t ∕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 .

KW - Boundaried graphs

KW - Equivalence classes

KW - Finite integer index

KW - Independent set

KW - Protrusions

UR - http://www.scopus.com/inward/record.url?scp=85062342120&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2019.02.024

DO - 10.1016/j.dam.2019.02.024

M3 - Article

AN - SCOPUS:85062342120

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -