Algorithmic Aspects of Disjunctive Total Domination in Graphs

For a graph \(G=(V,E)\), \(D\subseteq V\) is a dominating set if every vertex in \(V\!\setminus \!D\) has a neighbor in D. If every vertex in V has to be adjacent to a vertex of D, then D is called a total dominating set of G. The (total) domination problem on G is to find a (total) dominating set D of the minimum cardinality. The (total) domination problem is well-studied. Recently, the following variant is proposed. Vertex subset D is a disjunctive total dominating set if every vertex of V is adjacent to a vertex of D or has at least two vertices in D at distance 2 from it. The disjunctive total domination problem on G is to find a disjunctive total dominating set D of the minimum cardinality. For the complexity issue, the only known result is that the disjunctive total domination problem is NP-hard on general graphs. In this paper, by using a minimum-cost flow algorithm as a subroutine, we show that the disjunctive total domination problem on trees can be solved in polynomial time. This is the first polynomial-time algorithm for the problem on a special class of graphs. Besides, we show that the problem remains NP-hard on bipartite graphs and planar graphs.