Weighted Efficient Domination for $P_6$-Free and for $P_5$-Free Graphs

Abstract

In a finite undirected graph $G=(V,E)$, a vertex $v \in V$ dominates itself and its neighbors in G. A vertex set $D \subseteq V$ is an efficient dominating set (e.d.s. for short) of G if every $v \in V$ is dominated in G by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in G, is known to be $\mathbb {NP}$-complete for $P_7$-free graphs and solvable in polynomial time for $P_5$-free graphs. The $P_6$-free case was the last open question for the complexity of ED on F-free graphs.

Recently, Lokshtanov, Pilipczuk and van Leeuwen showed that weighted ED is solvable in polynomial time for $P_6$-free graphs, based on their quasi-polynomial algorithm for the Maximum Weight Independent Set problem for $P_6$-free graphs. Independently, by a direct approach which is simpler and faster, we found an $\mathcal{O}(n^5 m)$ time solution for weighted ED on $P_6$-free graphs. Moreover, we showed that weighted ED is solvable in linear time for $P_5$-free graphs which solves another open question for the complexity of (weighted) ED.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Let $G=(V,E)$ be a finite undirected graph without loops and multiple edges; let $|V|=n$ and $|E|=m$. A vertex $v \in V$ dominates itself and its neighbors. A vertex subset $D \subseteq V$ is an efficient dominating set (e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex in D.

The notion of efficient domination was introduced by Biggs [1] under the name perfect code. Note that not every graph has an e.d.s.; the Efficient Dominating Set (ED) problem asks for the existence of an e.d.s. in a given graph G. We can assume that G is connected; if not then the ED problem for G can be splitted into ED for each of its connected components. If a graph G with vertex weight function $w: V \rightarrow \mathbb {Z} \cup \{\infty ,-\infty \}$ and an integer k is given, the Minimum Weight Efficient Dominating Set (WED) problem asks whether G has an e.d.s. D of total weight $w(D):=\Sigma _{x \in D} w(x) \le k$.

As mentioned in [4], the maximization version of WED can be defined analogously, replacing the condition $w(D) \le k$ with $w(D) \ge k$. Since negative weights are allowed, the maximization version of WED is equivalent to its minimization version; subsequently we restrict the problem to the minimization version WED. The vertex weight $\infty$ plays a special role; vertices which are definitely not in any e.d.s. get weight $\infty$, and thus, in the WED problem we are asking for an e.d.s. of finite minimum weight. Let $\gamma _{ed}(G,w)$ denote the minimum weight of an e.d.s. in G. We call a vertex $x \in V$ forced if x is contained in every e.d.s. of finite weight in G.

The importance of the ED problem for graphs mostly results from the fact that it is a special case of the Exact Cover problem for hypergraphs (problem [SP2] of [9]); ED is the Exact Cover problem for the closed neighborhood hypergraph of G.

For a subset $U \subseteq V$, let G[U] denote the induced subgraph of G with vertex set U. For a graph F, a graph G is F -free if G does not contain any induced subgraph isomorphic to F. Let $P_k$ denote a chordless path with k vertices. $F+F'$ denotes the disjoint union of graphs F and $F'$; for example, $2P_3$ denotes $P_3+P_3$.

Many papers have studied the complexity of ED on special graph classes - see e.g. [3–6, 12] for references. In particular, a standard reduction from the Exact Cover problem shows that ED remains $\mathbb {NP}$-complete for $2P_3$-free (and thus, for $P_7$-free) chordal graphs. For $P_6$-free graphs, the question whether ED can be solved in polynomial time was the last open case for F-free graphs [5]; it was the main open question in [6]. As a first step towards a dichotomy, it was shown in [3] that for $P_6$-free chordal graphs, WED is solvable in polynomial time.

Recently, it has been shown by Lokshtanov et al. [10] that WED is solvable in polynomial time for $P_6$-free graphs (the time bound is more than $\mathcal{O}(n^{500})$). Their result for WED is based on their quasi-polynomial algorithm for the Maximum Weight Independent Set problem for $P_6$-free graphs. Independently, in [7] we found a polynomial time solution for WED on $P_6$-free graphs using a direct approach which is simpler than the one in [10] and leads to the much better time bound $\mathcal{O}(n^5 m)$. According to [5], the results of [7, 10] finally lead to a dichotomy for the WED problem on $P_k$-free graphs and moreover on F-free graphs.

In our approach, we need the following notion: A graph $G=(V,E)$ is unipolar if there is a partition of V into sets A and B such that G[A] is $P_3$-free (i.e., the disjoint union of cliques) and G[B] is a complete graph. See e.g. [8, 11] for recent work on unipolar graphs. Note that ED remains $\mathbb {NP}$-complete for unipolar graphs [8] (which can also be seen by the standard reduction from Exact Cover; there, every clique in G[A] has only two vertices). Clearly, every unipolar graph is $2P_3$-free and thus $P_7$-free. It follows that for each $k \ge 7$, WED is NP-complete for $P_k$-free unipolar graphs.

The main results of this paper are the following:

• 1. In Sect. 2, we give a polynomial time reduction of the WED problem for $P_6$-free graphs to WED for $P_6$-free unipolar graphs.

• 2. In Sect. 3, we solve WED for $P_6$-free unipolar graphs in polynomial time.

• 3. In Sect. 4, we describe the polynomial time algorithm for the WED problem on $P_6$-free graphs. Thus, we obtain a dichotomy for the WED problem on F-free graphs, and in particular on $P_k$-free graphs and on $P_k$-free unipolar graphs.

In the full version of this paper, we describe a linear time algorithm for WED on $P_5$-free graphs based on modular decomposition (see [2] for details); this answers another open question in [6].

Due to space limitation, most of the proofs and the linear time algorithm for WED on $P_5$-free graphs cannot be given here.

2 Reducing WED on $P_6$-Free Graphs to WED on $P_6$-Free Unipolar Graphs

Throughout this section, let $G=(V,E)$ be a connected $P_6$-free graph. Subsequently we consider the distance levels of $v \in V$ according to the usual approach which is used already in various papers such as [6]. For $v \in V$, let $N_i(v)$ denote the i-th distance level of v, that is $N_i(v)=\{u \in V \mid d_G(u,v)=i\}$. Then, since G is $P_6$-free, we have $N_i(v) = \emptyset$ for each $i \ge 5$. If $v \in D$ for an e.d.s. D of G then, by the e.d.s. property, we have

$$\begin{aligned} (N_1(v) \cup N_2(v)) \cap D = \emptyset . \end{aligned}$$

(1)

Let $G_v := (N_2(v) \cup N_3(v) \cup N_4(v),E_v)$ such that $N_2(v)$ is turned into a clique by correspondingly adding edges, i.e., $E_v = E' \cup F$ where $E'$ is the set of the original edges in $G[N_2(v) \cup N_3(v) \cup N_4(v)]$ and F is the set of new edges turning $N_2(v)$ into a clique, and let $w(x):=\infty$ for every $x \in N_2(v)$. We first claim:

Proposition 1

$G_v$ is $P_6$-free.

Proof

Suppose to the contrary that there is a $P_6$ P in $G_v$, say with vertices a, b, c, d, e, f and edges ab, bc, cd, de, ef. If $\{ab,bc,cd,de,ef\} \cap F = \emptyset$ then P would be a $P_6$ in G which is a contradiction. Thus, $\{ab,bc,cd,de,ef\} \cap F \ne \emptyset$. Then clearly, $|\{ab,bc,cd,de,ef\} \cap F| = 1$ since $N_2(v)$ is a clique in $G_v$. Now in any case, we get a $P_6$ in G by adding N[v] and the corresponding edges in N[v] and between $N_1(v)$ and $N_2(v)$ which is a contradiction. $\square$

Obviously, the following holds:

Proposition 2

 

(i):

For vertex $v \in V$ with $w(v) < \infty$, D is a finite weight e.d.s. in G with $v \in D$ if and only if $D \setminus \{v\}$ is a finite weight e.d.s. in $G_v$.

(ii):

Thus, if for every $v \in V$, WED is solvable in time T for $G_v$ then WED is solvable in time $n \cdot T$ for G.

From now on, let D(v) denote an e.d.s. of finite weight of $G_v$. We call a vertex x v -forced if $x \in D(v)$ for every e.d.s. D(v) of finite weight of $G_v$ and v -excluded if $x \notin D(v)$ for every such e.d.s. D(v) of $G_v$. Clearly, if x is v-excluded then we can set $w(x)=\infty$, e.g., for all $x \in N_2(v)$, $w(x)=\infty$ as above.

Let $Q_1, \ldots , Q_r$ denote the connected components of $G_v[N_3(v) \cup N_4(v)]$ (i.e., of $G[N_3(v) \cup N_4(v)]$). By (1), we have:

$$\begin{aligned} \text {For each}\, i \in \{1,\ldots , r\},\,\text {we have}\,|Q_i \cap D(v)| \ge 1. \end{aligned}$$

(2)

Clearly, the D(v)-candidates in $Q_i$ must have finite weight.

A component $Q_i$ is trivial if $|Q_i|=1$. Obviously, by (2), the vertices of the trivial components are v-forced.

Clearly, since D(v) is an e.d.s. of finite weight, every $x \in N_2(v)$ must contact a component $Q_i$ for some $i \in \{1,\ldots , r\}$.

2.1 Join-Reduction

Now we consider a graph $G=(A \cup B,E)$ such that $A_1,\ldots ,A_k$ are the components of G[A], and a vertex weight function w with $w(b)=\infty$ for all $b \in B$. Assume that G has an e.d.s. D of finite weight. As above, we can assume that every component $A_i$ is nontrivial since any trivial component $A_i$ consists of a forced D-vertex.

By the e.d.s. property of D, we have (analogously to condition (2)):

$$\begin{aligned} \text {For every}\, x \in B, x \textcircled {1}A_i\,\text {for at most one}\, i \in \{1,\ldots ,k\}. \end{aligned}$$

(3)

Thus, from now on, we can assume that every vertex $x \in B$ has a join to at most one component $A_i$. Moreover, if $x \textcircled {1}A_i$ for some $i \in \{1,\ldots , k\}$ then for every neighbor $y \in A_j$ of x, $j \ne i$, $y \notin D$, i.e., we can set $w(y)=\infty$, and thus, $y \notin D$ for any e.d.s. D of finite weight of G.

For any vertex $x \in B$ with $x \textcircled {1}A_i$ for exactly one $i \in \{1,\ldots , k\}$, by the e.d.s. property of D, $|D \cap A_i| \ge 2$ is impossible. Thus, x is correctly dominated if $|D \cap A_i|=1$, that is, the D-candidates in $A_i$ are universal for $A_i$; let $U_i$ denote the set of universal vertices in $A_i$ (note that $U_i$ is a clique). Clearly, for $x \textcircled {1}A_i$ we have:

$$\begin{aligned} \text {If}\,U_i=\emptyset \,\text {then}\,G\,\text {has no finite weight e.d.s.} \end{aligned}$$

(4)

Thus, for every $A_i$ such that there is a vertex $x \in B$ with $x \textcircled {1}A_i$, we can reduce $A_i$ to the clique $U_i$, we can omit x in B, and for every neighbor $y \in A_j$ of x, $j \ne i$, we set $w(y)=\infty$. The following algorithm is needed twice in this manuscript:

Join-Reduction Algorithm

Given: A graph $G=(A \cup B,E)$ such that $A_1,\ldots ,A_k$ are the components of G[A], and a vertex weight function w with $w(b)=\infty$ for all $b \in B$.

Task: Reduce G in time $\mathcal{O}(n^3)$ to an induced subgraph $G'=(A' \cup B',E')$ with weight function $w'$ and components $A'_1,\ldots ,A'_k$ of $G[A']$ such that we have:

(i):

For every $b \in B'$ and every $i \in \{1,\ldots ,k\}$, if b contacts (nontrivial) component $A'_i$ then b distinguishes $A'_i$.

(ii):

$\gamma _{ed}(G,w)=\gamma _{ed}(G',w') < \infty$ or state that G has no such e.d.s.

Lemma 1

The Join-Reduction Algorithm is correct and can be done in time $\mathcal{O}(n^3)$.

For applying the Join-Reduction Algorithm to $G_v$, we set $B := N_2(v)$ and $A := N_3(v) \cup N_4(v)$. For reducing WED on G to WED on a unipolar graph $G'$, this is a first step which, by condition (i) of the Task, leads to the fact that finally, for every nontrivial component $Q_j$ of $G[N_3(v) \cup N_4(v)]$, every vertex in $N_2(v)$ which contacts $Q_j$ also distinguishes $Q_j$.

2.2 Component-Reduction

Let $G'_v=(A' \cup B',E')$ be the result of applying the Join-Reduction algorithm to $G_v$; let $B'$ be the corresponding subset of $N_2(v)$ and let $A'$ be the corresponding subset of $N_3(v) \cup N_4(v)$. Recall that in $G'_v$, $B'$ is a clique. In the next step, we reduce WED for $G_v$ to WED for unipolar graphs.

We consider the components $Q_i$ of $G'_v[A']$ which are not yet a clique; as already mentioned, we can assume that if $x \in B'$ has a neighbor in $Q_i$ then it has a neighbor and a non-neighbor in $Q_i$. For $1 \le i \le r$, let $Q^+_i(x):=Q_i \cap N(x)$ and $Q^-_i(x):= Q_i \setminus N(x)$. Since $Q_i$ is connected, we have: If x distinguishes $Q_i$ then it distinguishes an edge in $Q_i$.

For $x,x' \in B'$ and edges $y_1z_1$ in $Q_i$, $y_2z_2$ in $Q_j$, $i \ne j$, let $xy_1 \in E, xz_1 \notin E$ and $x'y_2 \in E, x'z_2 \notin E$. Then, since G and $G_v$ are $P_6$-free, we have:

$$\begin{aligned} xy_2 \in E\,\text {or}\, xz_2 \in E\,\text {or}\,x'y_1 \in E\,\text {or}\,x'z_1 \in E. \end{aligned}$$

(5)

Another useful $P_6$-freeness argument is the following:

$$\begin{aligned} \text {For}\,x \in B'\,\text {and}\,y \in Q^+_i(x), y\,\text {does not distinguish any edge in}\,Q^-_i(x). \end{aligned}$$

(6)

We claim:

$$\begin{aligned} \text {There is a vertex}\,b^* \in B'\,\text {which contacts}\,Q_i\, \text {for every}\,i \in \{1,\ldots , r\}. \end{aligned}$$

(7)

Let $q^* \in D(v)$ be the vertex dominating $b^*$; without loss of generality assume that $q^* \in Q_1$, and let $D(v,q^*)$ denote a finite weight e.d.s. of $G_v$ containing $q^*$. $Q_1$ is partitioned into

• $Z:=N[q^*] \cap Q_1$,

• $W:=Q_1 \cap N(b^*) \setminus Z$, and

• $Y:=Q_1 \setminus (Z \cup W)$.

Then clearly, the following properties hold:

Lemma 2

 

(i):

$Z \cap D(v,q^*)=\{q^*\}$.

(ii):

$W \cap D(v,q^*)=\emptyset$.

(iii):

$Z \textcircled {0}Y$.

(iv):

For every component K of G[Y], the set of $D(v,q^*)$-candidate vertices in K is a clique.

For the algorithmic approach, we set $w(y)=\infty$ for every $y \in W$ and for every non-universal vertex $y \in K$ in any component K of $G_v[Y]$.

For $i \ge 2$, let $Q^+_i:=Q_i \cap N(b^*)$ and $Q^-_i:=Q_i \setminus N(b^*)$. Clearly, by the e.d.s. property, for every $i \ge 2$, $Q^+_i \cap D(v,q^*)=\emptyset$; set $w(y)=\infty$ for every $y \in Q^+_i$. Thus, the components of $G[Q^-_i]$ must contain the corresponding $D(v,q^*)$-vertices.

Again, as in Lemma 2 (iv), for each such component K, the $D(v,q^*)$-candidates must be universal vertices for K since by (6), two such $D(v,q^*)$-candidates in K would have a common neighbor in $Q^+_i$, i.e., only the universal vertices of component K are the $D(v,q^*)$-candidate vertices; set $w(y)=\infty$ for every non-universal vertex $y \in K$.

Let $I := \{a \in A' : w(a) = \infty \}$. Then I admits a partition $\{I_1,I_2,I_3\}$ as defined below:

• $I_1$ is formed by those vertices of I which are either in Z, or in Y, or in $Q^-_i$ for $i \ge 2$.

• $I_2$ is formed by those vertices of I which are either in W and contact exactly one component of G[Y] or in $Q^+_i$ and contact exactly one component of $G[Q^-_i]$ for $i \ge 2$.

• $I_3$ is formed by those vertices of I which are either in $W \setminus I_2$ or in $Q^+_i \setminus I_2$ for $i \ge 2$.

Note that we have:

(a):

By construction and by the e.d.s. property, if $I_3 \ne \emptyset$ then $D(v,q^*)$ does not exist (in fact each vertex of $I_3$ either would not be dominated by any $D(v,q^*)$-candidate or would be dominated by more than one $D(v,q^*)$-candidate).

(b):

By construction, if $D(v,q^*)$ exists then $D(v,q^*)$ is an e.d.s. of $G'_v[(A' \cup B') \setminus (I_1 \cup I_2)]$ as well; in particular, by construction and by (6), each vertex of $I_1 \cup I_2$ is dominated in $G'_v$ by exactly one vertex of $D(v,q^*)$; then vertices of $I_1 \cup I_2$ can be removed.

(c):

$G'_v[(A' \cup B') \setminus (I_1 \cup I_2)]$ is unipolar (once assuming that $I_3 = \emptyset$).

Then for every potential D(v)-neighbor $q^*$ of $b^*$, we can reduce the WED problem for $G'_v$ to the WED problem for $G'_v(q^*)$ consisting of $B'$ and the $P_3$-free subgraph induced by $\{q^*\}$ and by the corresponding cliques of universal vertices in components K as described above with respect to $D(v,q^*)$. Clearly, the $D(v,q^*)$-candidates in the cliques of the $P_3$-free subgraph can be chosen corresponding to optimal weights.

Summarizing, we can do the following:

Component-Reduction Algorithm

Given: The result $H=G'_v=(A' \cup B',E')$ with vertex weight function w of applying the Join-Reduction algorithm to $G_v$ such that $K_1,\ldots ,K_s$ denote the clique components and $Q_1,\ldots ,Q_r$ denote the non-clique components of $G'_v[A']$.

Task: Reduce H in time $\mathcal{O}(n^3)$ to (less than n) unipolar graphs $H_{\ell }=G'(q^*)$ with weight function $w_{\ell }$, $1 \le \ell < n$, such that $\gamma _{ed}(H,w)= \min _{\ell } \gamma _{ed}(H_{\ell },w_{\ell })$ or state that H has no e.d.s. of finite weight.

begin

(a):

Determine a vertex $b^* \in B'$ contacting every $Q_i$, $i \in \{1,\ldots , r\}$.

(b):

For every $q^* \in N(b^*) \cap A'$ with $w(q^*) < \infty$, say $q^* \in Q_i$, reduce $Q_i$ according to Lemma 2 and for all j, $j \ne i$, reduce $Q_j$ according to the paragraph after the proof of Lemma 2 such that finally, the resulting subgraph $G'(q^*)$ is unipolar.

end

Lemma 3

The Component-Reduction Algorithm is correct and can be done in time $\mathcal{O}(n^3)$.

Corollary 1

If WED is solvable in polynomial time on $P_6$-free unipolar graphs then it is solvable in polynomial time on $P_6$-free graphs.

3 Solving WED on $P_6$-Free Unipolar Graphs in Polynomial Time

Throughout this section, let $G=(V,E)$ be a connected $P_6$-free unipolar graph with partition $V=A \cup B$ such that G[A] is the disjoint union of cliques $A_1,\ldots ,A_k$, and G[B] is a complete subgraph. Clearly, if $k \le 3$ then every e.d.s. of G contains at most four vertices. Thus, from now on, we can assume that $k \ge 4$. In particular, for any e.d.s. D of G, $|D \cap B| \le 1$. Thus, WED for such graphs is solvable in polynomial time if and only if WED is solvable in polynomial time for e.d.s. D with $B \cap D = \emptyset$.

Clearly, for a $P_6$-free unipolar graph, the following holds (recall (5)):

Claim 1

If for distinct $b_1,b_2 \in B$, $b_1$ distinguishes an edge $x_1x_2$ in $A_i$ and $b_2$ distinguishes an edge $y_1y_2$ in $A_j$, $i \ne j$, then either $b_2$ contacts $\{x_1,x_2\}$ or $b_1$ contacts $\{y_1,y_2\}$.

The key result of this section is the following:

Lemma 4

For connected unipolar graphs fulfilling Claim 1, it can be checked in polynomial time whether G has a finite weight e.d.s. D with $B \cap D = \emptyset$.

Lemma 4 is based on various propositions described subsequently. As a first step, we again reduce G corresponding to the Join-Reduction Algorithm of Sect. 2: Since $B \cap D=\emptyset$, clearly, $|D \cap A_i|=1$ for every $i \in \{1,\ldots ,k\}$. Thus, if $A_i=\{a_i\}$ then $a_i$ is a forced D-vertex; from now on, we can assume that every $A_i$ is nontrivial.

Moreover, every $b \in B$ must contact at least one $A_i$, and if b has a join to two components $A_i,A_j$, $i \ne j$, then G does not have an e.d.s. Thus, by (3) and the subsequent paragraph in Sect. 2, from now on, we can assume that no vertex $b \in B$ has a join to any $A_i$, i.e., if b contacts $A_i$ then it distinguishes $A_i$.

Again, as by (7), there is a vertex $b^* \in B$ which contacts every $A_i$. However, we need a stronger property. For this, we define the following notions:

Definition 1

For vertices $b_1,b_2 \in B$ and a nontrivial component $K=A_i$ of A, we say:

(i):

$b_2$ overtakes $b_1$ for K if $b_2$ distinguishes an edge in $K \setminus N(b_1)$.

(ii):

$b_2$ includes $b_1$ for K if $N(b_2) \cap K \supseteq N(b_1) \cap K$.

(iii):

$b_2$ strictly includes $b_1$ for K if $N(b_2) \cap K \supset N(b_1) \cap K$.

(iv):

$b_1$ and $b_2$ cover K if $N(b_1) \cup N(b_2) = K$.

(v):

$b_1 \rightarrow b_2$ if $b_2$ overtakes $b_1$ for at least three distinct nontrivial components of A.

(vi):

$b^* \in B$ is a good vertex of B if for none of the vertices $b \in B \setminus \{b^*\}$, $b^* \rightarrow b$ holds.

Assume that G has an e.d.s. D of finite weight.

Claim 2

For vertices $b_1,b_2 \in B$, we have:

(i):

$b_1$ and $b_2$ cover at most two $A_i$, $A_j$, $i,j \in \{1,\ldots ,k\}$, $i \ne j$.

(ii):

If $b_2$ overtakes $b_1$ for $A_i$ then for any $A_j$, $j \ne i$, $b_1$ does not overtake $b_2$.

(iii):

If $b_2$ overtakes $b_1$ for some $A_i, A_j$, $i \ne j$, then $b_2$ strictly includes $b_1$ for $A_i, A_j$.

(iv):

If $b_2$ overtakes $b_1$ for some $A_i, A_j$, $i \ne j$, then $b_2$ includes $b_1$ for all but at most two $A_{\ell }$, $1 \le \ell \le k$.

(v):

If $b_2$ strictly includes $b_1$ for some $A_i$ then $b_2$ includes $b_1$ for all but at most two $A_{\ell }$, $1 \le \ell \le k$.

Let $H=(B,F)$ denote the directed graph with vertex set B and edges $b \rightarrow b' \in F$ as in Definition 1 (v). Thus, a good vertex of B is one with outdegree 0 with respect to H. As usual, H is a directed acyclic graph (dag for short) if there is no directed cycle in H.

Claim 3

H is a dag.

It is well known that any dag has a vertex with outdegree 0. Thus, Claim 3 implies:

Claim 4

There is a good vertex $b^* \in B$.

Let $b^*$ be such a good vertex. Then, since by the condition in Lemma 4, $B \cap D = \emptyset$, $b^*$ must have a D-neighbor $a^* \in A \cap N(b^*) \cap D$; the algorithm tries all possible vertices in $A \cap N(b^*)$. Let $D(a^*)$ denote an e.d.s. with $a^* \in D(a^*)$; without loss of generality, assume that $a^* \in A_1$. Clearly, $(A_1 \setminus \{a^*\}) \cap D(a^*) = \emptyset$. Without loss of generality, let us assume that $A_1 = \{a^*\}$. Since $a^*$ dominates $b^*$, each neighbor of $b^*$ in $A_i$, $i \ge 2$, is not in $D(a^*)$. For $i \in \{2,\ldots ,k\}$, let $A'_i := A_i \setminus N(b^*)$, and let $A' = \{a^*\} \cup A'_2 \cup \ldots \cup A'_k$. Obviously, we have:

(a):

For each $A'_i$, $|A'_i \cap D(a^*)| = 1$.

Moreover, as before, we can assume:

(b):

For each vertex $b \in B$, b does not have a join to two distinct $A'_i$, $A'_j$, $i \ne j$.

(c):

If vertex $b \in B$ has a join to exactly one $A'_i$ then it does not contact the remaining components $A'_j$, $j \ne i$.

Thus, again by (3) and the subsequent paragraph in Sect. 2, from now on, we can assume that no vertex $b \in B$ has a join to any $A_i$, i.e., if b contacts $A_i$ then it distinguishes $A_i$. Next we claim:

(d):

At most two distinct components $A'_i,A'_j$ are distinguished by some vertex of $B \setminus \{b^*\}$.

Summarizing, by the above, $D(a^*)$ exists if and only if

(i):

the above properties hold and

(ii):

$G[A' \cup B]$ has a (weighted) e.d.s. $D(a^*)$ with $B \cap D(a^*) = \emptyset$.

Checking (i) can be done in polynomial time (actually one should just check if some of the above properties hold). Checking (ii) can be done in polynomial time as shown below: For the components of $G[A']$, let

• $C_{1}(A')$ be the set of those components of $G[A']$ which are not distinguished by any vertex of B, and

• $C_{2}(A')$ be the set of those components of $G[A']$ which are distinguished by some vertex of B.

For each member K of $C_{1}(A')$, any vertex of K (of minimum weight, for WED) can be assumed to be the only vertex in $D(a^*) \cap K$, without loss of generality since such vertices form a clique and have respectively the same neighbors in $G[(A' \cup B) \setminus K]$ (for WED, one can select a vertex of minimum weight).

Concerning $C_{2}(A')$, we have $|C_{2}(A')| \le 2$ by property (d). Then the set $\{(a^*,a_2,\ldots ,a_k) \mid a_i \in A'_i, i \in \{2,\ldots ,k\}\}$ of k-tuples of candidate vertices in $D(a^*)$ contains $\mathcal{O}(n^2)$ members by property (d). Thus one can check in polynomial time if $D(a^*)$ exists.

Algorithm WED for $P_6$ -free unipolar graphs

Given: A connected $P_6$-free unipolar graph $G=(A \cup B,E)$ such that B is a clique and G[A] is the disjoint union of cliques $A_1,\ldots ,A_k$.

Task: Determine an e.d.s. of G with minimum finite weight if there is one or state that G does not have such an e.d.s.

(a):

Reduce G to $G'$ by the Join-Reduction Algorithm. $\{$From now on, we can assume that for every $b \in B$ and every $i \in \{1,\ldots ,k\}$, b distinguishes $A_i$ if b contacts $A_i$.$\}$

(b):

Construct the dag H according to Definition 1 (v), and determine a good vertex $b^* \in B$ in H.

(c):

For every neighbor $a^* \in A'$ of $b^*$, determine the $\mathcal{O}(n^2)$ possible tuples of $D(a^*)$-candidates and check whether they are an e.d.s. of finite weight.

(d):

Finally, choose an e.d.s. of minimum finite weight or state that $G'$ does not have such an e.d.s.

Theorem 1

Algorithm WED for $P_6$-free unipolar graphs is correct and can be done in time $\mathcal{O}(n^3 m)$.

4 The Algorithm for WED on $P_6$-Free Graphs

By combining the principles described above (and in particular by Corollary 1, Lemma 4, and Theorem 1) we obtain:

Algorithm WED for $P_6$ -free graphs

Given: A $P_6$-free graph $G=(V,E)$.

Task: Determine an e.d.s. of G with minimum finite weight if there is one or state that G does not have such an e.d.s.

For every $v \in V$ do

begin

(a):

Determine the distance levels $N_i(v)$, $1 \le i \le 4$.

(b):

For $G_v$ as defined in Sect. 2, with $B=N_2(v)$ and $A=N_3(v) \cup N_4(v)$, reduce $G_v$ to $G'_v$ by the Join-Reduction Algorithm. $\{$From now on, we can assume that for every $b \in B$ and every $i \in \{1,\ldots ,k\}$, b distinguishes $A_i$ if b contacts $A_i$.$\}$

(c):

According to the Component-Reduction Algorithm, determine a vertex $b^* \in B$ contacting every component in G[A] which is not a clique, and for every neighbor $q^* \in N(b^*) \cap A$, do:

(c.1):

Reduce $G'_v$ to $G'(v,q^*)$ by the Component-Reduction Algorithm. $\{$Now, $G'(v,q^*)$ is $P_6$-free unipolar.$\}$

(c.2):

Carry out the Algorithm WED for $P_6$-free unipolar graphs for input $G'(v,q^*)$ with its weight function.

(d):

Finally, for every resulting candidate e.d.s., check whether it is indeed a finite weight e.d.s. of G, choose an e.d.s. of minimum finite weight of G or state that G does not have such an e.d.s.

end

Theorem 2

Algorithm WED for $P_6$-free graphs is correct and can be done in time $\mathcal{O}(n^5 m)$.

5 Conclusion

As mentioned, the direct approach for solving WED on $P_6$-free graphs gives a dichotomy result for the complexity of WED on F-free graphs. In [3], using an approach via $G^2$, it was shown that WED can be solved in polynomial time for $P_6$-free chordal graphs, and a conjecture in [3] says that for $P_6$-free graphs with e.d.s., the square is perfect which would also lead to a polynomial time algorithm for WED on $P_6$-free graphs but anyway, the time bound of our direct approach is better than in the case when the conjecture would be true.