Blocking dominating sets for $H$-free graphs via edge contractions

In this paper, we consider the following problem: given a connected graph $G$, can we reduce the domination number of $G$ by one by using only one edge contraction? We show that the problem is $\mathsf{NP}$-hard when restricted to $\{P_6,P_4+P_2\}$-free graphs and that it is $\mathsf{coNP}$-hard when restricted to subcubic claw-free graphs and $2P_3$-free graphs. As a consequence, we are able to establish a complexity dichotomy for the problem on $H$-free graphs when $H$ is connected.

• Publication year

  2019

• Venue

  International Symposium on Algorithms and Computation

• Publication date

  2019-06-28

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4230/LIPIcs.ISAAC.2019.21arXiv 1906.12297
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Reducing the domination number of graphs via edge contractions

  2019influential reference
• Exact algorithms for the minimum cost vertex blocker clique problem

  2019cited by this paper
• Blockers for Simple Hamiltonian Paths in Convex Geometric Graphs of Odd Order

  2018cited by this paper
• Contraction and Deletion Blockers for Perfect Graphs and $H$-free Graphs

  2017cited by this paper
• Critical Vertices and Edges in $H$-free Graphs

  2017cited by this paper
• Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions

  2017cited by this paper
• Graph Theory

  2016cited by this paper
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions

  2016cited by this paper
• Contraction Blockers for Graphs with Forbidden Induced Paths

  2015cited by this paper
• Minimum edge blocker dominating set problem

  2015cited by this paper
• Minimum vertex blocker clique problem

  2014cited by this paper
• Critical edges for the assignment problem: Complexity and exact resolution

  2013cited by this paper
• Blockers for Noncrossing Spanning Trees in Complete Geometric Graphs

  2012cited by this paper
• Minimum d-blockers and d-transversals in graphs

  2011cited by this paper
• The most vital nodes with respect to independent set and vertex cover

  2011cited by this paper
• Weighted Transversals and Blockers for Some Optimization Problems in Graphs

  2011cited by this paper
• Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

  2010cited by this paper
• Domination and Total Domination Contraction Numbers of Graphs

  2010cited by this paper
• Hard Tiling Problems with Simple Tiles

  2000cited by this paper

• The complexity of blocking (semi)total dominating sets with edge contractions

  2022cites this paper
• Reducing graph transversals via edge contractions

  2020cites this paper
• Reducing the domination number of P3+kP2-free graphs via one edge contraction

  2020influential citation
• Reducing the domination number of graphs via edge contractions

  2019cites this paper