Domination and its variants in split graphs -P versus NPC dichotomy

Abstract

We investigate the complexity of minimum total outer-connected domination in split graphs. Given a connected graph G, a minimum total outer-connected dominating set asks for a set $D \subseteq V(G)$ such that it is a total dominating set and the graph induced on $V(G) \setminus D$ is connected. It is known that the Total Outer-Connected Domination problem (TOCD) in general graphs is NP-complete. A split graph is a graph in which the vertex set can be partitioned into a clique and an independent set. Panda et al., have established that the TOCD is NP-complete in split graphs. In this paper, we strengthen this NP-completeness result by presenting an interesting dichotomy: we show that TOCD is NP-complete in split graphs with $\Delta ^I=3$ ($K_{1,5}$-free split graphs) and present a polynomial-time algorithm for TOCD in split graphs with $\Delta ^I=2$ ($K_{1,4}$-free split graphs). We revisit the complexity of domination in split graphs, and prove that in $\Delta ^I=3$ split graphs the domination problem is NP-complete whereas in $\Delta ^I=2$ split graphs the domination problem is polynomial-time solvable.

1 Introduction

The study of domination and its variants has attracted many researchers due its applications in theory and computing [6, 19]. Further, the domination satisfying some specific property has intersting connection to other combinatorial problems, for example, if the property is connected, then the study of connected domination is equivalent to the study of maximum leaf spanning tree problem in graphs [8]. Also, if the input is restricted, then the study of connected (total) domination in split graphs is same as the study of the Steiner tree problem in split graphs [17]. The focus of this paper is two fold; (1) the study of domination in split graphs when the specific property is outer connectedness and total-outer connectedness, (2) identify the hard vs easy instances of domination in split graphs and discover a dichotomy.

A set D is dominating set of V(G), if each vertex in $V(G) \setminus D$ is adjacent to at least one vertex in D [10, 11]. A dominating set D is a total dominating set, if each vertex in D is adjacent to at least one vertex in D, and it is an outer-connected dominating set if the graph induced on $V(G) \setminus D$ is connected. A dominating set D is called a total outer-connected dominating set if D is a total dominating set and an outer-connected dominating set. The study on these variants was initiated by Cyman [4, 5] as it has applications in computer networks and facility location problems [10].

On the computational complexity front, domination and its variants are NP-complete in general graphs. In particular, the Total Outer-Connected Domination problem (TOCD) in split graphs [14] and the Outer-Connected Domination (OCD) problem in split graphs [15] are NP-complete. The aim of this paper is to take a closer look at these reductions in split graphs and identify NP-complete vs polynomial-time solvable input instances. This line of study has been reported in the literature for Steiner tree [17] and Hamiltonicity [16] in split graphs.

It is important to highlight that TOCD is NP-complete in bipartite graphs [9] and polynomial-time solvable in bounded tree-width graphs and trees [14]. OCD is NP-complete in bipartite graphs [4], chordal graphs [12] and polynomial-time solvable in interval graphs and trees [14].On the parameterized complexity front, the domination problem is W[2]-hard on general graphs [2] whereas the complexities of OCD and TOCD on general graphs are open. For these problems, some progress on approximation algorithms is reported in [14].

Our contribution We investigate the NP-complete instances of split graphs [12, 14] and obtain an interesting dichotomy for TOCD and OCD: NP-complete for split graphs with $\Delta ^I=3$ ($K_{1,5}$-free split graphs) and polynomial-time solvable for split graphs with $\Delta ^I=2$ ($K_{1,4}$-free split graphs).

Graph preliminaries Unless explicitly stated we work with simple, undirected and connected graphs. We follow the notations as in [18]. For a graph G, let V(G) denote the vertex set and E(G) denote the edge set. The edge set $E(G)=\{\{u,v\} ~|~u$ is adjacent to v in G}. The open neighborhood of a vertex v is $N_G(v)=\{u \in V(G) ~\vert ~ \{u,v\} \in E(G)\}$ and the closed neighborhood of a vertex v is $N_G[v]=N(v) \cup \{v\}$. For a graph G and a set $H \subseteq V(G)$, G[H] represents the subgraph of G induced on the vertex set H. A split graph G is a graph in which V(G) can be partitioned into two sets; a clique K and an independent set I. A split graph is represented as $G(K \cup I,E)$ and K is a maximal clique. In a split graph, for each vertex u in K, $N^I_G(u)=N_G(u) \cap I$, $d^I_G=\vert N^I_G(u) \vert$ and for each vertex v in I, $N^K_G(v)=N(v) \cap K$, $d^K_G=\vert N^K_G(v) \vert$. For a split graph G, $\Delta ^I_G=\text{ max }\{d^I_G(u)\}, u \in K$ and $\Delta ^K_G=\text{ max }\{d^K_G(v)\}, v \in I$. A matching in a graph is a set of edges with no shared end points. A maximum matching is a matching of maximum size. An edge cover $E_c$ is a set of edges of G such that each vertex of G is incident to some edge of $E_c$. A subgraph is a graph in which each vertex has degree at most three.

2 The total outer-connected domination in split graphs

2.1 Hardness result: TOCD in $\Delta ^I=3$ split graphs

In this section we show that TOCD in $\Delta ^I=3$ split graphs is NP-complete. Using the result of [14], we show that TOCD in $\Delta ^I=3$ split graphs is NP-complete. For the sake of completeness, we present the reduction along with the proof of correctness. We consider EXACT-3-COVER [13] problem, which is a candidate NP-complete problem for our investigation.

EXACT-3-COVER (X3C)

Instance A finite set X with $\vert X \vert =3q$ and a collection ${\mathcal {C}}$ of 3-element subsets of X.

QuestionDoes ${\mathcal {C}}$ contain an exact cover of X, that is, a subcollection $\mathcal {C'}\subseteq {\mathcal {C}}$ such that every element in X belongs to exactly one member of $\mathcal {C'}$?

Decision version of the Total Outer-Connected Domination problem (TOCD) in Split graphs

Instance A split graph.

QuestionDoes there exist a total dominating set D of size at most k such that $G[V \setminus D]$ is connected?

Theorem 1

TOCD is NP-complete for $\Delta ^I=3$ split graphs.

Proof

TOCD is in NP Given a certificate D, we can verify in deterministic polynomial-time that whether D is a total dominating set and $G[V\setminus D]$ is connected. Thus, the total outer-connected domination problem is in NP.

TOCD is NP-Hard Any arbitrary instance of X3C is reduced to TOCD as follows: Let $X=\{x_1, x_2,\ldots ,x_{3q}\}$ and ${\mathcal {C}}=\{C_1,C_2,\ldots ,C_m\}$ be an arbitrary instance of X3C. Each $C_i$ in ${\mathcal {C}}$ is an arbitrary 3-element subset of X. Construct a split graph $G(K\cup I,E)$ where $I=W \cup X,W=\{w_1,w_2,\ldots ,w_{3q}\}, X=\{x_1, x_2,\ldots ,x_{3q}\}$ and $K=C\cup Y\cup Z,C=\{c_1,c_2,\ldots ,c_m\}, Y=\{y_1,y_2,\ldots ,y_{3q}\}, Z=\{z_1,z_2,\ldots ,z_{3q}\}$ and edge set of G as $E(G)=\{ \{x_i, c_j\} ~ \vert x_i \in C_j,1\le i \le 3q, 1\le j \le m\} \cup \{ \{x_i, y_i\} ~\vert 1 \le i \le 3q\}, \{\{z_i, w_i\} ~\vert 1 \le i \le 3q\} \cup \{\{c_j, y_i\} 1 \le i \le 3q, 1 \le j \le m\}, \{\{c_j, z_i\} 1 \le i \le 3q, 1 \le j \le m\}, \{\{y_i, z_i\} \vert 1 \le i \le 3q\}\cup \{\{x_i,x_j\}~|~1\le i<j\le 3q\}\cup \{\{y_i,y_j\}~|~1\le i<j\le 3q\}\cup \{\{z_i,z_j\}~|~1\le i<j\le 3q\}\cup \{\{c_i,c_j\}\mid 1\le i < j \le m\}$. We now show that the instances created by this reduction are $\Delta ^I=3$ split graphs. If on the contrary, G is a graph with $\Delta ^I=4$. Then, there exists a vertex $u \in K$ such that $deg^I(u)=4$. Observe that for each vertex $v \in Z \cup Y$, $deg^I(v)=1$. Hence, $u \notin Z \cup Y$. It follows that $u \in C$. Further, note that the element corresponding to $u \in C$ is a 4-element subset of X, which is a contradiction to the definition of collection ${\mathcal {C}}$. Therefore, it follows that the reduced instances are $\Delta ^I=3$ split graph.

Claim 1

${\mathcal {C}}$ has an exact-3-cover of size q if and only if G has a total outer-connected dominating set of size at most 7q.

Proof

Let $\mathcal {C'}\subseteq {\mathcal {C}}$ be the solution of X3C. Then $\{c_j \vert c_j \in C \wedge C_j \in \mathcal {C'}\} \cup W \cup Z$ is a total outer-connected dominating set of cardinality 7q. Conversely suppose that G has a total outer-connected dominating set, say D of cardinality at most 7q. Since all W vertices are pendant, $W\cup Z \subseteq D$. Let $D'=D\setminus (W\cup Z)$. Then $|D'|\le q$ and $D'$ has to totally dominate all the 3q vertices of X. Suppose that $D'$ contains $d_1$ vertices of set Y and $d_2$ vertices of set C, to totally dominate 3q vertices in X. Also these $d_1+d_2$ vertices can totally dominate $d_1+3d_2$ vertices of the set X. Hence

$3q\le d_1+3d_2\le q+2d_2$

$3q\le q+2d_2$

$q\le d_2$

$d_1+3d_2\le q+2d_2$

$d_1+d_2\le q$

$q\ge d_1+d_2$

$d_2=q$ and $d_1=0$

This implies that $D'$ contains exactly q vertices of the set ${\mathcal {C}}$ to totally dominate all the vertices of the set X. This implies that $\mathcal {C'} = \{C_j | c_j \in D'\}$ is an exact cover of ${\mathcal {C}}$. Hence ${\mathcal {C}}$ has an exact cover if and only if G has a total outer-connected dominating set of cardinality at most 7q.

Theorem 2

The Total Outer-Connected Domination in $\Delta ^I=k$ split graph, $k\ge 3$ is NP-complete.

Proof

Follows from Theorem 1.

2.2 Polynomial result: TOCD in $\Delta ^I=2$ split graphs

In this section, we shall present the other part of the dichotomy; we show that TOCD in $\Delta ^I=2$ split graphs is polynomial-time solvable. Toward this end, we transform a split graph G with $\Delta ^I=2$ into a corresponding graph H which is defined as follows; $V(H)=I$, $E(H)=\{\{u,v\} ~|~ u,v \in V(H) \text{ and } \exists w \in K, \{u,w\}, \{v,w\} \in E(G) \}$. That is, the vertex set of H is the set I of G and two vertices in H is adjacent if there is a clique vertex adjacent to both of them. Further, the minimum edge cover solution of H can be used to find a minimum TOCD of G, which we shall establish in this section.

Claim 2

Let $K'$ be the set of clique vertices corresponding to edges in $E_c$ as per Algorithm 1. Let r be the number of isolated vertices in $V(G) \setminus K'$ as per Algorithm 1. Then, r obtained from Algorithm 1 is minimum.

Proof

Using our construction, it is clear that the edge cover approach identifies the set of clique vertices that totally dominate V(G). It is also clear that a minimum edge cover with minimum r is a minimum total dominating set. In our algorithm, Steps 3-12, fixing a maximum matching, we explore possible maximum matchings followed by minimum edge cover with minimum r. Observe that, this task is being carried for each unmatched vertex. Thus, r is minimum.

Time complexity analysis We make use of algorithm given in [16] to find maximum matching, which incurs $O(n^3)$. Subsequently, we perform DFS to compute r and update the matching as well the edge cover solution. Therefore, the overall time complexity for finding MTOCD algorithm is $O(n^3)$.

Theorem 3

The D output by Algorithm 2 is a minimum TOCD.

Proof

For graph G, let $U \subseteq K$ be the set of clique vertices in D and $I' \subseteq I$ be the set of vertices from I in D. Let $E_c$ be the edge cover solution of $G_s$

Claim

D is a total dominating set.

Proof

Since the solution of edge cover corresponds to clique vertices in G and if there exists any $i\in I$ vertex in D, then all of its neighbors are in D. For each vertex $u \in K$ and $u \notin D$ is dominated by vertices in U (the solution has at least one clique vertex), and for each $i \in I$ and $i \notin D$ has a adjacent vertex in D (edge cover ensures each vertex is covered). For pendant vertices in I, the pendant vertex and its clique neighbor are in D. Hence, D is a total dominating set.

Claim

The graph induced on $V(G) \setminus D$ is connected.

Proof

Clearly, the graph induced on $K \setminus U$ is connected. For each vertex $u \in (I' \setminus I)$, if u is pendant then u and its clique neighbor are in D. This means, the degree of u is at least two and there will be two edges incident on u in H. Of the two, one edge is included in edge cover and hence the corresponding clique vertex in D. The clique vertex corresponding to the other edge ensures outer connectedness. Thus, the claim follows.

Claim

D is MTOCD.

Proof

Suppose if there exists a TOCD $D'$ such that $\vert D'\vert < \vert D \vert$. Then, let $U'=K \cap D'$ and $J=I \cap D'$. Case: $\vert U' \vert < \vert U \vert$. Since $E_c$ is a minimum edge cover solution and hence, the corresponding clique vertex set, $U'$ is also minimum. Hence, this case is not possible. Case: $\vert J\vert < |I'|$, by Claim 2 we know that $I'$ has the minimum number of isolated vertices of I. Hence $\vert J \vert < \vert I' \vert$ is not possible. Thus, D is a minimum TOCD of G.

Remarks

1. If the input split graph has pendant vertices in I, then in any minimum TOCD, we include the closed neighborhood of pendant vertices in the solution. Therefore, we pre-process the input graph before invoking edge cover algorithm.

2. If there is a clique vertex v such that $d_G^I(v)=1$, then we get a self loop at $w \in N_G^I(v)$ in H. We assume that such a self loop edge is included in our maximum matching.

3. Let $G(K \cup I,E)$ be a split graph with no pendant vertices in G. Then, we observe that the minimum TOCD in such split graphs is also the minmum OCD.

Interestingly, for an arbitrary split graph, minimum OCD is NP-complete in $\Delta ^I=3$ split graphs and polynomial-time solvable in $\Delta ^I=2$ split graphs, which we establish in the next section.

3 The Outer-Connected Domination in split graphs

3.1 Outer-Connected Domination in $\Delta ^I=3$ split graphs

We shall now present a polynomial-time reduction from Exact-3-cover problem to Outer-Connected Domination in $\Delta ^I=3$ split graphs.

EXACT-3-COVER(X3C)

Instance A finite set X with $\vert X \vert =3q$ and a collection ${\mathcal {C}}$ of 3-element subsets of X.

Question Does ${\mathcal {C}}$ contain an exact cover of X, that is, a subcollection $\mathcal {C'}\subseteq {\mathcal {C}}$ such that every element in X belongs to exactly one member of $\mathcal {C'}$?

Decision version of Outer-Connected Domination (OCDD) in split graphs

Instance A split graph.

Question Does there exist a dominating set D of size at most k such that $G[V \setminus D]$ is connected?

Theorem 4

Outer-Connected Domination in $\Delta ^I=3$ split graph is NP-complete.

Proof

The outer-connected domination problem is in NP Given a certificate OCD, we can verify in deterministic polynomial-time that whether OCD is a total dominating set and $G[V\setminus OCD]$ is connected. Thus the total outer-connected domination problem is in NP.

The outer-connected domination problem is NP-Hard Any arbitrary instance of X3C is reduced to OCD as follows: Let $X=\{x_1, x_2,\ldots ,x_{3q}\}$ and ${\mathcal {C}}=\{C_1,C_2,\ldots ,C_m\}$ be an arbitrary instance of X3C. Construct vertex set of G as $I=W \cup X, W=\{w_1,w_2,\ldots ,w_{3q}\}, X=\{x_1,x_2,\ldots ,x_{3q}\}$ and $K=C \cup Y \cup Z, C=\{c_1,c_2,\ldots ,c_m\}, Y=\{y_1,y_2,\ldots ,y_{3q}\}, Z=\{z_1,z_2,\ldots ,z_{3q}\}$ and the edge set of G as $E(G)=\{\{x_i, c_j\} \vert x_i \in C_j, 1 \le i \le 3q, 1 \le j \le m\} \cup \{\{x_i, y_i\} \vert 1 \le i \le 3q\}, \{\{z_i, w_i\} \vert 1 \le i \le 3q\} \cup \{\{c_j, y_i\} ~|~ 1\le i \le 3q, 1\le j \le m \}, \{\{c_j, z_i\} ~|~ 1 \le i \le 3q, 1 \le j \le m\}, \{\{y_i, z_i\} \vert 1 \le i \le 3q\}$. We now show that the instances created by this reduction are $\Delta ^I=3$ split graphs. If on the contrary, G is $\Delta ^I=4$ there exists a vertex $u \in K$ such that $deg^I(u)=4$. Observe that for each vertex $u \in Z \cup Y$, $deg^I(u)=1$. Hence, if $deg^I(u)=4$ exists it should be in C. This implies that there exists a 4-element subset in $c\in {\mathcal {C}}$ corresponding to $u\in C$, which is a contradiction as all the subsets are of size 3 in ${\mathcal {C}}$. Therefore it follows that the reduced split graph is $\Delta ^I=3$ split graph. An illustration is given in Fig. 1.

Fig. 1

An example reduction for Outer Connected Domination

Claim 3

${\mathcal {C}}$ has an exact cover of size q if and only if G has a total outer-connected dominating set of size at most 4q.

Proof

Let $\mathcal {C'}$ be the solution of X3C. Then $\{c_j \vert \mathcal {C'}\}\cup W$ is a outer-connected dominating set of cardinality 4q.

Conversely suppose that G has a outer-connected dominating set, say D of cardinality at most 4q. Since all W vertices are pendant, $W \subseteq D$. Let $D'=D\setminus (W)$. Then $D'\le q$ and $D'$ has to dominate all the 3q vertices of X. Suppose that $D'$ contains $d_1$ vertices of set Y and $d_2$ vertices of set C, to dominate 3q vertices of X. Also these $d_1+d_2$ vertices can dominate $d_1+3d_2$ vertices of the set X. Hence

$3q\le d_1+3d_2\le q+2d_2$

$3q\le q+2d_2$

$q\le d_2$

$d_1+3d_2\le q+2d_2$

$d_1+d_2\le q$

$q\ge d_1+d_2$

$d_2=q$ and $d_1=0$

This implies that $D'$ contains exactly q vertices of the set ${\mathcal {C}}$ to dominate all the vertices of the set X. This implies that $\mathcal {C'} = \{C_j | c_j \in D'\}$ is an exact cover of ${\mathcal {C}}$. Hence, ${\mathcal {C}}$ has an exact cover if and only if G has a outer-connected dominating set of cardinality at most 4q.

Theorem 5

Outer-Connected Domination in $\Delta ^I=k$ split graph, $k\ge 3$ is NP-complete.

Proof

Follows from Theorem 4

3.2 Polynomial result: OCD in $\Delta ^I=2$ split graphs

In this section, we present a polynomial-time algorithm for minimum OCD in $\Delta ^I=2$ split graphs. We make use of the transformation presented in Sect. 2.2.

Theorem 6

The set D obtained from Algorithm 3 is MOCD.

Proof

Clearly, all pendant vertices in I is included in D. For each edge in the maximum matching, the corresponding clique vertices are also in D. The current solution which includes pendant vertices and clique vertices corresponding to the maximum matching cannot dominate any unmatched vertex of G. Therefore, we include all unmatched vertices in D. Thus, D is MOCD. $\square$

Time complexity analysis Computing maximum matching [16] takes $O(n^3)$ and hence, the time complexity of Algorithm 3 is $O(n^3)$.

4 Domination in $\Delta ^I=3$ Split graphs

In this section, we show that the dominating set in $\Delta ^I=3$ split graphs is NP-complete. Although dominating set is NP-complete in split graphs [1], the reduction instances cannot bounded by degree for both K and I. Interestingly, the reduction presented here generates instances of $\Delta ^I=3$ split graphs. We present a polynomial-time reduction from Exact-3-cover problem.

Decision version of Domination (DD)

Instance A split graph.

Question Does there exist a dominating set D of size at most k?

Theorem 7

The Domination problem in $\Delta ^I=3$ split graph is NP-complete.

Proof

The domination problem is NP-Hard Any arbitrary instance of X3C is reduced to OCD as follows: Let $X=\{x_1, x_2,\ldots ,x_{3q}\}$ and ${\mathcal {C}}=\{C_1,C_2,\ldots ,C_m\}$ be an arbitrary instance of X3C. Construct vertex set of G as $I=\{X\}, X=\{x_1, x_2,\ldots ,x_{3q}\}$ and $K=\{C\},C=\{c_1,c_2,\ldots ,c_m\}$ and the edge set of G as $E(G)=\{\{x_i, c_j\} \vert x_i \in C_j,1 \le i \le 3q, 1 \le j \le m\} \cup \{\{c_i, c_j\} \vert 1 \le i, j \le m\}$. We now show that the instances created by this reduction are $\Delta ^I=3$ split graphs. If on the contrary, G is $\Delta ^I=4$ there exists a vertex $u \in K$ such that $deg^I(u)=4$. Observe that for each vertex $u \in Z$, $deg^I(u)=1$. Hence if $deg^I(u)=4$ exists it should be in C. This implies that there exists a 4-element subset in $c \in {\mathcal {C}}$ corresponding to $u \in C$, which is a contradiction as all the subsets are of size 3 in ${\mathcal {C}}$. Therefore, it follows that the reduced split graph is $\Delta ^I=3$ split graph. An example reduction is illustrated in Figure 2.

Fig. 2

An Example reduction for Domination in Split graphs

Claim 4

${\mathcal {C}}$ has an exact cover of size q if and only if G has an dominating set of size at most q.

Proof

Let $\mathcal {C'}$ be the solution of X3C. Then $\{c_j \vert C_j\in \mathcal {C'},c_j\in C\}$ is a dominating set of cardinality q. Conversely, suppose that G has a dominating set, say D of cardinality at most q. D has to dominate all the 3q vertices of X. Since $\vert X \vert$ has 3q and q vertices of K should dominate all of I This implies that $D'$ contains exactly q vertices of the set ${\mathcal {C}}$ to dominate all the vertices of the set X. This implies that $\mathcal {C'} = \{C_j | c_j \in D'\}$ is an exact cover of ${\mathcal {C}}$. Hence ${\mathcal {C}}$ has an exact cover if and only if G has a dominating set of cardinality at most q. $\square$

Theorem 8

The Domination problem in $\Delta ^I=k$ split graph, $k\ge 3$ is NP-complete.

Proof

Follows from Theorem 7

4.1 Domination in $\Delta ^I=2$ split graphs

In this section, we prove that the Steiner tree problem and the dominating set problem in split graphs are of same complexity.

Theorem 9

Let $G(K \cup I,E)$ be a split graph. G with $R=I$, the terminal set and S is a minimum Steiner set if and only if S is a minimum dominating set of G.

Proof

When the terminal vertices are $R=I$, then the minimum Steiner set S are clique vertices, $S \subseteq K$. Clearly, S is a minimum dominating set of G. Suppose if there exists a dominating set for G whose cardinality is less than S, then it contradicts the minimality of S. Hence, S is a minimum dominating set of G.

Converse: if D is a dominating set of G with $v \in D \cap I$, then we obtain another dominating set $D'=(D \setminus \{v\}) \cup \{w\}$, where w is a clique neighbor of v. This shows that, there exists a minimum dominating set $D \subseteq K$. Thus, D is a minimum Steiner set with terminal set $R=I$.

The Steiner tree problem and its solution for $\Delta ^I=2$ ($K_{1,4}$-free) split graphs is reported in [17]. Therefore, the dominating set problem for $\Delta ^I=2$ split graphs is also polynomial-time solvable.

Observation 1

Let $G(K\cup I,E)$ be a split graph. G with $R=I$, the terminal set and S is a minimum Steiner set if and only if S is a minimum total dominating set of G.

Observation 2

Let $G(K\cup I,E)$ be a split graph. D is total dominating set if and only if D is the connected dominating set of G.

Conclusions and Directions for further research: In this paper, we have investigated domination and its variants in split graphs, and presented dichotomy results for outer connected domination and total outer connected domination problems. In particular, we have strengthen the results of [14] and identify the borderline between polynomial-time solvable input instances and NP-complete input instances. The complexity of these domination problems in other subclasses of chordal and bipartite graphs are open. This would be an interesting direction for further research.