Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2011-009 (March 30, 2011)

Exact Algorithms for Annotated Edge Dominating Set in Cubic Graphs
by Mingyu Xiao, Hiroshi Nagamochi

pdf File

Given a graph $G=(V,E)$ together with a nonnegative integer requirement on vertices $r:V\rightarrow Z_+$, the \emph{annotated edge dominating set} problem is to find a minimum set $M\subseteq E$ such that, each edge in $E-M$ has at least one common endpoint with an edge in $M$, and $M$ contains at least $r(v)$ edges incident on each vertex $v\in V$. The annotated edge dominating set problem is a natural extension of the classical edge dominating set problem, in which the requirement on vertices is zero. The edge dominating set problem is an important graph problem and has been extensively studied. It is well known that the problem is NP-hard, even when the graph is restricted to a planar or bipartite graph with maximum degree $3$. In this paper, we show that the annotated edge dominating set problem in graphs with maximum degree $3$ can be solved in $O^*(1.2721^n)$ time and polynomial space, where $n$ is the number of vertices in the graph. We also show that there is an $O^*(2.2306^k)$-time polynomial-space algorithm to decide whether a graph with maximum degree $3$ has an annotated edge dominating set of size $k$ or not.