Paper detail

The complexity of the bondage problem in planar graphs

A set $S\subseteq V(G)$ of a graph $G$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$. Let $γ(G)$ be the cardinality of a minimum dominating set in $G$. The bondage number $b(G)$ of a graph $G$ is the smallest cardinality of a set of edges $A\subseteq E(G)$, such that $γ(G-A)=γ(G)+1$. The $d$-Bondage is the problem of deciding, given a graph $G$ and an integer $d\geq 1$, if $b(G)\leq d$. This problem is known to be $\mathsf{NP}$-hard even for bipartite graphs and $d=1$. In this paper, we show that $1$-Bondage is $\mathsf{NP}$-hard, even for the class of $3$-regular planar graphs, the class of subcubic claw-free graphs, and the class of bipartite planar graphs of maximum degree $3$, with girth $k$, for any fixed $k\geq 3$. On the positive side, for any planar graph $G$ of girth at least $8$, we show that we can find, in polynomial time, a set of three edges $A$ such that $γ(G-A)>γ(G)$. Last, we exposed some classes of graphs for which Dominating Set can be solved in polynomial time, and where $d$-Bondage can also be solved in polynomial time, for any fixed $d\geq 1$.