@inproceedings{ffbb3f352213411784fa8229072c71b9,
title = "Complexity and algorithms for semipaired domination in graphs",
abstract = "For a graph G = (V,E) with no isolated vertices, a set D ⊆ V is called a semipaired dominating set of G if (i) D is a dominating set of G, and (ii) D can be partitioned into two element subsets such that the vertices in each two element set are at distance at most two. The minimum cardinality of a semipaired dominating set of G is called the semipaired domination number of G, and is denoted by γpr2(G). The Minimum Semipaired Domination problem is to find a semipaired dominating set of G of cardinality γpr2(G). In this paper, we initiate the algorithmic study of the Minimum Semipaired Domination problem. We show that the decision version of the Minimum Semipaired Domination problem is NP-complete for bipartite graphs and chordal graphs. On the positive side, we present a linear-time algorithm to compute a minimum cardinality semipaired dominating set of interval graphs. We also propose a 1 + ln(2Δ + 2)-approximation algorithm for the Minimum Semipaired Domination problem, where Δ denotes the maximum degree of the graph and show that the Minimum Semipaired Domination problem cannot be approximated within (1−ϵ) ln|V| for any ϵ > 0 unless P=NP.",
keywords = "Approximation algorithm, Bipartite graphs, Chordal graphs, Domination, Graph algorithm, Interval graphs, NP-complete, Semipaired domination",
author = "Henning, {Michael A.} and Arti Pandey and Vikash Tripathi",
note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 30th International Workshop on Combinatorial Algorithms, IWOCA 2019 ; Conference date: 23-07-2019 Through 25-07-2019",
year = "2019",
doi = "10.1007/978-3-030-25005-8_23",
language = "English",
isbn = "9783030250041",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "278--289",
editor = "Colbourn, {Charles J.} and Roberto Grossi and Nadia Pisanti",
booktitle = "Combinatorial Algorithms - 30th International Workshop, IWOCA 2019, Proceedings",
address = "Germany",
}