A study on the weighted efficient domination problem for \(C_4\)-free bipartite graphs

1. Introduction

1.1. Preliminaries

For any missing concept or notation let us refer to [10].

Let \(G\) be a finite undirected graph, let \(V(G)\) denote its vertex set with \(|V(G)|=n\), and let \(E(G)\) denote its edge set with \(|E(G)|=m\). For any \(U \subseteq V(G)\), let \(N(U):=\{v \in V(G) \setminus U: v\) is adjacent to some vertex of \(U\}\) denote the neighborhood of \(U\), and let \(N[U]:=N(U) \cup U\) denote the closed neighborhood of \(U\); in particular, if \(U = \{u\}\), then let us simply write \(N(u)\) and \(N[u]\). For any \(U,W \subseteq V(G)\), if every vertex in \(U\) is adjacent (is nonadjacent) to every vertex in \(W\), we denote it by \(U \text{①} W\) (by \(U \text{⓪} W\)); in particular, for \(U=\{u\}\), we simply denote \(U \text{①} W\) (denote \(U \text{⓪} W\)) by \(u \text{①} W\) (by \(u \text{⓪} W\)). For any \(u \in V(G)\) and for any \(W \subseteq V(G)\), with \(u \not \in W\), let us say that \(u\) \(contacts\) \(W\) if \(u\) is adjacent to some vertex of \(W\). For any \(u,v \in V(G)\), \(dist_G(u,v)\) denotes the minimum distance between \(u\) and \(v\) in \(G\), i.e., the minimum length of a path between \(u\) and \(v\) in \(G\); similarly, for any \(v \in V(G)\) and for any \(U \subseteq V(G)\), \(dist_G(U,v) = min\{dist_G(u,v) : u \in U\}\). Furthermore, for any \(u \in V(G)\) and for any natural \(i\), let us write \(N_i(u) = \{v \in V(G): dist_G(u,v) = i\}\); similarly, for any \(U \subseteq V\) and for any natural \(i\), let us write \(N_i(U) = \bigcup_{u \in U} N_i(u) \setminus U\). Finally, for any \(U \subseteq V(G)\), let \(G[U]\) denote the subgraph of \(G\) induced by vertex set \(U\).

For a set \({\cal F}\) of graphs, a graph \(G\) is called \({\cal F}\)-free if \(G\) contains no induced subgraph isomorphic to a member of \({\cal F}\); in particular, we say that \(G\) is \(H\)-free if \(G\) is \(\{H\}\)-free.

For \(h \ge 1\), let \(P_h\) denote the chordless path with \(h\) vertices, and let \(K_h\) denote the complete graph with \(h\) vertices (clearly, \(P_2=K_2\)). For \(h \ge 4\), let \(C_h\) denote the chordless cycle with \(h\) vertices. The girth of a graph \(G\) is the length of a shortest [and thus induced] cycle contained in \(G\). For \(i,j,k \ge 0\), let \(S_{i,j,k}\) denote the tree formed by three chordless paths, namely \(P_{i+1},P_{j+1},P_{k+1}\), which share a unique endpoint. Thus, the claw is \(S_{1,1,1}\), the chair (also called the fork) is \(S_{1,1,2}\), and \(P_k\) is isomorphic to \(S_{0,0,k-1}\). Finally, we denote by \(G + H\) the disjoint union of graphs \(G\) and \(H\), in particular let \(2H\) denote \(H + H\).

1.2. The weighted efficient domination (WED) problem

Let \(G=(V(G),E)\) be a finite undirected graph. A vertex \(v\) dominates itself and its neighbors. A vertex subset \(D \subseteq V(G)\) 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\). Then, for any e.d.s. \(D\) of \(G\), one has \(|D \cap N[v]| = 1\) for every \(v \in V(G)\). The notion of efficient domination was introduced by Biggs [4] under the name perfect code. Note that a graph may have no e.d.s., e.g., a \(C_4\) or a \(C_5\) (in particular, in [28], it is considered the problem to compute the minimum number of vertices in a set \(S\) such that the graph \(G – S\) has an e.d.s.).

Let us mention the following theorem shown in [40]:

Theorem 1.1. [40] If a graph has two or more e.d.s., then all such e.d.s. have the same cardinality.

The Efficient Dominating Set (ED for short) problem can be defined as follows:

\(\bullet\) Given a graph \(G\), check if \(G\) has an e.d.s.

The Weighted Efficient Dominating Set (WED for short) problem can be defined as follows:

\(\bullet\) Given a graph \(G\) and a weight function \(w: V(G) \rightarrow \mathbb{R}\), compute \(D^* \in\) arg min\(\{w(D): D\) is an e.d.s. of \(G\}\), where \(w(D) = \sum\limits_{d \in D}{w(d)}\).

Note that, since a graph may have no e.d.s., the WED problem may have no feasible solution.

In particular, if \(w(v) = 1\) for every \(v \in V(G)\), then the WED problem is the ED problem.

Finally, according to [7], let us point out that, by Theorem 1.1 and since negative weights are allowed, the Weighted Efficient Dominating Set could be equivalently defined with respect to maximum weight (instead of minimum weight).

Let us mention [6] and [27] for a detailed study on this topic. The WED problem is motivated by various applications, including coding theory and resource allocation in parallel computer networks; see e.g [3, 2, 4, 20, 32, 33, 34, 39, 40, 44, 45]. Efficient dominating sets are also called perfect dominating sets and independent perfect dominating sets in various papers.

The Exact Cover problem asks for a subset \({\cal F’}\) of a set family \({\cal F}\) over a ground set, say \(V\), containing every vertex in \(V\) exactly once, i.e., \({\cal F’}\) forms a partition of \(V\). As shown by Karp [29], this problem is NP-complete even for set families containing only \(3\)-element subsets of \(V\) (see problem X3C [SP2] in [25]). Clearly, the ED problem is the Exact Cover problem for the closed neighborhood hypergraph of \(G\), i.e., if \(D=\{d_1,\ldots,d_k\}\) is an e.d.s. of \(G\) then \(N[d_1] \cup \ldots \cup N[d_k]\) forms a partition of \(V(G)\). In [3, 2], it was shown that the ED problem is NP-complete.

A set \(M\) of edges in a graph \(G\) is an efficient edge dominating set (e.e.d.s. for short) of \(G\) if and only if it is an e.d.s. in its line graph \(L(G)\). The Efficient Edge Dominating Set (EED for short) problem asks for the existence of an e.e.d.s. in a given graph G. Thus, the EED problem for a graph G corresponds to the ED problem for its line graph \(L(G)\). Again, note that not every graph has an e.e.d.s. Efficient edge dominating sets are also called dominating induced matchings in some papers (see e.g. [9, 19]). In [26], it was shown that the EED problem is NP-complete; see also [9, 19, 37, 38]. Thus, the ED problem is NP-complete for line graphs. Since line graphs are claw-free, the ED problem is NP-complete for claw-free graphs as well.

Many papers have studied the complexity of the ED problem on special graph classes (see [12, 40] for references). The ED problem remains NP-complete for bipartite graphs [45], \(2P_3\)-free chordal graphs [40, 45], chordal unipolar graphs [23, 45], line graphs of bipartite graphs [38], planar bipartite graphs [39], chordal bipartite graphs [39] (a bipartite graph \(G\) is chordal bipartite if \(G\) is \(C_{2k}\)-free for every \(k \ge 3\). i.e., it is a hole-free bipartite graph), planar graphs with maximum degree at most 3 [24, 30]. Thus, for every \(k \ge 3\), the ED problem is NP-complete for \(C_{2k}\)-free bipartite graphs. Moreover, the ED problem is NP-complete for planar bipartite graphs [39] and even for planar bipartite graphs of maximum degree 3 [12] and girth at least \(g\) for every fixed \(g\) [42]. Thus, the ED problem is NP-complete for \(C_4\)-free bipartite graphs.

A linear forest is the disjoint union of chordless paths, namely, it is a \(C_k\)-free (for any \(k \geq 3\)) and claw-free graph. The NP-completeness of the ED problem for \(2P_3\)-free chordal graphs, for bipartite graphs, and for claw-free graphs mentioned above implies:

Corollary 1.2. For any graph \(F\), different to a \(2P_3\)-free linear forest, the ED problem is NP-complete in the class of \(F\)-free graphs.

Corollary 1.2 motivated the study of the (W)ED problem in the class of \(F\)-free graphs, when \(F\) is a \(2P_3\)-free linear forest. The last remaining open case was the complexity of the ED problem on \(P_6\)-free graphs (see [8]); actually, it was open even for \(P_6\)-free chordal graphs. Lokshtanov, Pilipczuk, and van Leeuwen [35], and independently Brandstädt and Mosca [13], showed that the ED problem is solvable in polynomial time for \(P_6\)-free graphs (the time bound in the direct approach of [13] is \(O(n^5m)\) while in [35], it is more than \(n^{500}\)).

As mentioned above, in [23, 43, 45], it was shown that ED is NP-complete for \(2P_3\)-free chordal unipolar graphs and thus, in general, for \(P_7\)-free graphs. Then, by the above polynomial results on \(P_6\)-free graphs, one obtains a dichotomy.

Furthermore, if the ED problem is solvable in polynomial time for \((P_k + \ell P_2)\)-free graphs, \(\ell \geq 0\), then it is solvable in polynomial time for \((P_k +(\ell +1)P_2)\)-free graphs [8]. Thus, the ED problem is solvable in polynomial time for \((P_6 +\ell P_2)\)-free graphs for every fixed \(\ell \geq 1\). Let us mention that the ED problem is solvable in linear time for \(P_5\)-free graphs [5]. Moreover the ED problem is solvable in polynomial for different subclasses of \(P_7\)-free graphs [11].

However, regardless of Corollary 1.2, the WED problem is solvable in polynomial time for distance-hereditary graphs [39], for AT-free graphs and for dually chordal graphs [7], and for some “comb product graphs” [31].

Let us conclude with a focus on bipartite graphs.

Lu and Tang [39] showed that the ED problem is solvable in linear time for bipartite permutation graphs (which are a subclass of convex bipartite graphs). In [11], it is shown that the ED problem can be solved in polynomial time for interval bipartite graphs (which include convex bipartite graphs, which are a subclass of chordal bipartite graphs). In [1], it is shown that the ED problem can be solved in polynomial time for diameter three bipartite graphs, while the ED problem is NP-complete for graphs of diameter \(d = 3k\) or \(d = 3k+2\) for \(k \geq 1\).

It is well known that for every graph class with bounded clique-width, the ED problem can be solved in polynomial time [21]; for instance, the clique-width of claw-free bipartite, i.e., \(K_{1,3}\)-free bipartite graphs is bounded. Dabrowski and Paulusma [22] published a dichotomy for boundedness of clique-width of \(H\)-free bipartite graphs (see also [36]). For instance, the clique-width of \(S_{1,2,3}\)-free bipartite graphs is bounded (which includes \(K_{1,3}\)-free bipartite graphs).

Since the ED problem remains NP-complete for bipartite graphs, Corollary 1.2 and the above results motivate the study of the (W)ED problem on \(F\)-free bipartite graphs, when \(F\) is not a \(2P_3\)-free linear forest and when \(F\)-free bipartite graphs have unbounded clique width.

In [14], it is shown that the ED problem can be solved in polynomial time for \(P_7\)-free bipartite graphs, for \(\ell P_4\)-free bipartite graphs for fixed \(\ell\), for \(S_{2,2,4}\)-free bipartite graphs as well as for \(P_9\)-free bipartite graphs with degree at most 3. Furthermore the WED problem can be solved in polynomial time for \(S_{1,1,5}\)-free bipartite graphs [15] for \(S_{1,3,3}\)-free bipartite graphs [16], and for \(P_{8}\)-free bipartite graphs [17, 18].

In particular one could consider the following open problems:

What is the complexity of the ED problem for

• \(-\) \(P_k\)-free bipartite graphs, \(k \ge 9\) ?

• \(-\) \(S_{1,3,4}\)-free bipartite graphs ?

• \(-\) \(S_{1,1,6}\)-free bipartite graphs ?

• \(-\) \(S_{1,2,5}\)-free bipartite graphs ?

• \(-\) \(S_{2,2,k}\)-free bipartite graphs for \(k \ge 5\) ?

• \(-\) chordal bipartite graphs with vertex degree at most 3 ?

1.3. This manuscript

This manuscript reports a study on the WED problem for \(C_4\)-free bipartite graphs, as motivated above, recalling that the ED problem remains NP-complete for \(C_4\)-free bipartite graphs.

In detail, this manuscript introduces the following results.

Theorem 1.3. For \((S_{1,2,5},C_4)\)-free bipartite graphs, the WED problem can be solved in \(O(n^{19})\) time.

Theorem 1.4. For \((P_{10},C_4)\)-free bipartite graphs, the WED problem can be solved in \(O(n^6)\) time.

The approach introduced for Theorem 1.4 can be extended for \((P_t,C_4)\)-free bipartite graphs, for \(t \geq 11\), as discussed later.

More generally along this study \(-\) mainly due to the first author \(-\) it turned out that many polynomial results could be introduced by a similar approach.

In particular the WED problem is solvable in polynomial time for the following graph classes:

• \((P_{11},C_4,C_6)\)-free bipartite graphs,

• \((P_{13},C_4,C_6,C_8)\)-free bipartite graphs,

• \((2P_{7},C_4,C_6,C_8)\)-free bipartite graphs,

• \((P_{16},C_4,C_6,C_8,C_{10})\)-free bipartite graphs,

• \((2P_{9},C_4,C_6,C_8,C_{10})\)-free bipartite graphs.

Let us conclude with a result from [42] which could be useful to present this topic.

Consider the following transformation [which recalls that introduced in [41] showing that the Maximum Independent Set problem remains NP-hard for graphs of girth at least \(g\) for every fixed \(g\)]: Let \(G = (V(G), E(G))\) be a graph and let \(G’ = (V(G’),E(G’))\) be the graph obtained from \(G\) by replacing every edge \(xy \in E\) with an induced \(P_5\) of vertices \(x,a,b,c,y\) and edges \(xa,ab,bc,cy\), namely \(x-a-b-c-y\); in particular let us say that \(x-a-b-c-y\) is a \(blue\) path of \(G’\) and that vertices \(a,b,c\) are the \(interior\) vertices of \(x-a-b-c-y\).

Theorem 1.5. [42] Let \(G = (V(G),E(G))\) be any graph and let \(G’ = (V(G’),E(G’))\) be the graph obtained from \(G\) as above. Then \(G\) has an e.d.s. of cardinality \(k\) if and only if \(G’\) has an e.d.s. of cardinality \(k + |E|\).

Proof. First let us assume that \(G\) has an e.d.s. say \(D\) of cardinality \(k\). Then one can define an e.d.s. \(D’\) of \(G’\) as follows with reference to each edge \(xy \in E(G)\) (by definition of e.d.s. for each edge \(xy \in E(G)\) at most one vertex of \(xy\) is in \(D\)):

if \(xy \in E(G)\), \(x \in D\), \(y \not \in D\), then with reference to the blue path \(x-a-b-c-y\) of \(G’\), set \(x,c\) in \(D’\);

if \(xy \in E(G)\), \(x \not \in D\), \(y \not \in D\), then with reference to the blue path \(x-a-b-c-y\) of \(G’\), set \(b\) in \(D’\).

By definition of e.d.s. and by construction one has that \(D’\) is an e.d.s. of \(G’\); in particular, for each blue path \(P\) of \(G’\) there is exactly one interior vertex of \(P\) belonging to \(D’\), so that \(D’\) has cardinality \(k + |E|\).

Then let us assume that \(G’\) has an e.d.s. say \(D’\) of cardinality \(k + |E(G)|\). Note that by definition of e.d.s., for each blue path \(P\) of \(G’\), there is exactly one interior vertex of \(P\) belonging to \(D’\). Then let us observe that:

if \(a \in D’\), \(b,c, \not \in D’\), then by definition of e.d.s. one has \(x \not \in D’\) and \(y \in D’\);

if \(b \in D’\), \(a,c, \not \in D’\), then by definition of e.d.s. one has \(x,y \not \in D’\).

By definition of e.d.s and by construction one has that \(D = D’ \cap V(G)\) is an e.d.s. of \(G\); in particular, for each blue path \(P\) of \(G’\) there is exactly one interior vertex of \(P\) belonging to \(D’\), so that \(D\) has cardinality \(k\). \(\square\)

Notice that, for any graph \(G\), the graph \(G’\) obtained from \(G\) as above is bipartite. Furthermore the above theorem admits a repeated application: in particular it shows that the ED problem remains NP-complete for bipartite graphs of girth at least \(g\) for every fixed \(g\).

2. The WED problem for \((S_{1,2,5},C_4)\)-free bipartite graphs

2.1. Preliminaries

Let \(G= (V(G),E(G)) = (X,Y,E(G))\) be an \((S_{1,2,5},C_4)\)-free bipartite graph.

For any vertex \(u \in V(G)\), we say that \(u\) is forced if \(u \in D\) for every e.d.s. \(D\) of \(G\), and \(u\) is excluded if \(u \notin D\) for every e.d.s. \(D\) of \(G\).

By a forced vertex, \(G\) can be reduced to \(G’\) as follows:

Claim 1. If \(u \in V(G)\) is forced, then \(G\) has an e.d.s. \(D\) with \(u \in D\) if and only if the reduced graph \(G’=G \setminus N[u]\) has an e.d.s. \(D’=D \setminus \{u\}\) such that all vertices in \(N_2(u)\) are excluded in \(G’\).

Analogously, for any vertex \(v \in V(G)\), we say that \(u \in V(G)\) is \(v\)-forced if \(u \in D\) for every e.d.s. \(D\) of \(G\) with \(v \in D\), and \(u\) is \(v\)-excluded if \(u \notin D\) for every e.d.s. \(D\) of \(G\) with \(v \in D\). For checking whether \(G\) has an e.d.s. \(D\) with \(v \in D\), we can clearly reduce \(G\) by forced vertices as well as by \(v\)-forced vertices when we assume that \(v \in D\):

Claim 2. If \(u \in V(G)\) is \(v\)-forced, for a vertex \(v \in V(G)\), then \(G\) has an e.d.s. \(D\) with \(v \in D\) if and only if the reduced graph \(G’=G \setminus N[u]\) has an e.d.s. \(D’=D \setminus \{u\}\) with \(v \in D’\) such that all vertices in \(N_2(u)\) are \(v\)-excluded in \(G’\).

Similarly, for \(k \ge 2\), \(u \in V(G)\) is \((v_1,\ldots,v_k)\)-forced if \(u \in D\) for every e.d.s. \(D\) of \(G\) with \(v_1,\ldots,v_k \in D\), and correspondingly, \(u \in V(G)\) is \((v_1,\ldots,v_k)\)-excluded if \(u \notin D\) for such e.d.s. \(D\), and \(G\) can be reduced by the same principle.

Clearly, for every component of \(G\), the WED problem is independently solvable. Thus, we can assume that \(G\) is connected.

Recall that \(dist_G(u,v)\) denotes the minimum distance, i.e., the minimum length of a path between \(u\) and \(v\) in \(G\). By definition of e.d.s., the distance between two \(D\)-vertices is at least \(3\). Moreover, if \(u,u’ \in D \cap X\) or \(u,u’ \in D \cap Y\) then \(dist_G(u,u’) \ge 4\).

If for an e.d.s. \(D\) in the bipartite graph \(G=(X,Y,E)\), \(|D|=1\), say without loss of generality, \(D =\{x\}\) with \(x \in X\) and \(D \cap Y=\emptyset\), then every \(y \in Y\) must have the \(D\)-neighbor \(x \in D\), i.e., \(x \text{①} Y\) and by the e.d.s. property, \(|X|=1\), i.e., \(X=\{x\}\) (else there is no such e.d.s. in \(G\)), which is a trivial e.d.s. solution.

Now assume that \(|D| \ge 2\), and without loss of generality, \(D \cap X \neq \emptyset\). Since \(G\) is connected, every \(x \in D \cap X\) must have at least distance \(2\) in \(G\), say \((x,y,x’)\) induce a \(P_3\) in \(G\). Then by the e.d.s. property, \(y,x’ \notin D\) and \(x’\) must have a \(D\)-neighbor \(y’ \in D \cap Y\) (else there is no such e.d.s. in \(G\)). Thus, \(D \cap X \neq \emptyset\) and \(D \cap Y \neq \emptyset\).

Then by the above let us formalize the following obseravtion.

Observation 2.1. If \(D\) is an e.d.s. of \(G\), then there is an induced \(P_4\) of \(G\) say \(P\), such that \(D\) contains the two endpoints of \(P\).

2.2. Distance levels

Let us fix an induced \(P_4\) of \(G\), say \(P\) of vertices \(p_1,p_2,p_3,p_4\), and edges \(p_1p_2,p_2p_3,p_3p_4\).

Let us recall the notation \(N_h(\{p_1,p_4\}) = \{v \in V(G): dist(v,\{p_1,p_4\}) = h\}\), for \(h \geq 1\), for the distance levels with respect to \(\{p_1,p_4\}\).

Notation: for brevity let us write \(\{p_1,p_4\} = N_0\) and \(N_h(\{p_1,p_4\}) = N_h\) for \(h \geq 1\).

Notice that \(G[N_0 \cup N_1]\) is connected.

Then let us assume that \(N_0 \subseteq D\), where \(D\) is a (possible) e.d.s. \(D\) of \(G\).

By definition of e.d.s., we have: \[D \cap (N_1 \cup N_2)=\emptyset.\tag{1}\]

If there is a vertex \(x \in N_2\) with \(N(x) \cap N_3=\emptyset\), then \(G\) has no e.d.s. \(D\) with \(N_0 \subseteq D\). Thus, we assume: \[\mbox{ Every vertex } x \in N_2 \mbox{ has a neighbor in } N_3.\tag{2}\]

If there is a vertex \(x \in N_2\) with \(|N(x) \cap N_3|=1\), say \(N(x) \cap N_3=\{y\}\), then \(y\) is \(N_0\)-forced. Then one can update \(N_0:= N_0 \cup \{y\}\) and re-define the distance levels with respect to \(N_0\). Notice that \(G[N_0 \cup N_1]\) is still connected. Thus, we assume: \[\mbox{ Every vertex } x \in N_2 \mbox{ has at least two neighbors in } N_3.\tag{3}\]

If there is a vertex \(y \in N_3\) with \(N(y) \cap N_4=\emptyset\), then \(y\) is \(N_0\)-forced. Then one can update \(N_0:= N_0 \cup \{y\}\) and re-define the distance levels with respect to \(N_0\) as above. Notice that \(G[N_0 \cup N_1]\) is still connected.

Thus, we assume: \[\mbox{ Every vertex } y \in N_3 \mbox{ has a neighbor in } N_4.\tag{4}\]

In particular, we have:

Lemma 2.2. For every \(r_2 \in N_2\), \(r_2\) is no endpoint of a \(P_6\) whose remaining vertices are in \(N_0 \cup N_1\).

Proof. Let \(r_2 \in N_2\) be the endpoint of a \(P_k\) \((r_2,r_1,v_1,\ldots,v_k)\), \(k \ge 1\), with \(r_1 \in N_1\) and \(v_1,\ldots,v_k \in N_0 \cup N_1\). Clearly, \((r_2,r_1,r_0)\) induce a \(P_3\) in \(G\) with \(r_1 \in N_1\) and \(r_0 \in N_0\).

Suppose to the contrary that \(r_2\) is the endpoint of a \(P_6\) \((r_2,r_1,v_1,v_2,v_3,v_4)\) with \(r_1 \in N_1\) and \(v_1,\ldots,v_4 \in N_0 \cup N_1\). By (3), \(r_2\) must have at least two neighbors in \(N_3\), say \(r_2r_3 \in E\), \(r_2r’_3 \in E\) with \(r_3,r’_3 \in N_3\) and without loss of generality, \(r_3 \in D\). By defnition of e.d.s., \(r’_3 \notin D\) and \(r’_3\) must have a \(D\)-neighbor \(s \in D \cap (N_3 \cup N_4)\). But then \((r_2,r_3,r’_3,s,r_1,v_1,v_2,v_3,v_4)\) (with midpoint \(r_2\)) induce an \(S_{1,2,5}\) in \(G\), which is a contradiction.

Thus, \(r_2\) is no endpoint of a \(P_6\) whose remaining vertices are in \(N_0 \cup N_1\), i.e., \(r_2\) is the endpoint of a \(P_5\) \((r_2,r_1,v_1,v_2,v_3)\) with \(r_1 \in N_1\) and \(v_1,v_2,v_3 \in N_0 \cup N_1\) or a \(P_4\) \((r_2,r_1,v_1,v_2)\) with \(r_1 \in N_1\) and \(v_1,v_2 \in N_0 \cup N_1\) or a \(P_3\) \((r_2,r_1,r_0)\) with \(r_1 \in N_1\) and \(r_0 \in N_0\), and Lemma 2.2 is shown. \(\square\)

Lemma 2.3. Every \(r_2 \in N_2\) is no endpoint of a \(P_5\) \(P=(r_2,r_3,r_4,r_5,r_6)\) with \(r_3 \in N_3\), \(r_4 \in N_3 \cup N_4\), \(r_5 \in N_3 \cup N_4 \cup N_5\), \(r_6 \in N_3 \cup N_4 \cup N_5 \cup N_6\), i.e., \(N_6=\emptyset\), \(N_5\) is independent, every edge in \(N_4\) does not contact \(N_5\), and for every edge \(r_3s_3\) in \(N_3\), there is no such \(P_4\) \((r_3,s_3,r_4,r_5)\) with \(r_4 \in N_4\) and \(r_5 \in N_4 \cup N_5\).

Proof. Let \((x,y_1,x_1,y)\) induce a \(P_4\) in \(G[N_0 \cup N_1]\) with \(x,y \in N_0\) and \(y_1,x_1 \in N_1\).

Suppose to the contrary that \(r_2 \in N_2\) is the endpoint of a \(P_5\) \(P=(r_2,r_3,r_4,r_5,r_6)\) with \(r_3 \in N_3\), \(r_4 \in N_3 \cup N_4\), \(r_5 \in N_3 \cup N_4 \cup N_5\), \(r_6 \in N_3 \cup N_4 \cup N_5 \cup N_6\). Without loss of generality, assume that \(r_2 \in N_2 \cap X\).

If \(r_2y_1 \in E\) then \((y_1,x,x_1,y,r_2,r_3,r_4,r_5,r_6)\) (with midpoint \(y_1\)) induce an \(S_{1,2,5}\) in \(G\), which is a contradiction. Thus, \(r_2y_1 \notin E\) and \(r_1r_2 \in E\) with \(r_1 \in N_1\), \(r_1 \neq y_1\).

First assume that \(r_1x \in E\). Since there is no such \(C_4\) \((r_1,x,y_1,x_1)\) in \(G\), \(r_1x_1 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,r_1,x,y_1,x_1,y)\) with \(r_1,x_1,y_1 \in N_1\) and \(x,y \in N_0\), which is a contradiction by Lemma 2.2. Thus, \(r_1x \notin E\), i.e., \(r_0r_1 \in E\) with \(r_0 \in N_0\), \(r_0 \neq x\). If \(r_1x’_1 \in E\) with \(yx’_1 \in E\) (possibly \(x_1=x’_1\)) then \((r_1,r_0,x’_1,y,r_2,r_3,r_4,r_5,r_6)\) (with midpoint \(r_1\)) induce an \(S_{1,2,5}\) in \(G\), which is a contradiction. Thus, \(r_1x’_1 \notin E\), i.e., \(r_1 \text{⓪} N(y)\).

Since \(G[N_0 \cup N_1]\) is connected, \(r_0\) and \(y\) must have distance at least \(3\); without loss of generality, \((r_0,r’_1,x’_1,y)\) induce a \(P_4\) with \(r’_1,x’_1 \in N_1\) (possibly \(x_1=x’_1\) but \(r_1 \neq r’_1\)). Since \(r’_1x’_1 \in E\) then, since there is no such \(C_4\) \((r_0,r_1,r_2,r’_1)\) in \(G\), \(r’_1r_2 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,r_1,r_0,r’_1,x’_1,y)\) with \(r_1,r’_1,x’_1 \in N_1\) and \(r_0,y \in N_0\), which is a contradiction by Lemma 2.2. Thus, \(r’_1x’_1 \notin E\), i.e., \(r’_1 \text{⓪} N(y)\), which is a contradiction.

Thus, \(r_2 \in N_2\) is no endpoint of a \(P_5\) \(P=(r_2,r_3,r_4,r_5,r_6)\) with \(r_3 \in N_3\), \(r_4 \in N_3 \cup N_4\), \(r_5 \in N_3 \cup N_4 \cup N_5\), \(r_6 \in N_3 \cup N_4 \cup N_5 \cup N_6\), i.e., \(N_6=\emptyset\), \(N_5\) is independent, every edge in \(N_4\) does not contact \(N_5\), and for every edge \(r_3s_3\) in \(N_3\), there is no such \(P_4\) \((r_3,s_3,r_4,r_5)\) with \(r_4 \in N_4\), \(r_5 \in N_4 \cup N_5\), and Lemma 2.3 is shown. \(\square\)

Corollary 2.4. For every \(r_2 \in N_2\) and \(r_3 \in D \cap N_3\) with \(r_2r_3 \in E\), \(r_2 \in N_2\) is no endpoint of \(P_4\) \((r_2,r_3,r_4,r_5)\) with \(r_3 \in D \cap N_3\), \(r_4 \in N_3 \cup N_4\), \(r_5 \in N_3 \cup N_4 \cup N_5\).

2.3. When no \(D\)-vertex is midpoint of a \(P_5\) in \(G\)

Let us show that an e.d.s. of \(G\) in arg min\(\{w(D) : D\) is an e.d.s. of \(G\) such that no \(D\)-vertex is midpoint of an induced \(P_5\}\) can be computed in polynomial time.

Let \(D\) denote such a possible e.d.s.

Lemma 2.5. For every \(P_8\) \(P=(x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4)\) in \(G\), \(x_1,x_2,y_2,x_3,y_3,y_4\) are excluded.

Proof. Let \(P=(x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4)\) induce a \(P_8\) in \(G\), and in this subsection, every \(D\)-vertex is no midpoint of a \(P_5\) in \(G\).

Since \(x_2\) is midpoint of a \(P_5\) \((x_1,y_1,x_2,y_2,x_3)\) in \(G\), \(x_2 \notin D\). Analogously, since \(y_2\) is midpoint of a \(P_5\) \((y_1,x_2,y_2,x_3,y_3)\) in \(G\), \(y_2 \notin D\), since \(x_3\) is midpoint of a \(P_5\) \((x_2,y_2,x_3,y_3,x_3)\) in \(G\), \(x_3 \notin D\), and since \(y_3\) is midpoint of a \(P_5\) \((y_2,x_3,y_3,x_4,y_4)\) in \(G\), \(y_3 \notin D\), i.e., \(x_2,y_2,x_3,y_3\) are excluded.

Finally suppose to the contrary that either \(x_1 \in D\) or \(y_4 \in D\); without loss of generality, assume that \(x_1 \in D\); recall that \(x_2,y_2\) are excluded. Then by definition of e.d.s., \(y_1,x_2 \notin D\) and \(x_2\) must have a \(D\)-neighbor \(y \in D\) with \(x_2y \in E\), \(y \neq y_1,y_2\). Clearly, by the e.d.s. property, \(x_1y \notin E\). Since in this subsection, \(y\) is no midpoint of a \(P_5\) in \(G\), \(yx_3 \notin E\) and \(yx_4 \notin E\) (else \(y \in D\) is midpoint of a \(P_5\) \((y_1,x_2,y,x_3,y_3)\) or \((y_1,x_2,y,x_4,y_4)\)).

But then \((x_2,y,y_1,x_1,y_2,x_3,y_3,x_4,y_4)\) (with midpoint \(x_2\)) induce an \(S_{1,2,5}\) in \(G\), which is a contradiction. Thus, \(x_1 \notin D\). Analogously, \(y_4 \notin D\), i.e., \(x_1,y_4\) are excluded, and Lemma 2.5 is shown. \(\square\)

Lemma 2.6. For every \(P_8\) \(P=(x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4)\) in \(G\), there are exactly two \(D\)-vertices \(y_1 \in D\) and \(x_4 \in D\) in \(P\) which are forced.

Proof. Let \(P=(x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4)\) induce a \(P_8\) in \(G\), and in this subsection, every \(D\)-vertex is no midpoint of a \(P_5\) in \(G\). Recall that by Lemma 2.5, \(x_1,x_2,y_2,x_3,y_3,y_4\) are excluded.

Suppose to the contrary that either \(y_1 \notin D\) or \(x_4 \notin D\); without loss of generality, assume that \(y_1 \notin D\). By Lemma 2.5, \(x_1,x_2 \notin D\) and \(y_1\) must have a \(D\)-neighbor \(x \in D\) with \(xy_1 \in E\), \(x \neq x_1,x_2\). Moreover, by the e.d.s. property, \(x_1\) must have a \(D\)-neighbor \(y \in D\) with \(x_1y \in E\).

Since in this subsection, \(x,y \in D\) are no midpoints of a \(P_5\) in \(G\), \(xy_2 \notin E\), \(xy_3 \notin E\), and \(xy_4 \notin E\) (else \(x \in D\) is midpoint of a \(P_5\) \((x_1,y_1,x,y_2,x_3)\) or \((x_1,y_1,x,y_3,x_4)\) or \((x_1,y_1,x,y_4,x_4)\)), as well as \(yx_3 \notin E\) and \(yx_4 \notin E\) (else \(y \in D\) is midpoint of a \(P_5\) \((y_1,x_1,y,x_3,y_3)\) or \((y_1,x_1,y,x_4,y_4)\)).

Since there is no such \(C_4\) \((y,x_1,y_1,x_2)\) in \(G\), we have \(yx_2 \notin E\). But then \((y_1,x,x_1,y,x_2,\\y_2,x_3,y_3,x_4)\) (with midpoint \(y_1\)) induce an \(S_{1,2,5}\) in \(G\), which is a contradiction. Thus, \(y_1 \in D\) is forced.

Analogously, \(x_4 \in D\) is forced, i.e., \(y_1,x_4\) are forced, and Lemma 2.6 is shown. \(\square\)

Summarizing one can proceed as follows. Set \(Y:= \emptyset\); then, for each induced \(P_8\) \(P=(x_1,y_1,\ldots,x_4,y_4)\) of \(G\), set \(Y:= Y \cup \{y_1,x_4\}\). Thus by Lemma 2.6 and by construction, all vertices in \(Y\) are forced, and \(G[V(G) \setminus Y]\) is \(P_8\)-free. Then by Claim 1, the problem is reduced to [the connected components of] \(G[V(G) \setminus N[Y]]\), with the assumption that vertices in \(N_2(Y)\) are excluded; that can be done in polynomial time, since WED is solvable in polynomial time for \(P_8\)-free bipartite graphs [17, 18]; in particular, the WED problem for \((P_8,C_4)\)-free bipartite graphs can be solved in \(O(n^3)\) time, by Corollary 8 introduced in the next section concerning the WED problem in \((P_{10},C_4)\)-free bipartite graphs; thus the running time bound of the above procedure can be estimated as \(O(n^{8} \cdot n^3)\) time.

Thus, in this subsection, the WED problem can be solved in polynomial time.

2.4. When \(D\)-vertices are midpoints of a \(P_5\) in \(G\)

Let us show that an e.d.s. of \(G\) in arg min\(\{w(D) : D\) is an e.d.s. of \(G\) such that some \(D\)-vertex is midpoint of an induced \(P_5\}\) can be computed in polynomial time.

Let \(D\) denote such a possible e.d.s.

Now assume that there is at least one \(D\)-vertex which is midpoint of an induced \(P_5\) in \(G\), say \((u_1,v_1,u,v_2,u_2)\), with midpoint \(u \in D\). Then by definition of e.d.s., \(u_1,u_2 \notin D\) and \(u_1,u_2\) must have \(D\)-neighbors in \(G\).

Thus, we can assume that:

— either \((v,u_1,v_1,u,v_2,u_2)\) induce a \(C_6\), with \(u,v \in D\), which we denote as \(2D-C_6\); in this case one can set \(N_0 := \{u,v\}\);

— or \((v,u_1,v_1,u,v_2,u_2,v’)\) induce a \(P_7\), with \(u,v,v’ \in D\), which we denote as \(3D-P_7\); in this case one can set \(N_0 := \{u,v,v’\}\).

In other words there is either a \(2D-C_6\) in \(G[N_0 \cup N_1]\) or a \(3D-P_7\) in \(G[N_0 \cup N_1]\).

Then the problem is to compute an e.d.s. \(D\) [of minimum weight] of \(G\), such that \(N_0 \subseteq D\), according to the above two cases.

Notice that in both cases one has:

\[G[N_0 \cup N_1] \mbox{ is connected}.\tag{5}\]

2.4.1. When there is a \(2D-C_6\) in \(G[N_0 \cup N_1]\)

Let \(C=(x,y_1,x_1,y,x’_1,y’_1)\) induce a \(2D-C_6\) in \(G[N_0 \cup N_1]\) with \(x,y \in N_0\), \(x_1,x’_1,y_1,y’_1 \in N_1\). Then for every \(D\)-vertex in \(D \cap N_3\) which is \((x,y)\)-forced, it can be in \(N_0\).

Lemma 2.7. For every \(2D-C_6\) in \(G[N_0 \cup N_1]\), \(N_2 = \emptyset\).

Proof. Let \(C=(x,y_1,x_1,y,x’_1,y’_1)\) induce a \(2D-C_6\) in \(G[N_0 \cup N_1]\) with \(x,y \in N_0\), \(x_1,x’_1,y_1,y’_1 \in N_1\).

Suppose to the contrary that \(N_2 \neq \emptyset\).

First assume that \(r_2 \in N_2\) contacts \(2D-C_6\) \(C \in G[N_0 \cup N_1]\); without loss of generality, \(r_2 \in N_2 \cap X\). By (1), \(r_2 \notin D\) and \(r_2\) must have a \(D\)-neighbor in \(N_3\). By (3), \(r_2\) must have two neighbors \(r_3,r’_3 \in N_3\), say \(r_3 \in D \cap N_3\), and by the e.d.s. property, \(r’_3 \notin D\) and \(r’_3\) must have a \(D\)-neighbor \(s \in D \cap (N_3 \cup N_4)\).

If \(y_1r_2 \in E\) then, since there is no such \(C_4\) \((r_2,y_1,x,y’_1)\) in \(G\), \(y’_1r_2 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,y_1,x_1,y,x’_1,y’_1)\) with \(x_1,y_1,x’_1,y’_1 \in N_1\) and \(y \in N_0\), which is a contradiction by Lemma 2.2. Thus, \(y_1r_2 \notin E\). Moreover, if \(y’_1r_2 \in E\) then, since there is no such \(C_4\) \((r_2,y_1,x,y’_1)\) in \(G\), \(y_1r_2 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,y’_1,x’_1,y,x_1,y_1)\) with \(x_1,y_1,x’_1,y’_1 \in N_1\) and \(y \in N_0\), which is a contradiction by Lemma 2.2. Thus, \(y’_1r_2 \notin E\).

If \(vr_2 \in E\) with \(xv \in E\), \(v \neq y_1,y’_1\), then, since there is no such \(C_4\) \((v,x,y_1,x_1)\) in \(G\), \(vx_1 \notin E\) and since there is no such \(C_4\) \((v,x,y’_1,x’_1)\) in \(G\), \(vx’_1 \notin E\).

But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,v,x,y_1,x_1,y)\) with \(v,x_1,y_1 \in N_1\) and \(x,y \in N_0\), which is a contradiction by Lemma 2.2.

Thus, \(r_2 \text{⓪} N(x)\), say \(r_1r_2 \in E\) with \(r_1 \in N_1\), \(r_1x \notin E\). Analogously, for \(r_2 \in N_2 \cap Y\), \(r_2 \text{⓪} N(y)\), say \(r_1r_2 \in E\) with \(r_1 \in N_1\), \(r_1y \notin E\). Without loss of generality, \(r_2 \in N_2 \cap X\). Then \(r_1 \in N_1 \cap Y\) and \(r_1x \notin E\), say \(r_0r_1 \in E\) with \(r_0 \in N_0\), \(r_0 \neq x\).

If \(r_1x_1 \in E\) then \(r_2\) is the endpoint of a \(P_6\) \((r_2,r_1,x_1,y_1,x,y’_1)\) with \(r_1,x_1,y_1,y’_1 \in N_1\) and \(x \in N_0\), which is a contradiction by Lemma 2.2. Thus, \(r_1x_1 \notin E\) and analogously, \(r_1x’_1 \notin E\).

If \(r_1u \in E\) with \(yu \in E\), \(u \neq x_1,x’_1\), then, since there is no such \(C_4\) \((u,y,x_1,y_1)\) in \(G\), \(uy_1 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,r_1,u,y,x_1,y_1)\) with \(r_1,u,x_1,y_1 \in N_1\) and \(y \in N_0\), which is a contradiction by Lemma 2.2. Thus, \(r_1 \text{⓪} N(y)\).

Assume that \(dist_G(y,r_0)=3\), say \((r_0,r’_1,u,y)\) induce a \(P_4\) in \(G\) (possibly \(u=x_1\) or \(u=x’_1\)). Since there is no such \(C_4\) \((r_0,r_1,r_2,r’_1)\) in \(G\), \(r’_1r_2 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,r_1,r_0,r’_1,u,y)\) with \(r_1,r’_1,u \in N_1\) and \(r_0,y \in N_0\), which is a contradiction by Lemma 2.2. Thus, \(N_2 \cap X=\emptyset\). Analogously, if there is an \(r_2 \in N_2 \cap Y\) then there is a contradiction, and \(N_2 \cap Y=\emptyset\).

Thus, \(N_2=\emptyset\), and Lemma 2.7 is shown. \(\square\)

Then for every \(2D-C_6\) in \(G[N_0 \cup N_1]\), it can be done in polynomial time. The running time bound can be estimated as \(O(n^6)\) time. Now assume that there are no such \(2D-C_6\)’s in \(G\).

2.4.2. When there is no \(2D-C_6\) in \(G[N_0 \cup N_1]\) but a \(3D-P_7\) in \(G[N_0 \cup N_1]\)

Lemma 2.8. For \(3D-P_7\) in \(G[N_0 \cup N_1]\): if the midpoint is in \(N_0 \cap X\), then \(N_2 \cap X = \emptyset\); if the midpoint is in \(N_0 \cap Y\), then \(N_2 \cap Y = \emptyset\).

Proof. Without loss of generality, let \((x_1,y_1,x_2,y_2,x_3,y_3,x_4)\) induce a \(3D-P_7\) in \(G[N_0 \cup N_1]\) with midpoint \(y_2 \in N_0 \cap Y\), and with \(x_1,x_4 \in N_0\), \(y_1,x_2,x_3,y_3 \in N_1\).

Suppose to the contrary that \(N_2 \cap Y \neq \emptyset\).

First assume that \(r_2 \in N_2 \cap Y\) contacts \(N(y_2)\). If \(r_2x_2 \in E\) then, since there is no such \(C_4\) \((r_2,x_2,y_2,x_3)\) in \(G\), \(r_2x_3 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,x_2,y_2,x_3,y_3,x_4)\), which is a contradiction by Lemma 2.2. Thus, \(r_2x_2 \notin E\).

If \(r_2x_3 \in E\) then, since there is no such \(C_4\) \((r_2,x_2,y_2,x_3)\) in \(G\), \(r_2x_2 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,x_3,y_2,x_2,y_1,x_1)\), which is a contradiction by Lemma 2.2. Thus, \(r_2x_3 \notin E\).

If \(r_2u \in E\) with \(y_2u \in E\), \(u \neq x_2,x_3\), then, since there is no such \(C_4\) \((r_2,u,y_2,x_2)\) in \(G\), \(r_2x_2 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,u,y_2,x_2,y_1,x_1)\), which is a contradiction by Lemma 2.2. Thus, \(r_2 \in N_2 \cap Y\) does not contact \(N(y_2)\), i.e., \(r_2 \text{⓪} N(y_2)\), say \(r_1r_2 \in E\) with \(r_1 \in N_1 \cap X\), \(r_1y_2 \notin E\).

If \(r_1y_1 \in E\) then \(r_2\) is the endpoint of a \(P_6\) \((r_2,r_1,y_1,x_2,y_2,x_3)\), which is a contradiction by Lemma 2.2. Thus, \(r_1y_1 \notin E\) and analogously, \(r_1y_3 \notin E\).

If \(r_1v \in E\) with \(x_1v \in E\), \(v \neq y_1\), then, since there is no such \(C_4\) \((v,x_1,y_1,x_2)\) in \(G\), \(vx_2 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,r_1,v,x_1,y_1,x_2)\), which is a contradiction by Lemma 2.2. Thus, \(r_1\) does not contact \(N(x_1)\) and analogously, \(r_1\) does not contact \(N(x_4)\), i.e., \(r_1 \text{⓪} N(x_1) \cup N(x_4)\).

Let \(r_0r_1 \in E\) with \(r_0 \in N_0\), \(r_0 \neq y_2\). Assume that \(G[N_0 \cup N_1]\) is connected; without loss of generality, \(dist_G(x_1,r_0)=3\), say \((x_1,v,r’_1,r_0)\) induce a \(P_4\) in \(G\), \(r’_1 \neq r_1\). Since there is no such \(C_4\) \((r_0,r_1,r_2,r’_1)\) in \(G\), \(r’_1r_2 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,r_1,r_0,r’_1,v,x_1)\), which is a contradiction by Lemma 2.2. Thus, there is no such distance between \(x_1\) and \(r_0\), and analogously, there is no such distance between \(x_4\) and \(r_0\).

Thus, for midpoint \(y_2 \in N_0 \cap Y\), \(N_2 \cap Y = \emptyset\). Analogously, if \((y_1,x_1,y_2,x_2,y_3,x_3,y_4)\) induce a \(3D-P_7\) in \(G[N_0 \cup N_1]\) with midpoint \(x_2 \in N_0 \cap X\), \(N_2 \cap X = \emptyset\), and Lemma 2.8 is shown. \(\square\)

Corollary 2.9. For \(3D-P_7\) in \(G[N_0 \cup N_1]\) with midpoint in \(N_0 \cap Y\), \(N_3 \cap X = \emptyset\), \(N_4 \cap Y = \emptyset\), \(N_5 \cap X = \emptyset\), i.e., \(N_3,N_4,N_5\) are independent.

Corollary 2.10. For \(3D-P_7\) in \(G[N_0 \cup N_1]\) with midpoint in \(N_0 \cap X\), \(N_3 \cap Y = \emptyset\), \(N_4 \cap X = \emptyset\), \(N_5 \cap Y = \emptyset\), i.e., \(N_3,N_4,N_5\) are independent.

Corollary 2.11. For two \(3D-P_7\)’s in \(G[N_0 \cup N_1]\) with midpoints in \(N_0 \cap X\) and in \(N_0 \cap Y\), \(N_2 = \emptyset\).

Lemma 2.12. For \(3D-P_7\) \((x_1,y_1,x_2,y_2,x_3,y_3,x_4)\) in \(G[N_0 \cup N_1]\), if the midpoint \(y_2 \in N_0 \cap Y\), then for \(r_2 \in N_2 \cap X\), \(r_2y_1 \in E\) and \(r_2y_3 \in E\).

Proof. Let \((x_1,y_1,x_2,y_2,x_3,y_3,x_4)\) induce a \(3D-P_7\) in \(G[N_0 \cup N_1]\) with midpoint \(y_2 \in N_0 \cap Y\), and with \(x_1,x_4 \in N_0\), \(y_1,x_2,x_3,y_3 \in N_1\).

Suppose to the contrary that for \(r_2 \in N_2 \cap X\), \(r_2y_1 \notin E\) or \(r_2y_3 \notin E\); without loss of generality, \(r_2y_1 \notin E\).

If \(r_2y_3 \in E\) then \(r_2\) is the endpoint of a \(P_6\) \((r_2,y_3,x_3,y_2,x_2,y_1)\), which is a contradiction by Lemma 2.2. Thus, \(r_2y_3 \notin E\), say \(r_1r_2 \in E\) with \(r_1 \in N_1\), \(r_1 \neq y_1,y_3\).

If \(r_1x_1 \in E\) then, since there is no such \(C_4\) \((r_1,x_1,y_1,x_2)\) in \(G\), \(r_1x_2 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,r_1,x_1,y_1,x_2,y_2)\), which is a contradiction by Lemma 2.2. Thus, \(r_1x_1 \notin E\), and analogously, \(r_1x_4 \notin E\), say \(r_0r_1 \in E\) with \(r_0 \in N_0\), \(r_0 \neq x_1,x_4\).

If \(r_1x_2 \in E\) then, since there is no such \(C_4\) \((r_1,x_2,y_2,x_3)\) in \(G\), \(r_1x_3 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,r_1,x_2,y_2,x_3,y_3)\), which is a contradiction by Lemma 2.2. Thus, \(r_1x_2 \notin E\) and analogously, \(r_1x_3 \notin E\). If \(r_1u \in E\) with \(y_2u \in E\), \(u \neq x_2,x_3\), then, since there is no such \(C_4\) \((u,y_2,x_2,y_1)\) in \(G\), \(uy_1 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,r_1,u,y_2,x_2,y_1)\), which is a contradiction by Lemma 2.2. Thus, \(r_1u \notin E\), i.e., \(r_1 \text{⓪} N(y_2)\).

Assume that \(dist_G(r_0,y_2)=3\), say \((r_0,r’_1,u,y_2)\) with \(r’_1 \neq r_1\) (possibly \(u=x_2\) or \(u=x_3\)). Since there is no such \(C_4\) \((r_2,r_1,r_0,r’_1)\) in \(G\), \(r’_1r_2 \notin E\). But then \(r_2\) is the endpoint of a \(P_6\) \((r_2,r_1,r_0,r’_1,u,y_2)\), which is a contradiction by Lemma 2.2.

Thus, \(r_2y_1 \in E\). Analogously, \(r_2y_3 \in E\), and Lemma 2.12 is shown. \(\square\)

Corollary 2.13. For \(3D-P_7\) \((y_1,x_1,y_2,x_2,y_3,x_3,y_4)\) in \(G[N_0 \cup N_1]\), if the midpoint \(x_2 \in N_0 \cap X\), then for \(r_2 \in N_2 \cap Y\), \(r_2x_1 \in E\) and \(r_2x_3 \in E\).

Corollary 2.14. For \(3D-P_7\) in \(G[N_0 \cup N_1]\), if the midpoint is in \(N_0 \cap Y\), then \(|N_2 \cap X|=1\). Analogously, for \(3D-P_7\) in \(G[N_0 \cup N_1]\), if the midpoint is in \(N_0 \cap X\), then \(|N_2 \cap Y|=1\).

Proof. Without loss of generality, let \((x_1,y_1,x_2,y_2,x_3,y_3,x_4)\) induce a \(3D-P_7\) in \(G[N_0 \cup N_1]\) with midpoint \(y_2 \in N_0 \cap Y\), and with \(x_1,x_4 \in N_0\), \(y_1,x_2,x_3,y_3 \in N_1\). Then by Lemma 2.12, for \(r_2 \in N_2 \cap X\), \(r_2y_1 \in E\) and \(r_2y_3 \in E\).

Suppose to the contrary that \(|N_2 \cap X| \ge 2\), say \(r_2,s_2 \in N_2 \cap X\) with \(r_2 \neq s_2\). Then by Lemma 2.12, also \(s_2y_1 \in E\) and \(s_2y_3 \in E\). But then there is a \(C_4\) \((y_1,r_2,y_3,s_2)\) in \(G\), which is a contradiction. Thus, \(|N_2 \cap X|=1\), and analogously, for \(3D-P_7\) in \(G[N_0 \cup N_1]\) with midpoint in \(N_0 \cap X\), \(|N_2 \cap Y|=1\). \(\square\)

Then by the above: \(|N_2| = 1\), \(N_i\) is independent for \(i = 3,4,5\). On the other hand by Lemma 2.3: \(N_6=\emptyset\), \(N_5\) is independent, every edge in \(N_4\) does not contact \(N_5\), and for every edge \(r_3s_3\) in \(N_3\), there is no such \(P_4\) \((r_3,s_3,r_4,r_5)\) with \(r_4 \in N_4\) and \(r_5 \in N_4 \cup N_5\). It follows that there is only one \(D\)-vertex in \(N_3\), and there is no such \(D\)-vertex in \(N_3\) with midpoint \(P_5\). Moreover, there is no such \(D\)-vertex in \(N_4\) with midpoint \(P_5\), and there is no such \(D\)-vertex in \(N_5\) with midpoint \(P_5\).

Then one can split the problem in \(|N_3|\) instances, one instance for each \(r_3 \in N_3\) with \(r_3\) fixed in \(D\), of the WED problem for \(G[N_3 \cup N_4 \cup N_5]\) by referring to the case when no \(D\)-vertex is midpoint of a \(P_5\) in \(G\). That can be done in polynomial time. Since the above procedure is repeated for each induced \(P_7\) of \(G\), according to Subsection 2.3, the running time bound can be estimated as \(O(n^7 \cdot n \cdot n^{11})\) time.

Thus, in this subsection, the WED problem can be solved in polynomial time.

Thus, Theorem 1.3 is shown.

3. The WED problem for \((P_{10},C_4)\)-free bipartite graphs

3.1. Preliminary

Let \(G = (V(G),E(G)\) be a graph, with \(|V(G)| = n\) and \(|E| = m\).

Notation: For any subset \(C \subseteq V(G)\) let us write:

\({\cal F}_C = \{(C’,{\cal D}(C’)) : C \subseteq C’ \subseteq C \cup N(C)\); \({\cal D}(C’)\) is the family of e.d.s. \(D’\) of \(G[C’]\) such that \(C’ \setminus C \subseteq D’\) and \({\cal D}(C’)\) is non-empty\(\}\).

In other words: for any possible e.d.s. \(D\) of \(G\), some vertices of \(D\) should dominate vertices of \(C\), in particular \(D \cap C\) may be non-empty; that defines a local vertex set \(C’\) which is formed by vertices of \(C\) and by those vertices of \(D \setminus C\) which dominate some vertex of \(C\); then \({\cal F}_C\) collects all such possible local vertex sets \(C’\).

Observation 3.1. Let \(G\) be a graph. For any subset \(C \subseteq V(G)\), such that \(|C| \leq t\) for some \(t \in \mathbb{N}\), the following statements hold:

• (i) for any \((C’,{\cal D}(C’)) \in {\cal F}_C\), one has \(|C’ \setminus C| \leq t\);

• (ii) family \({\cal F}_C\) contains \(O(n^{t})\) members;

• (iii) for any \((C’,{\cal D}(C’)) \in {\cal F}_C\), family \({\cal D}(C’)\) contains at most \(2^t\) members;

• (iv) if \(G\) has an e.d.s. say \(D\), then there is a member \((C’,{\cal D}(C’)) \in {\cal F}_C\), such that \(D \cap C’ = D’\) for some \(D’ \in {\cal D}(C’)\).

Proof. Statement (i) follows since \(|C| \leq t\) and by definition of e.d.s. Statement (ii) follows by statement (i) and by construction; in fact, for each \((C’,{\cal D}(C’)) \in {\cal F}_C\), \(C’ \setminus C\) is a subset of \(V(G) \setminus C\) of at most \(t\) elements. Statement (iii) follows by statement (i) and by construction; in fact, for each \((C’,{\cal D}(C’)) \in {\cal F}_C\), \(C’ \setminus C\) if fixed in the possible e.d.s. \(D’\) of \(G[C’]\) while the other possible elements of \(D’\) are a subset of \(C\). Statement (iv) follows by construction and by definition of e.d.s. \(\square\)

Then let us report the following result.

Theorem 3.2. [44, 45] The WED problem can be solved for trees in \(O(n+m)\) time.

Notation: Let us denote any rooted tree, with root say \(a\), as \(T(a)\); furthermore let us denote as \(T_j(a)\) the set of nodes of \(T(a)\) at distance \(j\) from node \(a\) (for \(j = 1,2, \ldots\)).

3.2. The solution method

Let us show that the WED problem can be solved for (\(P_{10},C_4\))-free bipartite graphs in polynomial time.

Since the WED problem can be solved for trees in \(O(n+m)\) time, by Theorem 3.2, and since a tree can recognized in \(O(n+m)\) time, let us just show that the WED problem can be solved for (\(P_{10},C_4\))-free bipartite graphs which are not trees in polynomial time.

For any bipartite graph \(G = (V(G),E(G))\), let us write \(V(G) = V_1(G) \cup V_2(G)\), where \(V_1(G)\) and \(V_2(G)\) are the two sides of \(G\) [i.e. they are independent sets].

Let us introduce the following algorithm to solve the WED problem for \((P_{10},C_4)\)-free bipartite graphs which are not trees.

Algorithm WED-P10

Input: a connected (\(P_{10},C_4\))-free bipartite graph \(G\) which is not a tree.

Output: an e.d.s. of \(G\) of minimum weight or a proof that \(G\) has no e.d.s.

begin

:: set \(D^* := \emptyset\) and set \(w(D^*) := \infty\);

:: for \(k = 6, 8, 10\), do

:: begin

:: :: if \(G\) contains some induced \(C_k\), then:

:: :: :: (\(k\).1) take \(any\) such induced \(C_k\)’s, say, of vertex-set \(C\);

:: :: :: (\(k\).2) compute family \({\cal F}_C\) [according to Observation 3.1];

:: :: :: (\(k\).3) for each member (\(C’,{\cal D}(C’)\)) of \({\cal F}_C\) do

:: :: :: :: (\(k\).3.1) for each e.d.s. \(D’ \in {\cal D}(C’)\) do

:: :: :: :: begin

:: :: :: :: :: (\(k\).3.1.1) compute \(D^{**} \in\) arg min\(\{w(D) : D\) is an e.d.s. of \(G\), with \(D \cap C’ = D’\}\);

:: :: :: :: :: (\(k\).3.1.2) if such an e.d.s \(D^{**}\) exists and if \(w(D^{**}) < w(D^*)\), then set \(D^* := D^{**}\);

:: :: :: :: end

:: :: :: (\(k\).4) if \(D^* = \emptyset\), then return “\(G\) has no e.d.s.”, and STOP;

:: :: :: (\(k\).5) if \(D^* \neq \emptyset\), then return \(D^*\), and STOP;

:: end

end.

Lemma 3.3. Algorithm WED-P10 is correct. Furthermore Algorithm WED-P10 can be executed in max\(\{O(n^3 \cdot T_6) , O(n^{3} \cdot T_8) , O(n^{3} \cdot T_{10})\}\) time, where \(O(T_k)\) is the running time bound of step (\(k\).3.1.1) for \(k = 6,8,10\); thus, it can be executed in polynomial time, provided that step (6.3.1.1), step (8.3.1.1), and step (10.3.1.1) can be executed in polynomial time.

Proof. As a preliminary let us remark that, since \(G\) is (\(P_{10},C_4\))-free bipartite, the only possible induced cycles in \(G\) are \(C_6\)’s, \(C_8\)’s, \(C_{10}\)’s.

Let us show that Algorithm WED-P10 is correct, by the following exhaustive cases.

Case 1. \(G\) has an e.d.s., say \(D^*\), of minimum weight.

By Observation 3.1-(iv), for \(any\) subset \(C \subseteq V(G)\) [with \(|C| \leq t\) for some \(t \in \mathbb{N}\)], there is a member \((C’,{\cal D}(C’)) \in {\cal F}_C\), such that \(D^* \cap C’ = D’\) for some \(D’ \in {\cal D}(C’)\).

If \(G\) contains some induced \(C_6\)’s, then for \(any\) such induced \(C_6\)’s, say, of vertex-set \(C\), there is a member \((C’,{\cal D}(C’)) \in {\cal F}_C\), such that \(D \cap C’ = D’\) for some \(D’ \in {\cal D}(C’)\): in this case, \(D^*\) [or another e.d.s. of the same weight] will be detected at the corresponding step (\(6\).3.1.1), and then \(D^*\) [or another e.d.s. of the same weight] will be fixed at the corresponding step (\(6\).3.1.2); finally \(D^*\) [or another e.d.s. of the same weight] will be returned at step (6.5), since at steps (\(6\).3.1.1) the algorithm detects just certain e.d.s. of \(G\) (if one), and at steps (\(6\).3.1.2) the algorithm possibly updates the current optimal solution with respect to these certain e.d.s. of \(G\).

If \(G\) is \(C_6\)-free and contains some induced \(C_8\)’s, then for \(any\) such induced \(C_8\)’s, say, of vertex-set \(C\), there is a member \((C’,{\cal D}(C’)) \in {\cal F}_C\), such that \(D^* \cap C’ = D’\) for some \(D’ \in {\cal D}(C’)\): in this case, \(D^*\) [or another e.d.s. of the same weight] will be detected at the corresponding step (\(8\).3.1.1), and then \(D^*\) [or another e.d.s. of the same weight] will be fixed at the corresponding step (\(8\).3.1.2); finally \(D^*\) [or another e.d.s. of the same weight] will be returned at step (8.5), since at steps (\(8\).3.1.1) the algorithm detects just certain e.d.s. of \(G\) (if one), and at steps (\(8\).3.1.2) the algorithm possibly updates the current optimal solution with respect to these certain e.d.s. of \(G\).

If \(G\) is \((C_6,C_8)\)-free and contains some induced \(C_{10}\)’s, then for \(any\) such induced \(C_{10}\)’s, say, of vertex-set \(C\), there is a member \((C’,{\cal D}(C’)) \in {\cal F}_C\), such that \(D^* \cap C’ = D’\) for some \(D’ \in {\cal D}(C’)\): in this case, \(D^*\) [or another e.d.s. of the same weight] will be detected at the corresponding step (\(10\).3.1.1), and then \(D^*\) [or another e.d.s. of the same weight] will be fixed at the corresponding step (\(10\).3.1.2); finally \(D^*\) [or another e.d.s. of the same weight] will be returned at step (10.5), since at steps (\(10\).3.1.1) the algorithm detects just certain e.d.s. of \(G\) (if one), and at steps (\(10\).3.1.2) the algorithm possibly updates the current optimal solution with respect to these certain e.d.s. of \(G\).

No other case is possible, since \(G\) is (\(P_{10},C_4\))-bipartite and is not a tree.

Therefore, in Case 1, the algorithm is correct.

Case 2. \(G\) has no e.d.s.

Algorithm WED-P10 starts by setting \(D^* = \emptyset\) and by setting \(w(D^*) = \infty\). Then, at step (\(k\).4), the algorithm returns “\(G\) has no e.d.s.”, provided that \(D^* = \emptyset\). As shown for Case 1, if \(G\) should have an e.d.s., then \(D^*\) would be updated [with \(D^* \neq \emptyset\)] at some step (\(k\).3.1.1), for some \(k \in \{6,8,10\}\).

Therefore, in Case 2, the algorithm is correct.

Now let us focus on the computational complexity of Algorithm WED-P10.

First let us observe that: step (8.3.1.1) is executed only if \(G\) is \(C_6\)-free; step (10.3.1.1) is executed only if \(G\) is (\(C_6,C_8\))-free.

For \(k \in \{6,8,10\}\): step (\(k\).1) can be executed in \(O(nm)\) time (in fact e.g., for \(k = 6\), \(G\) has an induced \(C_6\) if and only if for some vertex \(v\) of \(G\) there is a vertex \(y \in N_3(v)\) with two neighbors in \(N_2(v)\)); step (\(k\).2) can be executed in \(O(n^k)\) time [according to Observation 3.1-(i)]: in fact, one should consider just subsets \(U\) of \(N(C)\) of cardinality at most \(k\), and for each such subsets \(U\) check if the graph \(G[C \cup U]\) has an e.d.s. \(D’\) with \(U \subseteq D’\)]; step (\(k\).3) consists of \(O(n^{k})\) calls of step (\(k\).3.1.1) [according to to Observation 3.1-(ii)-(iii)], so that it can be executed in \(O(n^{k} \cdot T)\) time, where \(O(T)\) is the running time bound of step (\(k\).3.1.1).

This completes the proof of Lemma 3.3. \(\square\)

Lemma 3.4. Step (6.3.1.1) can be executed in \(O(n^3)\) time.

Proof. By definition of Algorithm WED-P10, let us fix any induced \(C_6\) of \(G\) of vertex-set \(C\), say of vertices \(c_1,\ldots,c_6\) and of edges \(c_1c_2, \ldots, c_6c_1\), and let us fix any member (\(C’,{\cal D}(C’)\)) of \({\cal F}_C\) and any e.d.s. \(D’ \in {\cal D}(C’)\).

Then let us show that \(D^{**} \in\) arg min\(\{w(D) : D\) is an e.d.s. of \(G\), with \(D \cap C’ = D’\}\) can be computed in polynomial time. For convenience let us denote \(D^{**}\) as \(D\).

Let us recall the notation \(N_h(D’) = \{v \in V(G): dist(v,D’) = h\}\), for \(h \geq 1\), for the distance levels with respect to \(D’\).

Notation: for brevity let us write \(D’ = N_0\) and \(N_h(D’) = N_h\) for \(h \geq 1\).

Let us observe that, by construction, one has \(C \subseteq N_0 \cup N_1\).

Let us observe that \(D \cap (N_1 \cup N_2) = \emptyset\) by definition of e.d.s., so that each vertex of \(N_2\) has to be dominated by some vertex of \(N_3\), that is, of \(D \cap N_3\): in particular each vertex of \(N_3\) which is isolated in \(G[N_3 \cup N_4 \cup \ldots]\) is forced to be in \(D\).

Let \({\cal H}\) be the family of connected components of \(G[N_3 \cup N_4 \cup \ldots]\).

For any vertex \(x \in N_2\), let us say that \(x\) is: of Type 1 if \(x\) is adjacent to some vertex of \(C\); of Type 2 if \(x\) is not of Type 1 and is adjacent to a vertex of \(N_1\) which is adjacent to a vertex of \(N_0 \cap C\) [that is of \(D’ \cap C\)]; of Type 3 if \(x\) is not of Type 1 and is adjacent to a vertex of \(N_1\) which is adjacent to a vertex of \(N_0 \setminus C\) [that is of \(D’ \setminus C\)]. Let us observe that, by definition of e.d.s., \(x\) is of [exactly] one of the above types.

Then let us consider the following properties.

P1. Each vertex of \(N_2\) is the endpoint of an induced \(P_6\) of \(G\) formed together with five vertices of \(N_0 \cup N_1\).

Proof. Let \(x \in N_2\). If \(x\) is of Type 1, then \(x\) is adjacent to exactly one vertex of \(C\) [since \(G\) is bipartite \(C_4\)-free], and then P1 holds. If \(x\) is of Type 2 or of Type 3, then P1 holds by definition of Type 2 or of Type 3, and by construction [since \(G\) is bipartite \(C_4\)-free]. \(\square\)

P2. Each member of \({\cal H}\) is a tree, rooted at some vertex of \(N_3\), of depth at most two.

Proof. Let \(H\) be a member of \({\cal H}\).

First let us show that \(H\) is a tree. By contradiction, assume that \(H\) contains an induced \(C_k\) for some \(k = 6,8,10\) [recall that \(G\) is bipartite (\(P_{10},C_4\))-free]. Now let \(x \in N_2\) be a vertex whose distance from the \(C_k\) is minimum over all vertices of \(N_2\): let \(P\) be a shortest path from \(x\) to \(C\) [thus all vertices of \(P\) are in \(N_3 \cup N_4 \cup \ldots\)]. Notice that the vertex of \(P\), which is adjacent to some vertex of the \(C_k\), is the endpoint of an induced \(P_5\) together with four vertices of the \(C_k\) [since \(G\) is bipartite \(C_4\)-free]; on the other hand, by P1, \(x\) is the endpoint of an induced \(P_6\) of \(G\) formed together with five vertices of \(N_0 \cup N_1\); thus, \(G\) contains an induced \(P_{10}\), a contradiction.

Then let us show that \(H\), rooted at some vertex of \(N_3\), is of depth at most two. Let \(a\) be any vertex of \(V(H) \cap N_3\) and let us fix \(a\) as the root of \(H\), namely, \(H = T(a)\) according to the notation introduced above. Then let \(x \in N_2\) be a neighbor of \(a\); notice that \(x\) is nonadjacent to any vertex of \(T_j(a)\), for \(j = 1,2,3\), since \(G\) is bipartite \(C_4\)-free. Thus \(T_3(a) = \emptyset\), else otherwise by P1 an induced \(P_{10}\) arises, involving vertices \(x\) and \(a\). \(\square\)

In what follows, by P2 [if necessary] let us write any member \(H\) of \({\cal H}\) as \(H = T(a)\) for some \(a \in N_3\) [that is \(H\) is a tree, rooted at vertex \(a \in N_3\), of depth at most two].

P3. For each member \(H = T(a)\) of \({\cal H}\), with \(|T_1(a)| \geq 2\) and \(|T_2(a)| > 0\), the following statements hold:

• (i) vertex \(a\) would be forced to be \(not\) in \(D\);

• (ii) there are at most \(|T_1(a)|\) possibilities for \(D \cap V(H)\), namely, \(D(H,t) = \{t\} \cup (T_2(a) \setminus N(t))\) for each \(t \in T_1(a)\) provided that \(D(H,t)\) is an e.d.s. of \(H\); in particular, in this case, \(D(H,t) \cap N_3 = \emptyset\);

• (iii) if none of the above sets \(D(H,t)\) is an e.d.s. of \(H\), then \(G\) has not the sought e.d.s. \(D\); else, one can choose one of them, of minimum weight.

Proof. Concerning (i). Since \(|T_2(a)| > 0\) and since \(T_3(a) = \emptyset\) [by P1], vertex \(a\) would be forced to be \(not\) in \(D\), by definition of e.d.s. 

Concerning (ii). By statement (i), exactly one vertex \(t\) of \(T_1(a)\) should be in \(D\) [by definition of e.d.s.], and in this case vertex \(t\) should be contained in exactly one e.d.s. of \(H\), namely \(D(H,t) = \{t\} \cup (T_2(a) \setminus N(t))\) recalling that \(T_2(a)\) is an independent set.

Then let us show, if \(D(H,t)\) is an e.d.s. of \(H\), then \(D(H,t) \cap N_3 = \emptyset\). Notice that every vertex \(x\) of \(N_2\) is adjacent to no vertex in \(D(H,t) \cap T_1(a) = \{t\}\); in fact otherwise \(x\) is the endpoint of an induced \(P_5\) [since \(G\) is bipartite \(C_4\)-free and by definition of e.d.s.] together with \(t,a\), another \(\bar{t} \in T_1(a)\) [which does exist as \(|T_1(a)| \geq 2\)], and the vertex in \(D(H,t) \cap N(\bar{t}) \cap T_2(a)\) [which does exist as \(D(H,t)\) is an e.d.s. of \(H\)]; thus, by P1, an induced \(P_{10}\) arises. Furthermore notice that every vertex \(x\) of \(N_2\) is adjacent to no vertex say \(z\) of \(D(H,t) \cap T_2(a)\): in fact otherwise \(x\) is the endpoint of an induced \(P_5\) [since \(G\) is bipartite \(C_4\)-free and by definition of e.d.s.] together with \(z\), the neighbor of \(z\) in \(T_1(a)\), \(a\), and \(t\); thus, by P1, an induced \(P_{10}\) arises. Therefore \(D(H,t) \cap N_3 = \emptyset\).

Concerning (iii). According to statement (ii), for each \(t \in T_1(a)\), one can easily check whether \(D(H,t)\) is an e.d.s. of \(H\). If, for any \(t \in T_1(a)\), \(D(H,t)\) is not an e.d.s. of \(H\), then \(G\) has not the sought e.d.s. \(D\). Else, one can choose the set \(D(H,t)\) [which is an e.d.s. of \(H\)] of minimum weight, for \(t \in T_1(a)\). \(\square\)

P4. For each member \(H = T(a)\) of \({\cal H}\), such that:

• (i) \(|T_1(a)| = 1\) and \(|T_2(a)| > 0\), or

• (ii) \(|T_1(a)| \neq 1\) and \(|T_2(a)| = 0\),

vertex \(a\) would be forced to be in \(D\) while the other vertices of \(H\) to be \(not\) in \(D\).

Proof. Concerning case (i): since \(|T_2(a)| > 0\) and since \(T_3(a) = \emptyset\) [by P1], vertex \(a\) would be forced to be \(not\) in \(D\) and should be dominated by the vertex in \(T_1(a)\) by definition of e.d.s. 

Concerning case (ii): the proof directly follows by construction and by definition of e.d.s.. \(\square\)

Let us observe that the only members \(H = T(a)\) of \({\cal H}\), which enjoy [the assumptions of] neither P3 nor P4, are those such that \(|T_1(a)| = 1\) and \(|T_2(a)| = 0\), i.e., are \(edges\) of \(G\).

Then let \(\{{\cal H}_1,{\cal H}_2\}\) be the partition of \({\cal H}\) such that: \({\cal H}_1\) is formed by those members of \({\cal H}\) which enjoy [the assumptions of] either of P3 or of P4, while \({\cal H}_2\) is formed by those members of \({\cal H}\) with \(|T_1(a)| = 1\) and \(|T_2(a)| = 0\), i.e., by those members of \({\cal H}\) which are \(edges\) of \(G\).

Assumption 1: Let us assume that, for each member \(H\) of \({\cal H}_1\) which enjoys P3, one can determine \(D \cap H\) according to P3 [else \(G\) has not the sought e.d.s. \(D\) by P3-(iii)].

Then by the above properties one can simplify the problem as follows.

Let us focus on \(G’ = G[N_2 \cup N_3 \cup N_4 \cup \ldots]\).

Let us assume that all vertices of \(G’\) are uncolored: the goal is to check if vertices of \(G’\) can be colored/partitioned into \(white\) vertices, i.e. those in \(D\), and \(black\) vertices, i.e. those in \(V(G) \setminus D\), with the constraint that all vertices of \(N_2\) have to be black.

In particular the following forcing rules hold:

(R1) if vertex \(w\) is colored white, then all vertices of \(N(w)\) should be colored black;

(R2) if vertex \(b\) is colored black and if \(b\) has a neighbor \(w\) colored white, then all vertices of \(N(b) \setminus \{w\}\) should be colored black;

(R3) if \(h_1,h_2\) are the two vertices of a member of \({\cal H}_2\) and if \(h_1\) is colored black (respectively, white), then \(h_2\) should be colored white (respectively, black).

Then one can execute the following Pre-procedure whose running time bound can be estimated as \(O(n^2)\) time: (1) assign color black to all vertices of \(N_2\); (2) for each member \(H\) of \({\cal H}_1\), assign to each vertex of \(H\) the forced color according to P3 and to P4 [by Assumption 1]; (3) apply iteratively rules (R1), (R2), (R3).

Notice that: for any \(H=T(a)\) in \({\cal H}_1\) enjoying P3, vertex \(a\) is black [by P3-(i)], and no vertex of \(N_2\) is adjacent to any white vertex of \(H=T(a)\) [by P3-(ii)]; for any \(H=T(a)\) in \({\cal H}_1\) enjoying P4, vertex \(a\) is white, while the other vertices of \(T(a)\) are black [by P4].

Assumption 2: Let us assume that the above pre-procedure does not lead to a contradiction [else \(G\) has not the sought e.d.s. \(D\)].

At this point one can just focus on the following set and family:

\(N’_2 = \{x \in N_2 : x\) is adjacent to no white vertex [by the pre-procedure]},

\({\cal H}’_2 = \{H \in {\cal H}_2 :\) the two vertices of \(H\) are still uncolored [by the pre-procedure]\(\}\).

Let \(V({\cal H}’_2)\) denote the vertex set of members of \({\cal H}’_2\).

P5. Graph \(G\) has the sought e.d.s. \(D\) if and only if \(G[N’_2 \cup V({\cal H}’_2)]\) has an e.d.s. say \(D_{\text{peripheral}}\) with \(N’_2 \cap D_{\text{peripheral}} = \emptyset\).

Proof. In fact so far we showed that, if \(G\) has the sought e.d.s. \(D\), then some forcing conditions involve \(N_2\) (namely, \(D \cap N_2 = \emptyset\), and each vertex of \(N_2\) should be dominated by some vertex of \(N_3\)) and all members of \({\cal H} \setminus {\cal H}’_2\) (according to the pre-procedure). Notice that, by construction and by definition of the pre-procedure, no vertex of \(N_2 \setminus N’_2\) contacts any member of \({\cal H}’_2\). Summarizing, \(N’_2\) is a cut set of \(G\), and each vertex of \(N’_2\) should be dominated by some vertex of \(V({\cal H}’_2)\). Then, according to Assumption 1 and to Assumption 2, P5 is shown with \(D = D’ \cup W \cup D_{\text{peripheral}}\) where \(W\) is the set of vertices colored by white [by the pre-procedure]. \(\square\)

The following property P6 is just a technical parenthesis which will be useful later.

P6 Let \(Q\) be a connected component of \(G[N’_2 \cup V({\cal H}’_2)]\), such that \(Q\) contains exactly one vertex say \(x\) of \(N’_2\) [in particular, \(x\) is a cutset by construction, and is colored black by the pre-procedure]. Then one can easily determine an “optimal” coloring of \(Q\) (i.e. of \(Q \setminus \{x\}\)).

Proof. By assumption \(Q\) is formed by vertex \(x\) and by say \(\ell\) members of \({\cal H}’_2\) [namely \(\ell\) edges] contacted by \(x\). Thus, \(Q\) admits \(\ell\) e.d.s. not containing \(x\), in particular one can easily compute them and choose anyone of minimum weight [which will be part of \(D_{\text{peripheral}}\)]. \(\square\)

P7. One can compute \(D^*_{\text{peripheral}} \in\) arg min\(\{w(D_{\text{peripheral}}) : D_{\text{peripheral}}\) is an e.d.s. of \(G[N’_2 \cup V({\cal H}’_2)]\) with \(N’_2 \cap D_{\text{peripheral}} = \emptyset\}\) in \(O(n^3)\) time.

Proof. First let us recall that (by construction and by definition of e.d.s.) each vertex of \(N’_2\) has to be covered by some vertex of \(V({\cal H}’_2)\). Without loss of generality, to our aim, let us assume that \(G[N’_2 \cup V({\cal H}’_2)]\) is connected.

Then let us recall the aforementioned induced \(C_{6}\) in \(G[N_0 \cup N_1]\), of vertex-set \(C\), say of vertices \(c_1,\ldots,c_{6}\), and say of edges \(c_1c_2, \ldots, c_{6}c_1\).

Claim 1. One can assume (without loss of generality) that:

• (i) each vertex of \(N’_2\) contacts at least two members of \({\cal H}’_2\);

• (ii) each vertex of \(N’_2\) is of Type 1 [i.e. is adjacent to some vertex of \(C\)].

Proof. Proof of (i): In fact let \(x \in N’_2\): if \(x\) contacts no member of \({\cal H}’_2\), then the sought e.d.s. \(D^*\) does not exist; if \(x\) contacts exactly one member of \({\cal H}’_2\), then the neighbor of \(x\) (in such a member) would be forced to be in \(D^*\), so that one could iteratively apply rules (R1), (R2), (R3), and then reduce (again) the problem to a subset of \(N’_2\) and to a subfamily of \({\cal H}’_2\).

Proof of (ii): Let \(x \in N’_2\). Let us recall that \(x\) can be of Type 1, or of Type 2, or of Type 3.

First let us observe that \(x\) can not be of Type 3. By contradiction assume that \(x\) is of Type 3. Then \(x\) is adjacent to a vertex \(y \in N_1 \setminus C\), which is adjacent to a vertex \(z \in N_0 \setminus C\), which is adjacent to a vertex of \(C\); furthermore, by statement (i), \(x\) contacts at least one [actually more than one] member say \(H\) of \({\cal H}’_2\); then, since \(G\) is bipartite \(C_4\)-free, the two vertices of \(H\), \(x,y,z,\) and five vertices of \(C\) induce a \(P_{10}\), a contradiction.

Then let us assume that \(x\) is of Type 2. Then let \(u \in N_1\) be adjacent to \(x\) and be adjacent to \(c_1 \in D’ \cap C\) (without loss of generality by symmetry). Then let us consider the following two exhaustive occurrences.

:: Assume that \(c_3\) or \(c_5\) has a neighbor in \(D’ \setminus C\). Without loss of generality by symmetry, assume that \(c_5\) has a neighbor in \(z \in D’ \setminus C\), i.e. \(z \in N_0\). Then [by construction and since \(G\) is bipartite \(C_4\)-free] vertices \(z,c_4,c_3,c_2,c_1,u,x\) induce a \(P_8\). On the other hand, by statement (i), vertex \(x\) contacts at least one [actually more than one] member say \(H\) of \({\cal H}’_2\). Then an induced \(P_{10}\) would arise together the two vertices of \(H\), i.e., this occurrence is not possible.

:: Assume that \(c_3\) and \(c_5\) have no neighbor in \(D’ \setminus C\). Then, by definition of e.d.s., \(c_4 \in D’ \cap C\). By statement (i), vertex \(x\) contacts at least two members of \({\cal H}’_2\), say of vertices \(h_1,h_2\) and of vertices \(k_1,k_2\), respectively, with \(x\) adjacent to \(h_1\) and to \(k_1\) (without loss of generality by symmetry).

Let us show that \(h_1\) and \(h_2\) are adjacent to no vertex of \(N’_2 \setminus \{x\}\). In fact:

if \(h_1\) is adjacent to a vertex \(x_1 \in N’_2\), then: either \(x_1\) is of Type 1, and thus an induced \(P_{10}\) arises involving vertices \(k_2,k_1,x,h_1,x_1\), and five vertices of \(C\); or \(x_1\) is of Type 2 with a neighbor \(u_1 \in N’_2\) adjacent to \(c_1\) or to \(c_4\) [with \(u_1 \neq u\) since \(G\) is \(C_4\)-free], and thus an induced \(P_{10}\) arises involving vertices \(k_2,k_1,x,h_1,x_1,u_1\), and four vertices of \(C\);

if \(h_2\) is adjacent to a vertex \(x_2 \in N’_2\), then \(x_2\) is adjacent to \(c_3\) or to \(c_5\) [else \(x_2,h_2,h_1,x,u,c_1,\\c_2,c_3,c_4,c_5\) induce a \(P_{10}\)], say to \(c_5\) without loss of generality by symmetry, and thus \(k_1,x,h_1,h_2,x_2,c_5,c_4,c_3,c_2,c_1\) induce a \(P_{10}\).

Then \(h_1\) and \(h_2\) are adjacent to no vertex of \(N’_2 \setminus \{x\}\). It follows [by a similar argument] that every member \(H\) of \({\cal H}’_2\), which is contacted by \(x\), is contacted by no vertex of \(N’_2 \setminus \{x\}\). Then one can easily determine an “optimal” coloring of each such members \(H\) according to P6.

This completes the proof of statement (ii). \(\square\)

Claim 2. For any member \(H\) of \({\cal H}’_2\), of vertices say \(h_1,h_2\), one has that: \(h_1\) is adjacent to at most one vertex of \(N’_2\), and \(h_2\) is adjacent to at most one vertex of \(N’_2\).

Proof. By symmetry let us just prove that \(h_1\) is adjacent to exactly one vertex of \(N’_2\): in particular, let us assume that \(h_1\) has a neighbor \(x \in N’_2\) (else the claim is proved), and by Claim 1 let us assume that \(x\) is adjacent to \(c_1\) (without loss of generality by symmetry).

Then let us show that no vertex \(x’ \in N’_2\), different to \(x\), is adjacent to \(h_1\): in fact otherwise, since \(G\) is bipartite \(C_4\)-free, \(x’\) is nonadjacent to \(x\) and is adjacent to \(c_3\) (without loss of generality by symmetry) since \(G\) is bipartite \(C_4\)-free; then by Claim 1 and since \(G\) is bipartite \(C_4\)-free, there exist two distinct members of \({\cal H}’_2\), say \(H’\) and \(H”\), such that \(x’\) contacts \(H’\) while \(x\) contacts \(H”\); then \(V(H’),x’,c_3,c_4,c_5,c_6,c_1,x,V(H”)\) induce a \(P_{11}\), that is not possible since \(G\) is \(P_{10}\)-free. \(\square\)

Notation. Let us say that a pair \(\{x,y\} \subseteq N’_2\) is a complementary pair of \(N’_2\) if there is a member \(H\) of \({\cal H}’_2\), of vertices say \(h_1,h_2\), such that \(x\) is adjacent to \(h_1\) while \(y\) is adjacent to \(h_2\); in particular, in this case, let us say that \(\{x,y\}\) covers \(H\), and that \(H\) is covered by \(\{x,y\}\). Notice that: \(x\) is nonadjacent to \(h_2\) (by Claim 2), \(y\) is nonadjacent to \(h_1\) (by Claim 2), \(x\) is nonadjacent to \(y\) (since \(G\) is \(C_4\)-free). Furthermore in what follows, as an agreement, let us assume that any complementary pair \(\{x,y\}\) of \(N’_2\) is an ordered pair with \(x \in V_1(G)\) and \(y \in V_2(G)\).

Claim 3. Let \(\{x,y\}\) be a complementary pair of \(N’_2\). Then \(\{x,y\}\) covers at least two members \({\cal H}’_2\).

Proof. By assumption, \(\{x,y\}\) is a complementary pair of \(N’_2\), that is, there is a member \(H\) of \({\cal H}’_2\), of vertices say \(h_1,h_2\), such that \(x\) is adjacent to \(h_1\) while \(y\) is adjacent to \(h_2\).

Without loss of generality by symmetry, let us assume that \(x\) is adjacent to \(c_1\), and that \(y\) is adjacent either to \(c_2\) or to \(c_4\).

First let us show that there are no distinct members of \({\cal H}’_2\), say \(H_x\) and \(H_y\), such that: \(x\) contacts \(H_x\) and does not contact \(H_y\), while \(y\) contacts \(H_y\) and does not contact \(H_x\). In fact, by contradiction, assume that such distinct members exist. Then: if \(y\) is adjacent to \(c_2\), then \(V(H_y),y,h_2,h_1,x,c_1,c_6,c_5,c_4\) induce a \(P_{10}\), that is not possible; if \(y\) is adjacent to \(c_4\), then \(V(H_y),y,c_4,c_5,c_6,c_1,x,V(H_x)\) induce a \(P_{10}\), that is not possible. Then the assertion is shown.

Then, by Claim 1, there is a member of \({\cal H}’_2\), say \(K\) of vertices \(k_1,k_2\), such that both \(x\) and \(y\) contact \(K\), i.e., \(x\) is adjacent to \(k_1\) while \(y\) is adjacent to \(k_2\) (by Claim 2).

This completes the proof of Claim 3. \(\square\)

Claim 4. Let \(\{x,y\}\) be a complementary pair of \(N’_2\). Then \(x\) and \(y\) are adjacent respectively to opposite vertices of \(G[C]\), i.e., \(x\) is adjacent to \(c_i\) while \(y\) is adjacent to \(c_{i+3}\) for some \(i \in \{1,\ldots,3\}\).

Proof. By Claim 3, \(\{x,y\}\) covers at least two two members say \(H,K\) of \({\cal H}’_2\), of vertices say respectively \(h_1,h_2\), and \(k_1,k_2\), such that \(x\) is adjacent to \(h_1\) and \(k_1\) while \(y\) is adjacent to \(h_2\) and \(k_2\).

Let us assume that \(x\) is adjacent to \(c_1\) without loss of generality by symmetry. Then \(y\) is nonadjacent to \(c_2\) [else \(h_2,y,k_2,k_1,x,c_1,c_6,c_5,c_4,c_3\) induce a \(P_{10}\)], \(y\) is nonadjacent to \(c_6\) [similarly by symmetry], so that \(y\) is adjacent to \(c_4\). \(\square\)

Claim 5. Let \(\{x,y\}\) be a complementary pair of \(N’_2\) and let \(H\) be a member of \({\cal H}’_2\), of vertices say \(h_1,h_2\), such that \(x\) is adjacent to \(h_1\) while \(y\) is adjacent to \(h_2\). Then: if one should fix the color of \(h_1\) [or of \(h_2\)] as white, then for any member \(H^*\) of \({\cal H}’_2\) which is contacted by \(x\) or by \(y\), the color of each vertex of \(H^*\) would be determined by the forcing rules.

Proof. By Claim 3, \(\{x,y\}\) covers at least two two members say \(H,K\) of \({\cal H}’_2\), of vertices say respectively \(h_1,h_2\), and \(k_1,k_2\), such that \(x\) is adjacent to \(h_1\) and \(k_1\) while \(y\) is adjacent to \(h_2\) and \(k_2\).

Now let us assume that one fixes the color of \(h_1\) as white [so that, by rule (R3), the color of \(h_2\) is forced to be black]. Then, by rule (R2), the color of \(k_1\) is forced to be black; so that, by rule (R3), the color of \(k_2\) is forced to be white; let us recall that \(y\) is adjacent to \(k_2\); at this point, by rule (R2), each vertex of any member \(H^*\) of \({\cal H}’_2\) [different to \(H\) and to \(K\)] which is contacted by \(x\) or \(y\), is forced to be black, so that by rule (R3) the other vertex of \(H^*\) is forced to be white. This shows Claim 3. \(\square\)

For any two complementary pairs \(\{x,y\}\) and \(\{x’,y’\}\) of \(N’_2\), let us say that \(\{x,y\}\) and \(\{x’,y’\}\) are disjoint if \(x \neq x’\) and \(y \neq y’\).

Claim 6. For any two disjoint complementary pairs \(\{x,y\}\) and \(\{x’,y’\}\) of \(N’_2\), one has that: \(x\) is adjacent to \(y’\), while \(y\) is adjacent to \(x’\).

Proof. By Claim 3, \(\{x,y\}\) covers at least two two members say \(H,K\) of \({\cal H}’_2\), of vertices say respectively \(h_1,h_2\), and \(k_1,k_2\), such that \(x\) is adjacent to \(h_1\) and \(k_1\) while \(y\) is adjacent to \(h_2\) and \(k_2\). By Claim 3, \(\{x’,y’\}\) covers at least two two members say \(H’,K’\) of \({\cal H}’_2\), of vertices say respectively \(h’_1,h’_2\), and \(k’_1,k’_2\), such that \(x’\) is adjacent to \(h’_1\) and \(k’_1\) while \(y’\) is adjacent to \(h’_2\) and \(k’_2\).

Let us recall that, by the above agreement, one has that \(x,x’ \in V_1(G)\) and \(y,y’ \in V_2(G)\); thus, \(x\) is nonadjacent to \(x’\), and \(y\) is nonadjacent to \(y’\).

Note that, by Claim 2 and since \(\{x,y\}\) and \(\{x’,y’\}\) are disjoint, one has that: \(x\) and \(y\) do not contact \(V(H’)\) and \(V(K’)\); \(x’\) and \(y’\) do not contact \(V(H)\) and \(V(K)\).

Let us assume, without loss of generality by symmetry, that \(x\) is adjacent to \(c_1\); thus, by Claim 4, \(y\) is adjacent to \(c_4\).

Now, by contradiction, assume that either \(x\) is nonadjacent to \(y’\), or \(y\) is nonadjacent to \(x’\).

First let us assume that \(x\) is nonadjacent to \(y’\), and \(y\) is nonadjacent to \(x’\): if \(x’\) is adjacent to \(c_1\), then \(h_2,y,k_2,k_1,x,c_1,x’,h’_1,h’_2,y’\) induce a \(P_{10}\); if \(x’\) is adjacent to \(c_3\), then \(h_2,y,k_2,k_1,x,c_1,c_2,c_3,x’,h’_1,\) induce a \(P_{10}\); if \(x’\) is adjacent to \(c_5\), then similarly by symmetry there are vertices which induce a \(P_{10}\).

Then let us assume that \(x\) is adjacent to \(y’\), and \(y\) is nonadjacent to \(x’\): then \(h_2,y,k_2,k_1,x,\\y’,k’_2,k’_1,x’,h’_1\) induce a \(P_{10}\).

Finally let us assume that \(x\) is nonadjacent to \(y’\), and \(y\) is adjacent to \(x’\): such an occurrence can be treated similarly to the previous one by symmetry.

This completes the proof of Claim 6. \(\square\)

Claim 7. There are at most three mutually disjoint complementary pairs of \(N’_2\).

Proof. By contradiction assume that there are four mutually disjoint complementary pairs of \(N’_2\), say \(\{x_1,y_1\}, \{x_2,y_2\}, \{x_3,y_3\}, \{x_4,y_4\}\). By the above agreement, one has \(x_1,x_2,x_3,x_4 \in V_1(G)\) and \(y_1,y_2,y_3,y_4 \in V_2(G)\). Then by Claim 4 and by Claim 6 one has that, for \(i = 1,2,3,4\), \(x_i\) is nonadjacent to \(y_i\) and is adjacent to \(y_j\) for every \(j \in \{1,2,3,4\} \setminus \{i\}\). Then \(x_1,y_2,x_3,y_4\) induce a \(C_4\), a contradiction. \(\square\)

Now let us conclude the proof of P7.

For that let us describe the following possible solution method.

Step initialization: set \(D^*_{\text{peripheral}}:= \emptyset\) and set \(w(D^*_{\text{peripheral}}):= \infty\).

Step A. Compute a maximal family, say \({\cal P}\), of mutually disjoint complementary pairs of \(N’_2\) [note that, by Claim 7, family \({\cal P}\) has at most three members]:

:: A1. if \({\cal P} = \{\emptyset\}\), then proceed as follows: note that, by construction and since \({\cal P} = \{\emptyset\}\), each member of \({\cal H}’_2\) is contacted by exactly one vertex of \(N’_2\); then, by Claim 2, each connected component say \(Q\) of \(G[N’_2 \cup V({\cal H}’_2)]\) contains exactly one vertex of \(N’_2\); then one can easily determine an “optimal” coloring of \(Q\) according to P6; then return the sought e.d.s. \(D^*_{\text{peripheral}}\), and STOP;

:: A2. if \({\cal P} \neq \{\emptyset\}\), then let us write \({\cal P} = \{\{x,y\},\{x’,y’\},\{x”,y”\}\}\), without loss of generality for this description; then go to Step B.

Step B. Select any three members of \({\cal H}’_2\), namely three edges \((h_1,h_2),(h’_1,h’_2),(h”_1,h”_2)\), which are respectively covered by \(\{x,y\},\{x’,y’\},\{x”,y”\}\). Note that, by rule (R3), each such edges can be colored in two ways [e.g., concerning edge \((h_1,h_2)\), one can fix either “\(h_1\) black and \(h_2\) white” or “ \(h_1\) white and \(h_2\) black”]: thus there are eight ways to color edges \((h_1,h_2),(h’_1,h’_2),(h”_1,h”_2)\).

Step C. For each such eight ways, namely for \(\alpha \in \{1,\ldots,8\}\), fix the corresponding coloring of edges \((h_1,h_2),(h’_1,h’_2),(h”_1,h”_2)\), and determine the color of the remaining vertices [by the forcing conditions] as follows:

— color vertices of those members of \({\cal H}’_2\) which are contacted by at least one vertex in \(\{x,y,x’,y’,x”,y”\}\) according to Claim 5;

— color vertices of the remaining members of \({\cal H}’_2\) \(-\) let \({\cal H}”_2\) denote the subfamily of \({\cal H}’_2\) formed by these remaining members \(-\) as follows: note that, by Claim 2, by Claim 7, and by step C1, each member of \({\cal H}”_2\) is contacted by exactly one vertex of \(N’_2\);

thus, each connected component say \(Q\) of \(G[N”_2 \cup V({\cal H}”_2)]\) contains exactly one vertex say \(x_Q\) of \(N’_2\), so that one can easily determine an “optimal” coloring of \(Q\) according to P6;

— if the above procedure has not led to any contradiction, then: (i) denote the set of white vertices as \(D^{\alpha}_{\text{peripheral}}\); (ii) if \(w(D^{\alpha}_{\text{peripheral}}) < w(D^{*}_{\text{peripheral}})\), then set \(D^{*}_{\text{peripheral}} := D^{\alpha}_{\text{peripheral}}\).

Step D.

:: If \(D^{*}_{\text{peripheral}} = \emptyset\), then return “\(G\) has no e.d.s.”, and STOP.

:: If \(D^{*}_{\text{peripheral}} \neq \emptyset\), then return \(D^{*}_{\text{peripheral}}\), and STOP.

The above solution method is correct by Claim 1, Claim 2, Claim 5, and Claim 7. Furthermore the running time bound can be estimated as \(O(n^3)\) time.

This completes the proof of P7. \(\square\)

This completes the proof of Lemma 3.4. \(\square\)

Lemma 3.5. Step (8.3.1.1) can be executed in polynomial time.

Proof. The proof is similar (but shorter) to that of Lemma 3.4.

As a preliminary let us remark that Step (8.3.1.1) is executed only if \(G\) is \(C_6\)-free: thus let us assume that \(G\) is \(C_6\)-free.

By definition of Algorithm WED-P10, let us fix any induced \(C_8\) of \(G\) of vertex-set \(C\), say of vertices \(c_1,\ldots,c_8\) and of edges \(c_1c_2, \ldots, c_8c_1\), and let us fix any member (\(C’,{\cal D}(C’)\)) of \({\cal F}_C\) and any e.d.s. \(D’ \in {\cal D}(C’)\).

Then let us show that \(D^{**} \in\) arg min\(\{w(D) : D\) is an e.d.s. of \(G\), with \(D \cap C’ = D’\}\) can be computed in polynomial time. For convenience let us denote \(D^{**}\) as \(D\).

Let us recall the notation \(N_h(D’) = \{v \in V(G): dist(v,D’) = h\}\), for \(h \geq 1\), for the distance levels with respect to \(D’\).

Notation: for brevity let us write \(D’ = N_0\) and \(N_h(D’) = N_h\) for \(h \geq 1\).

Let us observe that by construction one has \(C \subseteq N_0 \cup N_1\).

Let us observe that \(D \cap (N_1 \cup N_2) = \emptyset\) by definition of e.d.s., so that each vertex of \(N_2\) has to be covered by some vertex of \(N_3\), that is, of \(D \cap N_3\): in particular each vertex of \(N_3\) which is isolated in \(G[N_3 \cup N_4 \cup \ldots]\) is forced to be in \(D\).

Let \({\cal H}\) be the family of connected components of \(G[N_3 \cup N_4 \cup \ldots]\).

For any vertex \(x \in N_2\), let us say that \(x\) is: of Type 1 if \(x\) is adjacent to some vertex of \(C\); of Type 2 if \(x\) is not of Type 1 and is adjacent to a vertex of \(N_1\) which is adjacent to a vertex of \(N_0 \cap C\) [that is of \(D’ \cap C\)]; of Type 3 if \(x\) is not of Type 1 and is adjacent to a vertex of \(N_1\) which is adjacent to a vertex of \(N_0 \setminus C\) [that is of \(D’ \setminus C\)]. Let us observe that, by definition of e.d.s., \(x\) is of [exactly] one of the above types.

Then let us consider the following properties.

P1. Each vertex of \(N_2\) is the endpoint of an induced \(P_8\) of \(G\) formed together with seven vertices of \(N_0 \cup N_1\).

Proof. Let \(x \in N_2\). If \(x\) is of Type 1, then \(x\) is adjacent to exactly one vertex of \(C\) [since \(G\) is bipartite (\(C_4,C_6\))-free], and then P1 holds true. If \(x\) is of Type 2 or of Type 3, then P1 holds true by definition of Type 2 or of Type 3, and by construction [since \(G\) is bipartite (\(C_4,C_6\))-free]. \(\square\)

P2. Each member of \({\cal H}\) is a singleton.

Proof. Let \(H\) be a member of \({\cal H}\). Let us show that \(H\) has exactly one vertex. By contradiction, recalling that \(H\) is connected, assume that \(H\) contains at least two vertices. Now, let \(x \in N_2\) be a vertex adjacent to a vertex \(h\) of \(H\), and let \(h’\) be a neighbor of \(h\) in \(H\). By P1, \(x\) is the endpoint of an induced \(P_8\) of \(G\) formed together with seven vertices of \(N_0 \cup N_1\); thus, \(G\) contains an induced \(P_{10}\), a contradiction. \(\square\)

At this point, by construction and by the above observations, one has that the sought e.d.s. \(D\) exists if and only if \(D = D’ \cup V({\cal H})\) where \(V({\cal H})\) is the vertex set of all members of \({\cal H}\).

The running time bound for this final check can be estimated as \(O(n^2)\).

This completes the proof of Lemma 3.5. \(\square\)

Lemma 3.6. Step (10.3.1.1) can be executed in constant time.

Proof. The proof is similar (but shorter) to that of Lemma 3.4.

As a preliminary let us remark that Step (10.3.1.1) is executed only if \(G\) is (\(C_6,C_8\))-free: thus let us assume that \(G\) is (\(C_6,C_8\))-free.

By definition of Algorithm WED-P10, let us fix any induced \(C_{10}\) of \(G\) of vertex-set \(C\), say of vertices \(c_1,\ldots,c_8\) and of edges \(c_1c_2, \ldots, c_8c_1\), and let us fix any member (\(C’,{\cal D}(C’)\)) of \({\cal F}_C\) and any e.d.s. \(D’ \in {\cal D}(C’)\).

Then let us show that \(D^{**} \in\) arg min\(\{w(D) : D\) is an e.d.s. of \(G\), with \(D \cap C’ = D’\}\) can be computed in constant time. For convenience let us denote \(D^{**}\) as \(D\).

Let us recall the notation \(N_h(D’) = \{v \in V(G): dist(v,D’) = h\}\), for \(h \geq 1\), for the distance levels with respect to \(D’\).

Notation: for brevity let us write \(D’ = N_0\) and \(N_h(D’) = N_h\) for \(h \geq 1\).

Let us observe that by construction one has \(C \subseteq N_0 \cup N_1\).

Let us observe that \(D \cap (N_1 \cup N_2) = \emptyset\) by definition of e.d.s., so that each vertex of \(N_2\) has to be covered by some vertex of \(N_3\), that is, of \(D \cap N_3\): in particular each vertex of \(N_3\) which is isolated in \(G[N_3 \cup N_4 \cup \ldots]\) is forced to be in \(D\).

Let \({\cal H}\) be the family of connected components of \(G[N_3 \cup N_4 \cup \ldots]\).

For any vertex \(x \in N_2\), let us say that \(x\) is: of Type 1 if \(x\) is adjacent to some vertex of \(C\); of Type 2 if \(x\) is not of Type 1 and is adjacent to a vertex of \(N_1\) which is adjacent to a vertex of \(N_0 \cap C\) [that is of \(D’ \cap C\)]; of Type 3 if \(x\) is not of Type 1 and is adjacent to a vertex of \(N_1\) which is adjacent to a vertex of \(N_0 \setminus C\) [that is of \(D’ \setminus C\)]. Let us observe that, by definition of e.d.s., \(x\) is of [exactly] one of the above types.

Then let us consider the following properties.

P1. \(N_2 = \emptyset\).

Proof. Let \(x \in N_2\). If \(x\) is of Type 1, then \(x\) is adjacent to exactly one vertex of \(C\) [since \(G\) is bipartite (\(C_4,C_6,C_8\))-free], and then an induced \(P_{10}\) arises. If \(x\) is of Type 2 or of Type 3, then then an induced \(P_{10}\) arises by definition of Type 2 or of Type 3, and by construction [since \(G\) is bipartite (\(C_4,C_6,C_8\))-free]. \(\square\)

At this point, by construction and by the above observations, one has that the sought e.d.s. \(D\) always exists and \(D = D’\).

This completes the proof of Lemma 3.6. \(\square\)

Thus, Theorem 1.4 is shown.

The following corollary is useful for the running time bound introduced in Subsection 2.3.

Corollary 3.7. For \((P_{8},C_4)\)-free bipartite graphs, then WED problem can be solved in \(O(n^3)\) time.

Proof. The running time bound can be derived by the proof of Theorem 1.4, since for any induced \(C_6\) or \(C_8\) of vertex set say \(C\), one has that: for any fixed member \((C’,{\cal D}(C’))\) of \({\cal F}_C\) and for any \(D’ \in {\cal D}(C’)\), \(N_3(D’)\) is formed by singletons while \(N_4(D’) = \emptyset\). \(\square\)

4. The WED problem for subclasses of \((P_{t},C_4)\)-free bipartite graphs

This section can be view as first attempt of extension of the results in Section 3, in particular, let us adopt the preliminary introduced in Section 3.

For any bipartite graph \(G = (V(G),E(G))\), let us write \(V(G) = V_1(G) \cup V_2(G)\), where \(V_1(G)\) and \(V_2(G)\) are the two sides of \(G\) [i.e. they are independent sets].

Let us introduce the following algorithm \(-\) that generalizes Algorithm WED-P10 \(-\) to solve WED for \((P_{t},C_4)\)-free bipartite graphs, for \(t \geq 11\), which are not trees.

Algorithm WED

Input: a connected (\(P_{t},C_4\))-free bipartite graph \(G\), for \(t \geq 11\), which is not a tree.

Output: an e.d.s. of \(G\) of minimum weight or a proof that \(G\) has no e.d.s.

begin

:: set \(D^* := \emptyset\) and set \(w(D^*) := \infty\);

:: for \(k = 6, 8, 10, \ldots, 2 \lfloor t/2 \rfloor\), do

:: begin

:: :: if \(G\) contains some induced \(C_k\), then:

:: :: :: (\(k\).1) take \(any\) such induced \(C_k\)’s, say, of vertex-set \(C\);

:: :: :: (\(k\).2) compute family \({\cal F}_C\) [according to Observation 3.1];

:: :: :: (\(k\).3) for each member (\(C’,{\cal D}(C’)\)) of \({\cal F}_C\) do

:: :: :: :: (\(k\).3.1) for each e.d.s. \(D’ \in {\cal D}(C’)\) do

:: :: :: :: begin

:: :: :: :: :: (\(k\).3.1.1) compute \(D^{**} \in\) arg min\(\{w(D) : D\) is an e.d.s. of \(G\), with \(D \cap C’ = D’\}\);

:: :: :: :: :: (\(k\).3.1.2) if such an e.d.s \(D^{**}\) exists and if \(w(D^{**}) < w(D^*)\), then set \(D^* := D^{**}\);

:: :: :: :: end

:: :: :: (\(k\).4) if \(D^* = \emptyset\), then return “\(G\) has no e.d.s.”, and STOP;

:: :: :: (\(k\).5) if \(D^* \neq \emptyset\), then return \(D^*\), and STOP;

:: end

end.

Lemma 4.1. Algorithm WED is correct. Furthermore Algorithm WED can be executed in max\(\{O(n^{3} \cdot T_k) : k = 6, 8, 10, \ldots, 2 \lfloor t/2 \rfloor\}\) time, where \(O(T_k)\) is the running time bound of step (\(k\).3.1.1) for \(k = 6, 8, 10, \ldots, 2 \lfloor t/2 \rfloor\); thus, it can be executed in polynomial time, provided that each step (\(k\).3.1.1), for \(k = 6, 8, 10, \ldots, 2 \lfloor t/2 \rfloor\), can be executed in polynomial time.

Proof. As a preliminary let us remark that, since \(G\) is (\(P_{t},C_4\))-free bipartite, the only possible induced cycle in \(G\) are \(C_6\)’s, \(C_8\)’s, \(\ldots\), \(C_{t}\)’s.

Then the proof is very similar to that of Lemma 3.3 and is not reported for brevity. \(\square\)

Then for completeness \(-\) with reference to the polynomial results claimed in Subsection 1.3 \(-\) let us show, by the above approach, that WED can be solved for a subclass of bipartite \((P_{t},C_4)\)-free graphs (for \(t \geq 11\)) in polynomial time.

4.1. The WED problem for bipartite \((P_{13},C_4,C_6,C_8)\)-free graphs

In this subsection let us show that WED can be solved for bipartite \((P_{13},C_4,C_6,C_8)\)-free graphs in polynomial time.

Then let \(G\) be a bipartite \((P_{13},C_4,C_6,C_8)\)-free graph.

Then let us apply Algorithm WED with input graph \(G\).

Then the following lemma [which is just an adaptation of the lemma above] holds.

Lemma 4.2. Algorithm WED is correct. Furthermore Algorithm WED-P10 can be executed in max\(\{O(n^{3} \cdot T_k) : k = 10, 12\}\) time, where \(O(T_k)\) is the running time bound of step (\(k\).3.1.1) for \(k = 10, 12\). Thus Algorithm WED can be executed in polynomial time provided that each step (\(k\).3.1.1), for \(k = 10, 12\), can be executed in polynomial time.

Proof. The lemma directly follows by Lemma 4.2 since \(G\) is \((P_{13},C_4,C_6,C_8)\)-free. \(\square\)

The following lemma is just an adaptation of Lemma 3.4 with a slight modification.

Lemma 4.3. Step (10.3.1.1) can be executed in \(O(n^2)\) time.

Proof. By definition of Algorithm WED, let us fix any induced \(C_{10}\) of \(G\) of vertex-set \(C\), say of vertices \(c_1,\ldots,c_{10}\) and of edges \(c_1c_2, \ldots, c_{10}c_1\), and let us fix any member (\(C’,{\cal D}(C’)\)) of \({\cal F}_C\) and any e.d.s. \(D’ \in {\cal D}(C’)\).

Then let us show that \(D^{**} \in\) arg min\(\{w(D) : D\) is an e.d.s. of \(G\), with \(D \cap C’ = D’\}\) can be computed in polynomial time. For convenience let us denote \(D^{**}\) as \(D\).

Let us recall the notation \(N_h(D’) = \{v \in V(G): dist(v,D’) = h\}\), for \(h \geq 1\), for the distance levels with respect to \(D’\).

Notation: for brevity let us write \(D’ = N_0\) and \(N_h(D’) = N_h\) for \(h \geq 1\).

Let us observe that by construction one has \(C \subseteq N_0 \cup N_1\).

Let us observe that \(D \cap (N_1 \cup N_2) = \emptyset\) by definition of e.d.s., so that each vertex of \(N_2\) has to be covered by some vertex of \(N_3\), that is, of \(D \cap N_3\): in particular each vertex of \(N_3\) which is isolated in \(G[N_3 \cup N_4 \cup \ldots]\) is forced to be in \(D\).

Let \({\cal H}\) be the family of connected components of \(G[N_3 \cup N_4 \cup \ldots]\).

For any vertex \(x \in N_2\), let us say that \(x\) is: of Type 1 if \(x\) is adjacent to some vertex of \(C\); of Type 2 if \(x\) is not of Type 1 and is adjacent to a vertex of \(N_1\) which is adjacent to a vertex of \(N_0 \cap C\) [that is of \(D’ \cap C\)]; of Type 3 if \(x\) is not of Type 1 and is adjacent to a vertex of \(N_1\) which is adjacent to a vertex of \(N_0 \setminus C\) [that is of \(D’ \setminus C\)]. Let us observe that, by definition of e.d.s., \(x\) is of [exactly] one of the above types.

Let us remark that one can assume that \(x\) is either of Type 1 or of Type 2: in fact, if \(x\) is of Type 3, then \(x\) is adjacent to no vertex of \(N_3\) [else an induced \(P_{13}\) arises] so that the sought e.d.s. \(D\) would not exist.

Then let us consider the following properties.

P1. Each vertex of \(N_2\) is the endpoint of an induced \(P_{10}\) of \(G\) formed together with nine vertices of \(N_0 \cup N_1\).

Proof. Let \(x \in N_2\). If \(x\) is of Type 1, then \(x\) is adjacent to exactly one vertex of \(C\) [since \(G\) is bipartite (\(C_4,C_6,C_8\))-free], and then P1 holds. If \(x\) is of Type 2, then P1 holds by definition of Type 2, and by construction [since \(G\) is bipartite (\(C_4,C_6,C_8\))-free]. \(\square\)

P2. Each member of \({\cal H}\) is a tree, rooted at some vertex of \(N_3\), of depth at most one.

Proof. Let \(H\) be a member of \({\cal H}\).

First let us show that \(H\) is a tree. By contradiction, assume that \(H\) contains an induced \(C_k\) for some \(k = 10,12\) [recall that \(G\) is bipartite (\(C_4,C_6,C_8\))-free]. Now let \(x \in N_2\) be a vertex whose distance from the \(C_k\) is minimum over all vertices of \(N_2\): let \(P\) be a shortest path from \(x\) to \(C\) [thus all vertices of \(P\) are in \(N_3 \cup N_4 \cup \ldots\)]. Notice that the vertex of \(P\) is adjacent to no vertex of the \(C_k\) [since \(G\) is bipartite (\(C_4,C_6,C_8\))-free]; on the other hand, by P1, \(x\) is the endpoint of an induced \(P_{10}\) of \(G\) formed together with nine vertices of \(N_0 \cup N_1\); thus, \(G\) contains an induced \(P_{13}\), a contradiction.

Then let us show that \(H\), rooted at some vertex of \(N_3\), is of depth at most one. Let \(a\) be any vertex of \(V(H) \cap N_3\) and let us fix \(a\) as the root of \(H\), namely, \(H = T(a)\) according to the notation introduced above. Then let \(x \in N_2\) be a neighbor of \(a\); notice that \(x\) is nonadjacent to any vertex of \(T_j(a)\), for \(j = 1,2\), since \(G\) is bipartite \(C_4\)-free. Thus \(T_2(a) = \emptyset\), else otherwise by P1 and by the above an induced \(P_{10}\) arises, involving vertices \(x\) and \(a\). \(\square\)

In what follows, by P2 [if necessary] let us write any member \(H\) of \({\cal H}\) as \(H = T(a)\) for some \(a \in N_3\) [that is \(H\) is a tree, rooted at vertex \(a \in N_3\), of depth at most one].

P3. For each member \(H = T(a)\) of \({\cal H}\), with \(|T_1(a)| \neq 1\), vertex \(a\) would be forced to be in \(D\) while the other vertices of \(H\) to be \(not\) in \(D\).

Proof. The proof follows by construction, by definition of e.d.s., and by P2.   \(\square\)

Let us observe that the only members \(H = T(a)\) of \({\cal H}\), which do not enjoy [the assumptions of] P3, are those such that \(|T_1(a)| = 1\) [and \(|T_2(a)| = 0\) by P2], i.e., are \(edges\) of \(G\).

Then let \(\{{\cal H}_1,{\cal H}_2\}\) be the partition of \({\cal H}\) such that: \({\cal H}_1\) is formed by those members of \({\cal H}\) which enjoy [the assumptions of] of P3, while \({\cal H}_2\) is formed by those members of \({\cal H}\) with \(|T_1(a)| = 1\) [and \(|T_2(a)| = 0\) by P2], i.e., by those members of \({\cal H}\) which are \(edges\) of \(G\).

Let us focus on \(G’ = G[N_2 \cup N_3 \cup N_4 \cup \ldots]\).

Let us assume that all vertices of \(G’\) are uncolored: the goal is to check if vertices of \(G’\) can be colored/partitioned into \(white\) vertices, i.e. those in \(D\), and \(black\) vertices, i.e. those in \(V(G) \setminus D\), with the constraint that all vertices of \(N_2\) have to be black.

In particular the following forcing rules hold:

(R1) if vertex \(w\) is colored white, then all vertices of \(N(w)\) should be colored black;

(R2) if vertex \(b\) is colored black and if \(b\) has a neighbor \(w\) colored white, then all vertices of \(N(b) \setminus \{w\}\) should be colored black;

(R3) if \(h_1,h_2\) are the vertices of a member of \({\cal H}_2\) and if \(h_1\) is colored black (respectively, white), then \(h_2\) should be colored white (respectively, black).

Then one can execute the following Pre-procedure whose running time bound can be estimated as \(O(n^2)\) time: (1) assign color black to all vertices of \(N_2\); (2) for each member \(H\) of \({\cal H}_1\), assign to each vertex of \(H\) the forced color according to P3 ; (3) apply iteratively rules (R1), (R2), (R3).

Assumption 1: Let us assume that the above pre-procedure does not lead to a contradiction [else \(G\) has not the sought e.d.s. \(D\)].

At this point one can just focus on the following set and family:

\(N’_2 = \{x \in N_2 : x\) is adjacent to no white vertex [by the pre-procedure]\(\}\),

\({\cal H}’_2 = \{H \in {\cal H}_2 :\) vertices of \(H\) are still uncolored [by the pre-procedure]\(\}\).

Let \(V({\cal H}’_2)\) denote the vertex set of members of \({\cal H}’_2\).

P4. Graph \(G\) has the sought e.d.s. \(D\) if and only if \(G[N’_2 \cup V({\cal H}’_2)]\) has an e.d.s. say \(D_{\text{peripheral}}\) with \(N’_2 \cap D_{\text{peripheral}} = \emptyset\).

Proof. The proof is similar to that of P5 of Lemma 3.4. \(\square\)

The following property P5 is just a technical parenthesis which will be useful later.

P5 Let \(Q\) be a connected component of \(G[N’_2 \cup V({\cal H}’_2)]\), such that \(Q\) contains exactly one vertex say \(x\) of \(N’_2\) [in particular, \(x\) is a cutset by construction, and is colored black by the pre-procedure]. Then one can easily determine an “optimal” coloring of \(Q\) (i.e. of \(Q \setminus \{x\}\)).

Proof. The proof is similar to that of P6 of Lemma 3.4. \(\square\)

P6. One can compute \(D^*_{\text{peripheral}} \in\) arg min\(\{w(D_{\text{peripheral}}) : D_{\text{peripheral}}\) is an e.d.s. of \(G[N’_2 \cup V({\cal H}’_2)]\) with \(N’_2 \cap D_{\text{peripheral}} = \emptyset\}\) in \(O(n^2)\) time.

Proof. First let us recall that (by construction and by definition of e.d.s.) each vertex of \(N’_2\) has to be covered by some vertex of \(V({\cal H}’_2)\). Without loss of generality, to our aim, let us assume that \(G[N’_2 \cup V({\cal H}’_2)]\) is connected.

Then let us recall the aforementioned induced \(C_{10}\) in \(G[N_0 \cup N_1]\), of vertex-set \(C\), say of vertices \(c_1,\ldots,c_{10}\), and say of edges \(c_1c_2, \ldots, c_{10}c_1\).

Claim 1. One can assume (without loss of generality) that:

• (i) each vertex of \(N’_2\) contacts at least two members of \({\cal H}’_2\);

• (ii) each vertex of \(N’_2\) is of Type 1 [i.e. is adjacent to some vertex of \(C\)].

Proof. Proof of (i): In fact let \(x \in N’_2\): if \(x\) contacts no member of \({\cal H}’_2\), then the sought e.d.s. \(D^*\) does not exist; if \(x\) contacts exactly one member of \({\cal H}’_2\), then the neighbor of \(x\) (in such a member) would be forced to be in \(D^*\), so that one could iteratively apply rules (R1), (R2), (R3), and then reduce (again) the problem to a subset of \(N’_2\) and to a subfamily of \({\cal H}’_2\).

Proof of (ii): Let \(x \in N’_2\). Let us recall that, according to the above, \(x\) can be either of Type 1 or of Type 2. By statement (i) vertex \(x\) contacts at least one [actually more than one] member say \(H\) of \({\cal H}’_2\).

Let us observe that \(x\) can not be of Type 2. By contradiction assume that \(x\) is of Type 2. Then \(x\) is adjacent to a vertex \(y \in N_1 \setminus C\), which is adjacent to a vertex \(z \in N_0 \cap C\); then, since \(G\) is bipartite (\(C_4,C_6,C_8\))-free, the two vertices of \(H\), \(x,y\) and nine vertices of \(C\) induce a \(P_{13}\), a contradiction. \(\square\)

Claim 2. For any member \(H\) of \({\cal H}’_2\), of vertices say \(h_1,h_2\), one has that: \(h_1\) is adjacent to at most one vertex of \(N’_2\), and \(h_2\) is adjacent to at most one vertex of \(N’_2\).

Proof. By symmetry let us just prove that \(h_1\) is adjacent to exactly one vertex of \(N’_2\): in particular, let us assume that \(h_1\) has a neighbor \(x \in N’_2\) (else the claim is proved), and by Claim 1 let us assume that \(x\) is adjacent to \(c_1\) (without loss of generality by symmetry).

Then let us show that no vertex \(x’ \in N’_2\), different to \(x\), is adjacent to \(h_1\): in fact if \(x’\) is adjacent to \(h_1\), then, since \(G\) is bipartite \((C_4,C_6,C_8)\)-free, \(x’\) is nonadjacent to \(x\) and is nonadjacent to any vertex of \(C\); but this is not possible since, by Claim 1-(ii), \(x’\) is of Type 1. \(\square\)

Notation. Let us say that a pair \(\{x,y\} \subseteq N’_2\) is a complementary pair of \(N’_2\) if there is a member \(H\) of \({\cal H}’_2\), of vertices say \(h_1,h_2\), such that \(x\) is adjacent to \(h_1\) while \(y\) is adjacent to \(h_2\); in particular, in this case, let us say that \(\{x,y\}\) covers \(H\), and that \(H\) is covered by \(\{x,y\}\). Notice that: \(x\) is nonadjacent to \(h_2\) (by Claim 2), \(y\) is nonadjacent to \(h_1\) (by Claim 2), \(x\) is nonadjacent to \(y\) (since \(G\) is \(C_4\)-free). Furthermore in what follows, as an agreement, let us assume that any complementary pair \(\{x,y\}\) of \(N’_2\) is an ordered pair with \(x \in V_1(G)\) and \(y \in V_2(G)\).

Claim 3. Let \(\{x,y\}\) form a complementary pair of \(N’_2\). Then \(x\) and \(y\) are adjacent respectively to opposite vertices of \(G[C]\), i.e., \(x\) is adjacent to \(c_i\) while \(y\) is adjacent to \(c_{i+5}\) for some \(i \in \{1,\ldots,5\}\).

Proof. Let us assume that \(x\) is adjacent to \(c_1\) without loss of generality by symmetry. Then \(y\) is nonadjacent to \(c_2\) [else \(h_1,h_2,y,c_2,c_1,x\) induce a \(C_{6}\)], \(y\) is nonadjacent to \(c_{10}\) [similarly by symmetry], \(y\) is nonadjacent to \(c_4\) [else \(h_1,h_2,y,c_4,c_3,c_2,c_1,x\) induce a \(C_{8}\)], \(y\) is nonadjacent to \(c_{8}\) [similarly by symmetry], so that \(y\) is adjacent to \(c_6\). \(\square\)

Claim 4. Let \(\{x,y\}\) form a complementary pair of \(N’_2\). Let \(Q\) be the connected component of \(G[N’_2 \cup V({\cal H}’_2)]\) containing \(x\) and \(y\). Then \(V(Q) \cap N’_2 = \{x,y\}\).

Proof. Since \(\{x,y\}\) forms a complementary pair of \(N’_2\), let \(H\) be a member of \({\cal H}’_2\), of vertices say \(h_1,h_2\), such that \(x\) is adjacent to \(h_1\) while \(y\) is adjacent to \(h_2\). Let us assume that \(x\) is adjacent to \(c_1\) without loss of generality by symmetry.

By contradiction assume that \(V(Q) \cap N’_2 \subset \{x,y\}\). Then by construction there is a vertex \(z \in N’_2\) and a member \(K\) of \({\cal H}’_2\), of vertices say \(k_1,k_2\), such that (without loss of generality by symmetry) \(x\) is adjacent to \(k_1\) while \(z\) is adjacent to \(k_2\). Note that by Claim 2: \(y\) is nonadjacent to \(k_2\); \(z\) is nonadjacent to \(h_2\). Furthermore, by Claim 3, \(y\) and \(z\) are adjacent to \(c_6\). Then \(x,h_1,h_2,y,c_6,z,k_2,k_1\) induce a \(C_8\), a contradiction. \(\square\)

Claim 5. Let \(Q\) be a connected component of \(G[N’_2 \cup V({\cal H}’_2)]\). Then \(Q\) contains at most two vertices of \(N’_2\); in particular, if \(Q\) contains two vertices say \(x,y\) of \(N’_2\), then \(\{x,y\}\) is a complementary pair of \(N’_2\).

Proof. If \(Q\) contains two vertices say \(x,y\) of \(N’_2\), then by Claim 2 and since \(Q\) is connected, \(\{x,y\}\) is a complementary pair of \(N’_2\). Thus, by Claim 4, one obtains Claim 5. \(\square\)

Now let us conclude the proof of P6.

For that let us describe the following possible solution method based on Claim 5.

For every connected component \(Q\) of \(G[N’_2 \cup V({\cal H}’_2)]\):

:: if \(Q\) contains just one vertex of \(N’_2\), say \(x\), then one can easily determine an “optimal” coloring of \(Q\) according to P5;

:: if \(Q\) contains just two vertices of \(N’_2\), say \(x\) and \(y\), then \(\{x,y\}\) is a complementary pair of \(N’_2\); then \(Q\) contains say \(\ell\) edges, in particular, say \(\ell^*\) edges are covered by \(\{x,y\}\); then:

:: :: if \(\ell^* \geq 3\), then \(G\) has not the sought \(D_{\text{peripheral}}\); in fact according to (R3), in this case either \(x\) or \(y\) should be adjacent to two white vertices, and thus a contradiction would arise to the definition of e.d.s.;

:: :: if \(\ell^* = 2\), then there are two edges (\(h_1,h_2\)) and (\(k_1,k_2\)), such that \(x\) is adjacent to \(h_1\) and \(k_1\) while \(y\) is adjacent to \(h_2\) and \(k_2\); then there just two possible colorings of \(Q\): if the color of \(h_1\) is fixed as white, then one can determinate the color of all other vertices of \(Q\) by forcing rules (R1)-(R2)-(R3) [in fact, vertex \(h_2\) and \(k_1\) would be black, then \(k_2\) would be white; further, for each of the remaining (\(\ell -2\)) edges, the vertex which is adjacent to \(x\) or to \(y\) will be black while the other vertex will be white]; if the color of \(h_1\) is fixed as black, then \(h_2\) would be white, and then one can refer to the previous case by symmetry; summarizing one can easily determine an “optimal” coloring of \(Q\);

:: :: if \(\ell^* = 1\), then there is just one edge (\(h_1,h_2\)), such that \(x\) is adjacent to \(h_1\) while \(y\) is adjacent to \(h_2\); then each of the remaining (\(\ell – 1\)) edges is contacted by exactly one vertex in \(\{x,y\}\); let \({\cal E}_x\) the family of such edges contacted by \(x\) and let \({\cal E}_y\) the family of such edges contacted by \(y\); if the color of \(h_1\) is fixed as white, then: vertex \(h_2\) would be black, for each edge in \({\cal E}_x\) the vertex adjacent to \(x\) would be black (and thus the other vertex would be white), finally at this point there are just \(|{\cal E}_y|\) possible colorings for the edges in \({\cal E}_y\) (in fact exactly one neighbor of \(y\) should be white); if the color of \(h_1\) is fixed as black, then \(h_2\) would be white, and then one can refer to the previous case by symmetry; summarizing one can easily determine an “optimal” coloring of \(Q\).

Then \(-\) apart from the case in which a contradiction arises, namely, in which a connected component \(Q\) contains a complementary pair of \(N’_2\) that covers at least three members of \({\cal H}’_2\) \(-\) the sought e.d.s. \(D^*_{\text{peripheral}}\) is the union of all such “local” minimum e.d.s. for each connected component \(Q\) of \(G[N’_2 \cup V({\cal H}’_2)]\).

The above solution method is correct by Claim 1, Claim 2, and Claim 4. The running time bound can be estimated as \(O(n^2)\).

This completes the proof of P5. \(\square\)

This completes the proof of Lemma 4.3. \(\square\)

Lemma 4.4. Step (12.3.1.1) can be executed in constant time.

Proof. The proof is similar (but shorter) to that of Lemma 4.3.

As a preliminary let us remark that Step (12.3.1.1) is executed only if \(G\) is (\(C_6,C_8,C_{10}\))-free: thus let us assume that \(G\) is (\(C_6,C_8,C_{10}\))-free.

By definition of Algorithm WED, let us fix any induced \(C_{12}\) of \(G\) of vertex-set \(C\), say of vertices \(c_1,\ldots,c_{12}\) and of edges \(c_1c_2, \ldots, c_{12}c_1\), and let us fix any member (\(C’,{\cal D}(C’)\)) of \({\cal F}_C\) and any e.d.s. \(D’ \in {\cal D}(C’)\).

Then let us show that \(D^{**} \in\) arg min\(\{w(D) : D\) is an e.d.s. of \(G\), with \(D \cap C’ = D’\}\) can be computed in polynomial time. For convenience let us denote \(D^{**}\) as \(D\).

Let us recall the notation \(N_h(D’) = \{v \in V(G): dist(v,D’) = h\}\), for \(h \geq 1\), for the distance levels with respect to \(D’\).

Notation: for brevity let us write \(D’ = N_0\) and \(N_h(D’) = N_h\) for \(h \geq 1\).

Let us observe that by construction one has \(C \subseteq N_0 \cup N_1\).

Let us observe that \(D \cap (N_1 \cup N_2) = \emptyset\) by definition of e.d.s., so that each vertex of \(N_2\) has to be covered by some vertex of \(N_3\), that is, of \(D \cap N_3\): in particular each vertex of \(N_3\) which is isolated in \(G[N_3 \cup N_4 \cup \ldots]\) is forced to be in \(D\).

For any vertex \(x \in N_2\), let us say that \(x\) is: of Type 1 if \(x\) is adjacent to some vertex of \(C\); of Type 2 if \(x\) is not of Type 1 and is adjacent to a vertex of \(N_1\) which is adjacent to a vertex of \(N_0 \cap C\) [that is of \(D’ \cap C\)]; of Type 3 if \(x\) is not of Type 1 and is adjacent to a vertex of \(N_1\) which is adjacent to a vertex of \(N_0 \setminus C\) [that is of \(D’ \setminus C\)]. Let us observe that, by definition of e.d.s., \(x\) is of [exactly] one of the above types.

Then let us consider the following property.

P1. Each vertex of \(N_2\) is the endpoint of an induced \(P_{12}\) of \(G\) formed together with eleven vertices of \(N_0 \cup N_1\).

Proof. Let us remark that, if a vertex \(v\) not in \(C\) is adjacent to some vertex of \(C\), then \(v\) is adjacent to exactly one vertex of \(C\) [since \(G\) is bipartite (\(C_4,C_6,C_8,C_{10}\))-free]. Now let \(x \in N_2\). If \(x\) is of Type 1, then \(x\) is adjacent to exactly one vertex of \(C\), by definition of Type 1 and by the above remark. If \(x\) is of Type 2 nor of Type 3, then an induced \(P_{13}\) arises, by definition of such types and by the above remarks (i.e. no vertex of \(N_2\) is of Type 2 nor of Type 3). \(\square\)

Then P1 implies that \(N_3 = \emptyset\) [else, a vertex of \(N_2\) should be adjacent to a vertex of \(N_3\), so that an induced \(P_{13}\) would arise].

Then, by construction and by the above observations, one has that the sought e.d.s. \(D\) always exists and \(D = D’\).

This completes the proof of Lemma 4.4. \(\square\)

Then let us formalize and summarize the above as follows.

Theorem 4.5. For bipartite \((P_{13},C_4,C_6,C_8)\)-free graphs, the WED problem can be solved in \(O(n^{5})\) time.

5. Conclusions

The Weighted Efficient Set (WED) problem is a NP-hard problem and remains difficult for very restricted graph classes, such as, e.g., for claw-free graphs, for \(2P_3\)-free chordal graphs, and for bipartite planar graphs of maximum degree three and of fixed girth.

This manuscript reports a study on the WED problem for subclasses of \(C_4\)-free bipartite graphs \(-\) by the above the WED problem remains NP-hard for \(C_4\)-free bipartite graphs, even better, for \(C_4\)-free bipartite graphs which are planar and of maximum degree three.

Such subclasses concerned open directions of study according to the aforementioned results and to results on the boundedness of clique-width for bipartite graphs.

This manuscript shows that:

:: the WED problem can be solved in polynomial time for \((S_{1,2,5},C_4)\)-free bipartite graphs;

:: the WED problem can be solved in polynomial time for \((P_{10},C_4)\)-free bipartite graphs;

:: the approach introduced for for \((P_{10},C_4)\)-free bipartite graphs can be generalized, for subclasses of \((P_{t},C_4)\)-free bipartite graphs, for \(t \geq 11\); in particular the WED problem can be solved in polynomial time for the following graph classes:

• \((P_{11},C_4,C_6)\)-free bipartite graphs,

• \((P_{13},C_4,C_6,C_8)\)-free bipartite graphs,

• \((2P_{7},C_4,C_6,C_8)\)-free bipartite graphs,

• \((P_{16},C_4,C_6,C_8,C_{10})\)-free bipartite graphs,

• \((2P_{9},C_4,C_6,C_8,C_{10})\)-free bipartite graphs.

The true technical bottleneck seems to be based on the fact that an efficient dominating set of a graph intersects “somehow” each vertex (cf. e.g. [13] and [14]), each induced \(P_4\) (cf. e.g. [15]), each induced path/cycle of bounded length (cf. e.g. the results of this manuscript), and more generally each vertex subset of the graph. In particular, according to Observation 2, this fact can be a suitable starting point to define a solution method for the WED problem, once one fixes a bounded family of vertex subsets (such as, e.g., the vertices, the induced path/cycle of bounded length).

Let us observe that, with reference to the open cases introduced in Section 1 concerning bipartite graphs, the auxiliary assumption of \(C_4\)-freeness has not provided a deep progress. In particular, in the context of \(C_4\)-free bipartite graphs, the cases which remain open are the following graph classes:

• – \((P_{k},C_4\))-free bipartite graphs, \(k \geq 11\),

• – \((S_{2,2,5},C_4\))-free bipartite graphs,

• – \((S_{1,3,5},C_4\))-free bipartite graphs,

• – \((S_{1,2,6},C_4\))-free bipartite graphs.

However this auxiliary assumption has allowed to introduce new possible insights and methods which could be useful for further studies as described above.

Acknowledgments

The authors are very grateful to the referee for her/his careful report with valuable remarks and helpful suggestions. The second author would like to witness that he just tries to pray a lot and is not able to do anything without that – ad laudem Domini.