Theoretical Computer Science 562 (2015) 1–22

Contents lists available at ScienceDirect

In

C a D b D a

Ar

Re

Re

Ac

Av

Co

Ke

NP

FP

In

Do

W

Cu

At (k 1. ve in de ca it nu le m gr ca if ✩ * ht 03Theoretical Computer Science www.elsevier.com/locate/tcs dependent dominating set problem revisited✩ hing-Hao Liu a, Sheung-Hung Poon b,∗, Jin-Yong Lin a epartment of Computer Science, National Tsing Hua University, Hsinchu 30013, Taiwan epartment of Computer Science & Institute of Information Systems and Applications, National Tsing Hua University, Hsinchu 30013, Taiwan r t i c l e i n f o a b s t r a c t ticle history: ceived 7 April 2014 ceived in revised form 26 August 2014 cepted 1 September 2014 ailable online 8 September 2014 mmunicated by G. Ausiello ywords: -complete

T-algorithm dependent dominating set minating set eighted independent dominating set bic bipartite graph -most-cubic grid graph , )-graph

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.3028k + n) and O (4.2361k + 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. © 2014 Published by Elsevier B.V.

Introduction

A dominating set of a graph G = (V , E) is a subset D of V such that every vertex not in D is adjacent to at least one rtex of D . An independent set of a graph G = (V , E) is a subset I of V such that no two vertices in I are adjacent. An dependent dominating set of G is a subset of V which is both dominating and independent in G . Equivalently, an indepennt dominating set is a maximal independent set. The dominating set (DS) problem asks for a dominating set with minimum rdinality and the independent dominating set (IDS) problem asks for an independent dominating set with minimum cardinaly. The cardinalities of a minimum dominating set and a minimum independent dominating set are called the domination mber and the independent domination number, respectively. Moreover, the weighted independent dominating set (WIDS) probm asks for an independent dominating set D of the given weighted graph such that its weight w(D) =∑v∈D w(v) is inimum.

A graph is bipartite if its vertex set can be partitioned into two independent sets. A graph is cubic if every vertex in the aph has degree three. A graph is at-most-cubic if the degrees of its vertices are all at most three. A graph is planar if it n be embedded in the plane (drawn with points for vertices and curves for edges) without edge-crossings. A graph is grid it is an induced subgraph of a grid. In the former part of this paper, we consider several classes of cubic or at-most-cubic

Supported by grant NSC 100-2628-E-007-020-MY3, Taiwan.

Corresponding author.

E-mail addresses: chinghao.liu@gmail.com (C.-H. Liu), spoon@cs.nthu.edu.tw (S.-H. Poon), yongdottw@hotmail.com (J.-Y. Lin). tp://dx.doi.org/10.1016/j.tcs.2014.09.001 04-3975/© 2014 Published by Elsevier B.V. 2 C.-H. Liu et al. / Theoretical Computer Science 562 (2015) 1–22 gr

In ge

La re

ID a cu is kn bi al

ID fo ap lo er 4N an so th 3S gr th pr th th to on ap f ( w gr gr cu

G gr fo ex re sh ex

FP th po fo ke 4k of gr at effiaphs. A (k, )-graph is a graph such that its vertex set can be partitioned into at most k independent sets and cliques. the latter part of this paper, we turn to consider (k, )-graphs, whose related work is introduced in Section 5.

First, we describe related work on the IDS problem. Garey and Johnson [16] first showed that the IDS problem for neral graphs is NP-complete. Then, Corneil and Perl [10] showed that the IDS problem for bipartite graphs is NP-complete. ter, Clark et al. [9] showed that the IDS problem for grid graphs is NP-complete. In fact, they showed the IDS problem mains NP-complete when restricted to at-most-cubic grid graphs. Zverovich and Zverovich [26] further showed that the

S problem is NP-complete for at-most-cubic planar bipartite graphs of minimum girth some fixed k, where the girth of graph is the length of a shortest cycle contained in the graph. Moreover, Manlove [22] showed that the IDS problem for bic planar graphs is NP-complete. Recently, Song et al. [25] showed that the IDS problem for star-convex bipartite graphs

NP-complete, and the IDS problem for triad-convex bipartite graphs can be solved in polynomial time. To the best of our owledge, the IDS problem for cubic bipartite graphs was open. In this paper, we show that the IDS problem for cubic partite graphs is NP-complete. Moreover, via reduction from the rectilinear planar monotone 3SAT problem, we obtain an ternative but more direct proof for the NP-completeness of the IDS problem on at-most-cubic grid graphs.

Furthermore, we mention related work on the approximation results for the IDS problem. Irving [17] showed that the

S problem for general graphs is not in APX unless P = NP. Then, Kann [18] showed that the IDS problem is APX-complete r graphs of maximum degree a constant B . Alimonti and Calamoneri [2] showed that there is an upper bound 2 for proximation ratio of the IDS problem on at-most-cubic graphs. Later, Chlebík and Chlebíková [8] showed that there is a wer bound 681680 for approximation ratio of the IDS problem on at-most-cubic graphs.