Search

An independent dominating set of a graph G is a subset D of V such that every vertex not in D is adjacent to at least one vertex of D and no two vertices in D are adjacent. The independent dominating set (IDS) problem asks for an independent dominating set with minimum cardinality. First, we show that the independent dominating set problem and the dominating set problem on cubic bipartite graphs are both NP-complete. As an additional result, we give an alternative and more direct proof for the NP-completeness of both the independent dominating set problem and the dominating set problem on at-most-cubic grid graphs. Next, we show that there are fixed-parameter tractable algorithms for the independent dominating set problem and the dominating set problem on at-most-cubic graphs, which run in O ( 3.3028 k + n ) and O ( 4.2361 k + n ) time, respectively. Moreover, we consider the weighted independent dominating set problem on ( k , ? ) -graphs. We show that the problem on ( 2 , 1 ) -graphs is NP-complete. We also show that the problem can be solved in linear time for ( 1 , 1 ) -graphs and in polynomial time for ( 1 , ? ) -graphs for constant ?, respectively.

International audience; A dominating set in a graph is a subset of vertices such that each vertex is either in the dominating set or adjacent to some vertex in the dominating set. It is known that graphs have at most O(1.7159^n) minimal dominating sets. In this paper, we establish upper bounds on this maximum number of minimal dominating sets for split graphs, cobipartite graphs and interval graphs. For each of these graph classes, we provide an algorithm to enumerate them. For split and interval graphs, we show that the number of minimal dominating sets is at most 3^(n/3) \approx 1.4423^n, which is the best possible bound. This settles a conjecture by Couturier et al. (SOFSEM 2012). For cobipartite graphs, we lower the O(1.5875^n) upper bound from Couturier et al. to O(1.4511^n).

An edge dominating set of a graph G=(V,E) is a subset [email protected]?E of edges in the graph such that each edge in E-M is incident with at least one edge in M. In an instance of the parameterized edge dominating set problem, we are given a graph G=(V,E) and an integer k, and we are asked to decide whether G has an edge dominating set of size at most k. In this paper, we show that the parameterized edge dominating set problem can be solved in O^*(2.3147^k) time and polynomial space. We also show that this problem can be reduced to a quadratic kernel with O(k^3) edges.

In this paper, we study the Planar Connected Dominating Set problem, which, given a planar graph G=(V,E) and a non-negative integer k, asks for a subset [email protected]?V with |D|@?k such that D forms a dominating set of G and induces a connected graph. Answering an open question posed at the 2nd Workshop on Kernelization (WorKer 2010), we provide a kernelization algorithm for this problem, leading to a problem kernel with at most 130k vertices, improving the previously best upper bound on the kernel size. To this end, we incorporate a vertex coloring technique with data reduction rules and introduce a type distinction of regions into the region decomposition framework, which allows a refined analysis of the region size.

In this paper, we present an O^*(2.1479^k)-time algorithm to decide whether a graph of maximum degree 3 has an edge dominating set of size at most k or not, which is based on enumeration of vertex covers and improves all previous results on this problem. We first enumerate partial vertex covers of size at most 2k and then construct an edge dominating set based on each vertex cover to find a required edge dominating set. To effectively enumerate vertex covers, we adopt a branch-and-reduce method, and use some techniques, such as 'pseudo-cliques' and 'amortized transfer of cliques,' to analyze the running time bound.

We provide polynomial time data reduction rules for Connected Dominating Set on planar graphs and analyze these to obtain a linear kernel for the planar Connected Dominating Set problem. To obtain the desired kernel we introduce a method that we call reduce or refine. Our kernelization algorithm analyzes the input graph and either finds an appropriate reduction rule that can be applied, or zooms in on a region of the graph which is more amenable to reduction. We find this method of independent interest and believe that it will be useful for obtaining linear kernels for other problems on planar graphs.

We show that the problems steiner tree, dominating set and connected dominating set are NP-complete for chordal bipartite graphs.

We characterize the complexity of a number of basic optimization problems for unit disk graphs specified hierarchically as in [2, 17, 19, 20]. Both PSPACE-hardness results and polynomial time approximations are presented for most of the problems considered. These problems include minimum vertex coloring, maximum independent set, minimum clique cover, minimum dominating set and minimum independent dominating set. Each of our PSPACE-hardness results holds, when the hierarchical specifications are 1-level restricted and the graphs are specified hierarchically either as in [2] or as in [19]. The hardness results presented here significantly extend the hardness results in [2, 19]. The approximation algorithms presented here along with our results in [24, 25] are among the first polynomial time approximation algorithms for natural PSPACE-hard functions.

We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K"1","3, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2^O^(^k^^^2^)n^O^(^1^) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of Dominating Set is W[2]-hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general. The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of K"i","j-free graphs, which exclude, for some fixed i,j@?N, the complete bipartite graph K"i","j as a subgraph. For i,j>=2, the class of claw-free graphs and any class of K"i","j-free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable. We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any t>=4, the Dominating Set problem parameterized by the solution size is W[2]-hard in graphs that exclude the t-claw K"1","t as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are W[2]-hard in these graph classes. Finally, we show that for any t@?N, the Clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors.

In this paper, we discuss the approximability of the capacitated b-edge dominating set problem, which generalizes the edge dominating set problem by introducing capacities and demands on the edges. We present an approximation algorithm for this problem and show that it achieves a factor of 8/3 for general graphs and a factor of 2 for bipartite graphs. Moreover, we discuss the relationships of the edge dominating set problem and the vertex cover problem. The results show that improving the approximation factor beyond 8/3 using our approach of adding valid inequalities to a natural linear programming relaxation is as hard as improving the approximation factor for vertex cover beyond 2.

Four fundamental graph problems, Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut, are shown to be APX-complete even for cubic graphs. Therefore, unless P=NP, these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded by three.