Algorithmic and complexity aspects of problems related to total restrained domination for graphs

Yu Yang, Cai-Xia Wang and Shou-Jun Xu ()
Additional contact information
Yu Yang: Lanzhou University
Cai-Xia Wang: Lanzhou University
Shou-Jun Xu: Lanzhou University

Journal of Combinatorial Optimization, 2023, vol. 46, issue 5, No 1, 20 pages

Abstract: Abstract Let G be a graph with vertex set V and a subset $$D\subseteq V$$ D ⊆ V . D is a total dominating set of G if every vertex in V is adjacent to a vertex in D. D is a restrained dominating set of G if every vertex in $$V\setminus D$$ V \ D is adjacent to a vertex in D and another vertex in $$V\setminus D$$ V \ D . D is a total restrained dominating set if D is both a total dominating set and a restrained dominating set. The minimum cardinality of total dominating sets (resp. restrained dominating sets, total restrained dominating sets) of G is called the total domination number (resp. restrained domination number, total restrained domination number) of G, denoted by $$\gamma _{t}(G)$$ γ t ( G ) (resp. $$\gamma _{r}(G)$$ γ r ( G ) , $$\gamma _{tr}(G)$$ γ tr ( G ) ). The MINIMUM TOTAL RESTRAINED DOMINATION (MTRD) problem for a graph G is to find a total restrained dominating set of minimum cardinality of G. The TOTAL RESTRAINED DOMINATION DECISION (TRDD) problem is the decision version of the MTRD problem. In this paper, firstly, we show that the TRDD problem is NP-complete for undirected path graphs, circle graphs, S-CB graphs and C-CB graphs, respectively, and that, for a S-CB graph or C-CB graph with n vertices, the MTRD problem cannot be approximated within a factor of $$(1-\epsilon )\textrm{ln} n$$ ( 1 - ϵ ) ln n for any $$\epsilon >0$$ ϵ > 0 unless $$NP\subseteq DTIME(n^{O(\textrm{loglog}n)})$$ N P ⊆ D T I M E ( n O ( loglog n ) ) . Secondly, for a graph G, we prove that the problem of deciding whether $$\gamma _{r}(G) =\gamma _{tr}(G)$$ γ r ( G ) = γ tr ( G ) is NP-hard even when G is restricted to planar graphs with maximum degree at most 4, and that the problem of deciding whether $$\gamma _{t}(G) =\gamma _{tr}(G)$$ γ t ( G ) = γ tr ( G ) is NP-hard even when G is restricted to planar bipartite graphs with maximum degree at most 5. Thirdly, we show that the MTRD problem is APX-complete for bipartite graphs with maximum degree at most 4. Finally, we design a linear-time algorithm for solving the MTRD problem for generalized series–parallel graphs.

Keywords: Total domination number; Restrained domination number; Total restrained domination number; NP-complete; APX-complete; Linear algorithm (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01090-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:46:y:2023:i:5:d:10.1007_s10878-023-01090-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01090-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().