For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 Complexity of the Minimum Single Dominating Cycle Problem for Graph ClassesHiroshi ETO  Hiroyuki KAWAHARA  Eiji MIYANO  Natsuki NONOUE  Publication IEICE TRANSACTIONS on Information and Systems   Vol.E101-D   No.3   pp.574-581Publication Date: 2018/03/01 Online ISSN: 1745-1361 DOI: 10.1587/transinf.2017FCP0007 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theoretical Computer Science —)Category: Keyword: minimum single dominating problem,  graph classes,  (in)tractability,  (in)approximability,  Full Text: PDF>> Buy this Article Summary:  In this paper, we study a variant of the MINIMUM DOMINATING SET problem. Given an unweighted undirected graph G=(V,E) of n=|V| vertices, the goal of the MINIMUM SINGLE DOMINATING CYCLE problem (MinSDC) is to find a single shortest cycle which dominates all vertices, i.e., a cycle C such that for the set V(C) of vertices in C and the set N(V(C)) of neighbor vertices of C, V(G)=V(C)∪N(V(C)) and |V(C)| is minimum over all dominating cycles in G [6], [17], [24]. In this paper we consider the (in)approximability of MinSDC if input graphs are restricted to some special classes of graphs. We first show that MinSDC is still NP-hard to approximate even when restricted to planar, bipartite, chordal, or r-regular (r≥3). Then, we show the (lnn+1)-approximability and the (1-ε)lnn-inapproximability of MinSDC on split graphs under P≠NP. Furthermore, we explicitly design a linear-time algorithm to solve MinSDC for graphs with bounded treewidth and estimate the hidden constant factor of its running time-bound.