Dominating Induced Matchings for P ₇-Free Graphs in Linear Time

Abstract

Let G be a finite undirected graph with edge set E. An edge set E′⊆E is an induced matching in G if the pairwise distance of the edges of E′ in G is at least two; E′ is dominating in G if every edge e∈E∖E′ intersects some edge in E′. The Dominating Induced Matching Problem (DIM, for short) asks for the existence of an induced matching E′ which is also dominating in G; this problem is also known as the Efficient Edge Domination Problem.

The DIM problem is related to parallel resource allocation problems, encoding theory and network routing. It is ${\mathbb{NP}}$-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree three. However, its complexity was open for P _k -free graphs for any k≥5; P _k denotes a chordless path with k vertices and k−1 edges. We show in this paper that the weighted DIM problem is solvable in linear time for P ₇-free graphs in a robust way.

1 Introduction

Let G be a simple undirected graph with vertex set V and edge set E. A subset M of E is an induced matching in G if the G-distance of every pair of edges e,e′∈M, e≠e′, is at least two, i.e., e∩e′=∅ and there is no edge xy∈E with x∈e and y∈e′. A subset M⊆E is a dominating edge set if every edge e∈E∖M shares an endpoint with some edge e′∈M, i.e., if $e \cap e' \not= \emptyset$. A dominating induced matching (d.i.m. for short) is an induced matching which is also a dominating edge set.

Let us say that an edge e∈E is matched by M if e∈M or there is an e′∈M with e∩e′≠∅. Thus, M is a d.i.m. of G if and only if every edge of G is matched by M but no edge is matched twice.

The Dominating Induced Matching Problem (DIM, for short) asks whether a given graph has a dominating induced matching. This can also be seen as a special 3-colorability problem, namely the partition into three independent vertex sets A,B, and C such that G[B∪C] is an induced matching: If M⊆E is a d.i.m. of G then the vertex set has the partition V=A∪V(M) with independent vertex set A, and independent sets B,C with B∪C=V(M).

Dominating induced matchings are also called edge packings in some papers, and DIM is known as the Efficient Edge Domination Problem (EED for short). A brief history of EED as well as some applications in the fields of resource allocation, encoding theory and network routing are presented in [14] and [16].

Grinstead et al. [14] showed that EED is ${\mathbb{NP}}$-complete in general. EED remains hard for bipartite graphs [18]. In particular, [17] shows the intractability of EED for planar bipartite graphs and [10] for very restricted bipartite graphs with maximum degree 3 (the restrictions are some forbidden subgraphs). In [4], it is shown that the problem remains ${\mathbb {NP}}$-complete for planar bipartite graphs with maximum degree 3 but is solvable in polynomial time for hole-free graphs (in [9, 17], the complexity of EED was mentioned as an open problem for weakly chordal graphs which are a subclass of hole-free graphs). Some other new results for EED are given in [7]. In [9], as another open problem, it is mentioned that for any k≥5, the complexity of DIM is unknown for the class of P _k -free graphs. Note that the complexity of the related problems Maximum Independent Set and Maximum Induced Matching is unknown for P ₅-free graphs, and a lot of work has been done on subclasses of P ₅-free graphs.

In this paper, we show that for P ₇-free graphs, DIM is solvable in linear time. Actually, we consider the edge-weighted optimization version of DIM, namely the Minimum Dominating Induced Matching Problem (MDIM), which asks for a dominating induced matching M in G=(V,E) of minimum weight with respect to some given weight function ω:E→ℝ (if existent). For P ₅-free graphs, DIM is solvable in time $\mathcal{O}(n^{2})$ as a consequence of the fact that the clique-width of (P ₅,gem)-free graphs is bounded [5, 6] and a clique-width expression can be constructed in time $\mathcal{O}(n^{2})$ [3]. In [9], it is mentioned that DIM is expressible in a certain kind of Monadic Second Order Logic, and in [12], it was shown that such problems can be solved in linear time on any class of bounded clique-width assuming that the clique-width expressions are given or can be determined in the same time bound. It is well known that the clique-width of cographs (i.e., P ₄-free graphs) is at most 2 (and such clique-width expressions can be determined in linear time) and thus the DIM problem can be solved in linear time on cographs. In Sect. 4 we give a simple characterization of cographs having a d.i.m.

Our algorithm for P ₇-free graphs is based on a structural analysis of such graphs having a d.i.m. It is robust in the sense of [20] since it is not required that the input graph is P ₇-free; our algorithm either determines an optimal d.i.m. correctly or finds out that G has no d.i.m. or is not P ₇-free.

The paper is structured as follows: In Sect. 2, we give further basic notions. In Sect. 3, we develop some tools for the main algorithm, in Sect. 4 we solve the DIM problem for cographs in a simple way in linear time, in Sect. 5 we describe structural properties of a P ₇-free graph with d.i.m. and in particular discuss its distance levels with respect to an edge in a d.i.m. In Sect. 6, in procedure Check(xy), for a candidate edge xy (for which it is still unknown whether it is in a d.i.m.), it is analyzed whether its distance levels fulfill the properties of the distance levels described in Sect. 5, and one either obtains a d.i.m. or the answer that the input graph has no d.i.m. or is not P ₇-free. In Sect. 7, as another preparing step, we solve the DIM problem for P ₇-free bipartite graphs in linear time, and finally, in Sect. 8 we solve the DIM problem for P ₇-free graphs robustly in linear time. If one only aims for a polynomial time algorithm then one can carry out Check(xy) for every edge xy in G; most of the tools are only necessary for obtaining a linear time algorithm. In particular, Check(xy) is done only for a fixed number of candidate edges.

2 Further Basic Notions

Let G be a finite undirected graph without loops and multiple edges. Let V denote its vertex set and E its edge set; let |V|=n and |E|=m. For v∈V, let N(v):={u∈V∣uv∈E} denote the open neighborhood of v, and let N[v]:=N(v)∪{v} denote the closed neighborhood of v. If xy∈E, we also say that x and y see each other, and if $xy \not\in E$, we say that x and y miss each other. A vertex set S is independent (or stable) in G if for every pair of vertices x,y∈S, $xy \not\in E$. A vertex set is a clique in G if for every pair of vertices x,y∈S, x≠y, xy∈E holds. For uv∈E let N(uv):=N(u)∪N(v)∖{u,v} and N[uv]:=N[u]∪N[v]. Distinct vertices x and y are true twins if N[x]=N[y].

For U⊆V, let G[U] denote the induced subgraph of G with vertex set U, hence, the graph which contains exactly the edges xy∈E with both vertices x and y in U. Throughout this paper, subgraphs are meant to be induced subgraphs.

Let $\overline{G}$ (or co-G) denote the complement graph of G=(V,E), i.e., $\overline{G}=(V,\overline{E})$ with $xy \in \overline{E}$ if and only if x≠y and $xy \not\in E$.

Let A and B be disjoint vertex sets in G. If every vertex from A sees (misses, respectively) every vertex from B, we denote this by $A \text {\textcircled {{\footnotesize 1}}}B$ (by $A \text {\textcircled {{\footnotesize 0}}}B$, respectively).

A set H of at least two vertices of a graph G is called homogeneous if $H \not= V(G)$ and every vertex outside H is adjacent to all vertices in H or to no vertex in H. Obviously, H is homogeneous in G if and only if H is homogeneous in the complement graph $\overline{G}$.

A homogeneous set H is maximal if no other homogeneous set properly contains H. It is well known that in a connected graph G with connected complement $\overline{G}$, the maximal homogeneous sets are pairwise disjoint and can be determined in linear time (see, e.g., [19]).

A chordless path P _k (chordless cycle C _k , respectively) has k vertices, say v ₁,…,v _k , and edges v _i v _i+1, 1≤i≤k−1 (and v _k v ₁, respectively). We say that P _k has length k−1 and C _k has length k. Let K _i denote the clique with i vertices. Let K ₄−e or diamond be the graph with four vertices and five edges, say vertices a,b,c,d and edges ab,ac,bc,bd,cd; its mid-edge is the edge bc. Let W ₄ denote the graph with five vertices consisting of a C ₄ and a universal vertex (see Fig. 1). Let K _1,k denote the star with one universal vertex and k independent vertices. A star is nontrivial if it contains a P ₃ or an edge, otherwise it is trivial.

Fig. 1

K ₄, W ₄, diamond, gem, co-C ₆, domino and butterfly

For two vertices x,y∈V, let dist _G (x,y) denote the distance between x and y in G, i.e., the length of a shortest path between x and y in G. The distance of two edges e,e′∈E is the length of a shortest path between e and e′, i.e., dist _G (e,e′)=min{dist _G (u,v)∣u∈e,v∈e′}. In particular, this means that dist _G (e,e′)=0 if and only if e∩e′≠∅. For a vertex x, let N _i (x) denote the distance levels of x: N _i (x):={v∣dist _G (v,x)=i}. Thus, N ₁(x)=N(x). For an edge xy, let N _i (xy) denote the distance levels of xy: N _i (xy):={z∣dist _G (z,xy)=i}. Thus, N ₁(xy)=N(xy).

A connected component of G is a maximal vertex subset U⊆V such that all pairs of vertices of U are connected by paths in G[U]. A 2-connected component of G is a maximal vertex subset U⊆V such that all pairs of vertices of U are connected by at least two vertex-disjoint paths in G[U]. The 2-connected components are also called blocks. A vertex v is a cut-vertex of a connected graph G if G−v is disconnected. A block of G is a leaf block if it contains only one cut-vertex of G, otherwise it is an internal block. It is well known that the blocks of a graph can be determined in linear time [15] (see also [1]).

For a set $\mathcal{F}$ of graphs, a graph G is called $\mathcal{F}$-free if G contains no induced subgraph from $\mathcal{F}$. A hole is a C _k for some k≥5. A graph is hole-free if it is C _k -free for all k≥5. A graph is chordal if it is C _k -free for all k≥4. A graph is weakly chordal if it is C _k -free and $\overline {C_{k}}$-free for all k≥5.

If M is a d.i.m., an edge is matched by M if it is either in M or shares a vertex with some edge in M. Likewise, a vertex is matched if it is in V(M).

Note that M is a d.i.m. in G if and only if it is a dominating vertex set in the line graph L(G) and an independent vertex set in the square L(G)². Thus, the DIM problem is simultaneously a packing and a covering problem.

3 Some Basic Tools

3.1 Reducing the Graph by Mandatory Edges

If an edge e∈E is contained in any d.i.m. of G, we call it mandatory (or forced) in G. If an edge xy is mandatory, we can reduce the graph as follows: Delete x and y and all edges incident to x and y, and give all edges in distance one to xy the weight ∞. This means that these edges are not in any d.i.m. of finite weight in G. Let us call the resulting graph Reduced(G,{xy}).

For a set M of mandatory edges, let Reduced(G,M) denote the reduced graph by applying the reduction step Reduced(G,{xy}) to each edge xy∈M (in any order) as defined above. Obviously, this graph is an induced subgraph of G and can be determined in linear time for given G and M. Moreover:

Observation 1

Let M′ be an induced matching which is a set of mandatory edges in G. Then G has a d.i.m. M if and only if Reduced(G,M′) has a d.i.m. M∖M′.

We can also color red all vertices in distance 1 to a mandatory edge; subsequently, an edge ab with a red vertex a cannot be matched in vertex a; it has to be matched in vertex b. If also b is red then G has no d.i.m.

Reduced(G,M) is used in Algorithm P ₇-Free-DIM of Sect. 8.

3.2 Reducing Singular Triangle Leaf Blocks

In Algorithm P ₇-Free-DIM of Sect. 8, we also need another kind of reduction which is described subsequently. Let c be a cut-vertex of a leaf block consisting of the triangle abc. We call this a triangle leaf block. If c is a cut-vertex of only one such leaf block and no other leaf block has c as its cut-vertex, we call G[{a,b,c}] a singular triangle leaf block. For graph G, let G ^∗ denote the graph obtained from G by omitting all such singular triangle leaf blocks. Obviously, G ^∗ can be constructed in linear time.

There, we also need the following transformation: For every singular triangle leaf block abc with cut-vertex c and corresponding edge weights w(ab), w(ac), w(bc), let $\operatorname{Tr}(G,abc)$ be the graph with the same cut-vertex c where the triangle is replaced by a path a′b′c with new vertices a′, b′, and weights w(ab) for edge a′b′ and min(w(ac),w(bc)) for edge b′c. Let $\operatorname{Tr}(G)$ be the result of applying $\operatorname{Tr}(G,abc)$ to all singular triangle leaf blocks abc of G. Obviously, G has a d.i.m. if and only if $\operatorname{Tr}(G,abc)$ has a d.i.m., and the optimal weights of d.i.m.’s in G and $\operatorname{Tr}(G,abc)$ are the same. The only problem is the fact that the new graph is not necessarily P ₇-free when G is P ₇-free. We will apply this construction only in one case, namely when the internal blocks of G form a distance-hereditary bipartite graph; then $\operatorname{Tr}(G)$ is also distance hereditary bipartite.

3.3 Finding Some Mandatory Edges

The following observations are helpful, in particular for obtaining mandatory edges (some of them are mentioned e.g. in [4]):

Observation 2

Let M be a d.i.m. in G.

• (i) M contains at least one edge of every odd cycle C _2k+1 in G, k≥1, and exactly one edge of every odd cycle C ₃, C ₅, C ₇ of G.

• (ii) No edge of any C ₄ can be in M.

• (iii) If C is a C ₆ then either exactly two or none of the C-edges are in M.

Proof

(i): Let C be an odd cycle C _2k+1 in G, k≥1, with vertices v ₁,…,v _2k+1 and edges v _i v _i+1, i∈{1,…,2k+1} (index arithmetic modulo 2k+1). Suppose first that none of the edges of C are in M. Then the edge v ₁ v ₂ must be matched by an M-edge, say by v ₁ x, x≠v ₂,v _2k+1. Now the edge v ₂ v ₃ must be matched in v ₃ and so on, until finally the edge v _2k v _2k+1 must be matched in v _2k+1 but now two M-edges are in distance one-contradiction.

Now for C ₃’s and C ₅’s in G, obviously not more than one edge can be in M. If for a C ₇, two edges would be in M, say v ₁ v ₂∈M and v ₄ v ₅∈M then v ₆ v ₇ cannot be matched-contradiction.

(ii): If (v ₁,v ₂,v ₃,v ₄) is a C ₄ in G then if v ₁ v ₂∈M, v ₃ v ₄ is not matchable.

(iii): This condition obviously holds. □

Let us denote by butterfly (see Fig. 1) a graph of five vertices, say a,b,c,d,e, such that a,b,c and c,d,e induce a triangle. Let ab and de be the peripheral edges of the butterfly.

Observation 3

The mid-edge of any diamond in G is mandatory. Moreover, the peripheral edges of any butterfly are mandatory.

Subsequently, as a kind of preprocessing, some of the mid-edges of diamonds will be determined. Since for a linear-time algorithm it would be too time-consuming to determine all diamonds in G, we will mainly find such diamonds whose mid-edges are edges between true twins having at least two common neighbors. These are contained in maximal homogeneous sets which can be found in linear time.

3.4 Neighborhood Properties

Since the edges of any d.i.m. must have pairwise distance at least 2, we obtain by Observation 2:

Observation 4

If G has a d.i.m. then for all vertices v, G[N(v)] is cycle-free and P ₄-free.

Thus, the neighborhood of every vertex is the disjoint union of stars. Let S induce a star in N(v) containing a P ₃ with vertices a,b,c and edges ab,bc. Then G[S∪{v}] is called a diamond-star with mid-edge vb.

Observation 5

If G has a d.i.m. then for all vertices v, one of the following three cases holds:

• (i) G[N(v)] is the disjoint union of exactly one star with P ₃, and of isolated vertices. In this case, the mid-edge of the corresponding diamond-star is in M.

• (ii) G[N(v)] is the disjoint union of at least two edges and of isolated vertices. In this case, all the edges are in M.

• (iii) G[N(v)] is the disjoint union of at most one edge and of isolated vertices.

Proof

Let G have a d.i.m. M. Then by Observation 2(i), M contains an edge of every triangle, and by Observation 3, any P ₃ abc in N(v) generates a mandatory edge bv, and N(v) can not contain two stars with P ₃ since the mid-edge of any diamond-star is mandatory. Moreover, if in Case (ii), there are at least two edges in G[N(v)] then all the edges are in M. □

From the previous observations, it follows (see Fig. 1 for K ₄,W ₄, gem, and $\overline{C_{6}}$):

Corollary 1

If G has a d.i.m. then G is K ₄-free, W ₄-free, gem-free and $\overline{C_{k}}$-free for any k≥6.

3.5 Homogeneous Sets

Now we deal with homogeneous sets in G.

Proposition 1

Let G have a d.i.m. and let H be a homogeneous set in G.

• (i) If H contains an edge then N(H) is stable.

• (ii) If |N(H)|≥2 then H is either a stable set or a disjoint union of edges.

• (iii) Vertices x and y are true twins with at least two common neighbors in G if and only if they appear as an edge in a homogeneous set H with |N(H)|≥2.

Proof

Let G have a d.i.m. and let H be a homogeneous set in G.

(i): If H contains an edge then since by Corollary 1, G is K ₄-free, N(H) is stable.

(ii): If |N(H)|≥2 then by Observation 5 and Corollary 1, H must be P ₃-free, i.e., is a disjoint union of cliques. Since G is K ₄-free, these cliques are edges or vertices. If there is an edge uv in H and there is a component in H consisting of a single vertex w then by Observation 3, uv is a mandatory edge and for any a∈N(H), the edge aw cannot be matched-contradiction.

(iii): If x and y are true twins then x,y are contained in a (maximal) homogeneous set. On the other hand, if x and y with xy∈E appear in a P ₃-free homogeneous set H (by the proof of (ii), H is P ₃-free) then x and y are true twins. □

The following procedure uses Observation 5 and the fact that for a homogeneous set H with |N(H)|=1, say N(H)={z}, all connected components of H together with z are leaf blocks in G.

Procedure Hom-1-DIM(H)

Given: A non-stable homogeneous set H in G with N(H)={z}.

Task: Determine some mandatory edges or find out that G has no d.i.m.

• (a) If H contains a cycle or P ₄ then STOP-G has no d.i.m.

• (b) (Now H is a P ₄ -free forest.) If H contains at least two stars with P ₃ then STOP-G has no d.i.m.

• (c) (Now H is a P ₄ -free forest which contains at most one star with P ₃ .) If H contains exactly one star with P ₃, say P ₃ abc then M:=M∪{bz}. If another connected component of H contains an edge then STOP-G has no d.i.m.

• (d) (Now H is a P ₃ -free forest, i.e., a disjoint union of edges E′(H) and isolated vertices V′(H).) If E′(H) contains at least two edges then M:=M∪E′(H). If V′(H)≠∅ then STOP-G has no d.i.m.

• (e) (Now H is the disjoint union of exactly one edge and isolated vertices V′(H).) If there is an edge ab in H and V′(H)≠∅ then M:=M∪{az} or M:=M∪{bz} (depending on the better weight).

We postpone the discussion of the final case in (e), namely E′(H)={ab} and V′(H)=∅ (i.e., the case of a singular triangle leaf block). Since cographs can be recognized in linear time [8, 11], the following holds:

Lemma 1

Procedure Hom-1-DIM(H) is correct and can be carried out in linear time.

3.6 Checking the d.i.m. Property in Linear Time

In Sect. 8, we need the following:

Proposition 2

For a given set E′ of edges, it can be tested in linear time whether E′ is a d.i.m., and likewise, whether E′ is an induced matching.

Proof

For E′⊆E, in an array of all vertices in V, count the number m(x) of appearances of each vertex of V in the edges of E′ by going through all edges in E′ once.

• (1) Two edges of E′ intersect if and only if one of the vertices appears in more than one edge of E′, i.e., if there is a vertex x with m(x)≥2.

• (2) Two edges of E′ have distance 1 if and only if for an edge xy∈E∖E′, both m(x)≥1 and m(y)≥1.

• (3) E′ is dominating if and only if for each edge xy∈E, m(x)≥1 or m(y)≥1.

Obviously, steps (1)–(3) can be done in time $\mathcal{O}(n+m)$. The first two steps are checking whether E′ is an induced matching. □

3.7 Identifying a C ₃, C ₅, C ₇ or P ₇ in a Non-bipartite Graph

In Algorithm P ₇-Free-DIM of Sect. 8, we need the following:

Procedure Find-Odd-Cycle-Or-P ₇

Given: A connected non-bipartite graph G.

Task: Determine an odd cycle C ₃, C ₅, C ₇ or a P ₇ in G.

• (a) Choose a vertex x and determine the distance levels N ₁,N ₂,… with respect to x. If N ₆≠∅ then STOP-G contains a P ₇.

• (b) If there is an edge ab∈E in N ₁ then xab is a C ₃. Else N ₁ is stable.

• (c) If there is an edge ab∈E in N ₂ then either abc is a C ₃ for a common neighbor c∈N ₁ of a,b or for neighbors a′∈N ₁ of a and b′∈N ₁ of b, xaba′b′ is a C ₅. Else N ₂ is stable.

• (d) If there is an edge ab∈E in N ₃ then either abc is a C ₃ for a common neighbor c∈N ₂ of a,b or for neighbors a′∈N ₂ of a and b′∈N ₂ of b, and a common neighbor c∈N ₁ of a′,b′, caba′b′ is a C ₅ or for neighbors a″∈N ₁ of a′ and b″∈N ₁ of b′, xa″b″a′b′ab is a C ₇. Else N ₃ is stable.

• (e) If there is an edge ab∈E in N ₄ then either abc is a C ₃ for a common neighbor c∈N ₃ of a,b or for neighbors a′∈N ₃ of a and b′∈N ₃ of b, and a common neighbor c∈N ₂ of a′,b′, caba′b′ is a C ₅ or for neighbors a″∈N ₂ of a′ and a‴∈N ₁ of a″, xa‴a″a′abb′ is a P ₇. Else N ₄ is stable.

• (f) (Now N ₅ must contain an edge, otherwise G is bipartite.) For an edge ab in N ₅, let a ₄ denote a neighbor of a in N ₄ and let a _i−1∈N _i−1 denote a neighbor of a _i ∈N _i , i=2,3,4. Then either a ₄ ab is a C ₃ or xa ₁ a ₂ a ₃ a ₄ ab is a P ₇.

Obviously, the following holds:

Lemma 2

Procedure Find-Odd-Cycle-Or-P ₇ is correct and runs in linear time.

4 DIM for Cographs in Linear Time

Recall that G is a cograph if and only if G is P ₄-free. It is well known that a graph is a cograph if and only if its clique-width is at most 2. Thus, for solving the DIM problem on cographs, one could use the clique-width argument (as mentioned in the Introduction). Here we give a simple direct way. By Corollary 1, the following holds:

Corollary 2

If G has a d.i.m. and $\overline{G}$ is not connected then G is a cograph.

For the subsequent characterization of cographs with d.i.m., we need the following notion:

G is a super-star if G contains a universal vertex u such that G[V∖{u}] is the disjoint union of a star and a stable set. Note that every super-star has a d.i.m. M, namely if the star contains a P ₃ with central vertex c then M consists of the single edge uc, and if the star consists of only one edge ab, then {ua} and {ub} are both d.i.m.’s, and the choice of an optimal d.i.m. depends on the edge weights. If there is no edge in G[V∖{u}] then any edge uv is a d.i.m., and the choice of an optimal d.i.m. depends on the edge weights.

For cographs having a d.i.m., there is the following simple characterization:

Proposition 3

A connected cograph G has a d.i.m. if and only if it is either a super-star or the join $G=G_{1} \text {\textcircled {{\footnotesize 1}}}G_{2}$ of a disjoint union of edges G ₁ and a stable set G ₂.

Proof

Let G be a connected cograph with a d.i.m. M. Then, since G is K ₄-free, $G=G_{1} \text {\textcircled {{\footnotesize 1}}}G_{2}$ for some triangle-free (i.e., bipartite) subgraphs G ₁ and G ₂.

Case 1. G ₁ (or G ₂) contains only one vertex; without loss of generality say V(G ₁)={u}.

Then by Observation 5, G ₂ is the disjoint union of at most one star with P ₃, of edges and vertices. If exactly one of the connected components of G ₂ contains a P ₃ then this component is a star, say with central vertex c, and uc∈M. Now the other components of G ₂ must be isolated vertices since in every triangle, exactly one edge is in M. This shows that in this case, G is a super-star, and an optimal d.i.m. can be chosen as described above.

If none of these connected components contain P ₃ then the connected components of G ₂ are edges and vertices. If at least two such edges exist then all the connected components are edges, otherwise there is no d.i.m. This corresponds to the second case in Proposition 3.

If exactly one of the connected components is an edge, say ab, and all the others are vertices then ua and ub are possible d.i.m.’s. This is again a special super-star. If there is no edge in G ₂ then G is simply a star.

Case 2. G ₁ and G ₂ contain at least two vertices.

If none of G ₁, G ₂ contains an edge then if both G ₁ and G ₂ contain at least two vertices, every edge is in a C ₄ and therefore not in M-contradiction.

If G ₁ contains an edge then by Proposition 1(i), G ₂ is edgeless, and by Proposition 1(ii), G ₁ is a disjoint union of edges. In this case, the uniquely determined d.i.m. of G is the set of edges in G ₁.

Conversely, it is easy to see that any super-star has a d.i.m., and likewise any join of a disjoint union of edges and a stable set has a d.i.m. □

Corollary 3

Cographs with d.i.m. can be recognized in linear time.

The following uses Proposition 3:

Procedure Cograph-DIM

Given: A connected cograph G with edge weights.

Task: Decide whether G has a d.i.m. and if yes, determine an optimal d.i.m. of G.

• (a) Check whether G is either a super-star or the join of a disjoint union of edges and a stable set. If yes then G has a d.i.m. as described above, otherwise STOP-G has no d.i.m.

5 Structure of P ₇-free Graphs with Dominating Induced Matching

Throughout this section, let G=(V,E) be a connected P ₇-free graph having a d.i.m. Recall that if M is a d.i.m. of G then the vertex set V has the partition V=I∪V(M) with independent vertex set I. We suppose that xy∈M is an edge in an induced P ₃ of G and consider the distance levels N _i =N _i (xy), i≥1, with respect to the edge xy (see Fig. 2). Note that every edge of a hole C ₅, C ₆, or C ₇ is part of an induced P ₃. For triangles abc, this is not fulfilled if a and b are true twins. However, according to Proposition 1, true twins with at least two common neighbors will lead to mandatory edges as mid-edge of a diamond (or K ₄ if there is an edge in their neighborhood), and true twins a,b with only one common neighbor c form a leaf block abc which will be treated by procedure Hom-1-DIM or will be temporarily omitted by constructing G ^∗ (as described in Sect. 3.2) and looking for an odd cycle in G ^∗. Thus we can assume in this section that xy is an edge in M which is part of an induced P ₃.

Fig. 2

Distance levels

5.1 Distance Levels with Respect to an M-Edge xy

We refer to the partition V=V(M)∪I with d.i.m. M and independent set I. Since we assume that xy∈M, clearly, N ₁⊆I and thus:

$$ N_1 \mbox{ is a stable set}. $$

(1)

Moreover, no edge between N ₁ and N ₂ is in M. Since N ₁⊆I and all neighbors of vertices in I are in V(M), we have:

$$ N_2 \mbox{ is the disjoint union of some edges and isolated vertices}. $$

(2)

Let M ₂ denote the set of edges in N ₂ and let S ₂ denote the set of isolated vertices in N ₂; N ₂=V(M ₂)∪S ₂. Obviously:

$$ M_2 \subseteq M \quad\mbox{and}\quad S_2 \subseteq V(M). $$

(3)

Let M ₃ denote the set of M-edges with one endpoint in S ₂ (and the other endpoint in N ₃).

Since xy is contained in a P ₃, i.e., there is a vertex r such that y,x,r induce a P ₃, we obtain some further properties:

$$ N_5=\emptyset. $$

(4)

Proof of (4)

If there is a vertex v ₅∈N ₅ then there is a shortest path (v ₅, v ₄, v ₃, v ₂, v ₁), v _i ∈N _i , i=1,…,5, connecting v ₅ and a neighbor v ₁ of x or y. If v ₂ r∈E then v ₅,v ₄,v ₃,v ₂,r,x,y is a P ₇, and if v ₂ is nonadjacent to any personal neighbor of x with respect to y then v ₅,v ₄,v ₃,v ₂,v ₁,x,r is a P ₇ or v ₅,v ₄,v ₃,v ₂,v ₁,y,x is a P ₇-a contradiction which shows (4). □

This kind of argument will be used later again-we will say that the subgraph induced by x,y,N ₁,v ₂,v ₃,v ₄,v ₅ contains an induced P ₇.

Obviously, by (3) and the distance condition, the following holds:

$$ \mbox{No edge in } N_3 \mbox{ and no edge between } N_3 \mbox{ and } N_4 \mbox{ is in } M. $$

(5)

Furthermore the following statement holds.

$$ N_4 \mbox{ is the disjoint union of edges and isolated vertices.} $$

(6)

Proof of (6)

The proof is very similar to the one of (4): Let uv be an edge in N ₄ and let w∈N ₃ see u; then w must see also v since G is P ₇-free (recall the existence of r in a P ₃ with x and y). Then N ₄ must be P ₃-free—otherwise any neighbor w∈N ₃ of a P ₃ abc in N ₄ would induce a diamond w,a,b,c and then edge wb is mandatory in contradiction to Observation 3 and condition (5). Moreover, N ₄ is triangle-free (otherwise there is a K ₄ in contradiction to Corollary 1). Then N ₄ is a disjoint union of edges and vertices which shows (6). □

Let M ₄ denote the set of edges in N ₄ and let S ₄ denote the set of isolated vertices in N ₄; N ₄=V(M ₄)∪S ₄. Note that by (4) and (5), S ₄⊆I.

Since every edge ab in N ₄ together with a predecessor c in N ₃ forms a triangle, and ac,bc∉M, by (5) necessarily:

$$ M_4 \subseteq M. $$

(7)

By Observation 2(i), in every odd cycle C ₃, C ₅ and C ₇ of G, exactly one edge must be in M. Thus, (5) implies:

$$ N_3 \cup S_4 \mbox{ is bipartite.} $$

(8)

Note that in general, N ₃ is not a stable set.

5.2 Matching the S ₂-Vertices by N ₃-Neighbors

By the previous conditions and in particular, by (5), we obtain:

$$ M= \{xy\} \cup M_2 \cup M_3 \cup M_4. $$

(9)

From the algorithmic point of view, determining M ₂ and M ₄ for a candidate edge xy is easy since these are the edges in N ₂ (N ₄, respectively) if (2) ((6), respectively) is fulfilled for xy. The crucial point, however, is the problem how to match the vertices in S ₂ by edges with neighbors in N ₃, and the remaining part of this section is dealing with the conditions under which this is possible.

Let T _one:={t∈N ₃:|N(t)∩S ₂|=1}, and T _two:={t∈N ₃:|N(t)∩S ₂|≥2}. Note that if uv is an edge with u∈T _two then $uv \not\in M$ and uv must be matched by an M-edge at v since it cannot be matched at u because of the distance condition; in particular, T _two⊆I.

In general, (5) will lead to some forcing conditions since the edges in N ₃ and between N ₃ and N ₄ have to be matched. If an edge uv∈E cannot be matched at u then it has to be matched at v—in this case, as described later, we color the vertex v green if it has to be matched by an M ₃ edge. (For an algorithm checking the existence of a d.i.m., it is useful to observe that if vertices in distance one get color green then no d.i.m. exists.)

Let S ₃:=(N(M ₂)∩N ₃)∪(N(M ₄)∩N ₃)∪T _two. Then by definition, S ₃⊆N ₃, and obviously S ₃⊆I holds. Furthermore, since S ₄⊆I, one obtains:

$$ S_3 \cup S_4 \mbox{ is a stable set.} $$

(10)

Let $T^{*}_{\mathrm{one}} := T_{\mathrm{one}} \setminus S_{3}$. Then $N_{3}=S_{3} \cup T^{*}_{\mathrm{one}}$ is a partition of N ₃. In particular, $T^{*}_{\mathrm{one}}$ contains the M-mates of the vertices of S ₂. Recall that M ₃ denotes the set of M-edges with one endpoint in S ₂ (and the other endpoint in $T^{*}_{\mathrm{one}}$).

Let S ₂={u ₁,u ₂,…,u _k }, and let $T_{i} := T_{\mathrm{one}}^{*} \cap N(u_{i})$, i=1,…,k. Then $T_{\mathrm{one}}^{*}=T_{1} \cup\cdots\cup T_{k}$ is a partition of $T_{\mathrm{one}}^{*}$. The following condition is necessary for the existence of M ₃:

$$ \mbox{For all } i = 1,\ldots,k, T_i \neq\emptyset, \mbox{ and exactly one vertex of } T_i \mbox{ is in } V(M_3). $$

(11)

Recall that by Observation 5, G[T _i ] is the disjoint union of at most one star with P ₃, and of edges and isolated vertices. Furthermore, by Observation 5, G[T _i ] cannot contain two edges, i.e., the following statement holds for all i=1,…,k:

$$ G[T_i] \mbox{ is the disjoint union of isolated vertices and at most one star $Y_{i}$ with an edge.} $$

(12)

Proof of (12)

Assume that there are two edges, say ab and a′b′, in T _i . Then by Observation 5, ab and a′b′ are mandatory, but u _i ∈V(M)-contradiction. □

Assume that T _i contains the star Y _i with an edge.

$$ \mbox{For all } i,j = 1,\ldots,k, i \neq j, Y_i \mbox{ sees no vertex of } T_j. $$

(13)

Proof of (13)

Let $t'_{i}t''_{i}$ be an edge of Y _i . By contradiction assume that a vertex t _j ∈T _j , i≠j, is adjacent to Y _i , say t _j sees $t''_{i}$. Then, since by (8), $G[T^{*}_{\mathrm{one}}]$ is triangle-free, t _j is nonadjacent to $t'_{i}$, and now $x,y,N_{1},u_{j},t_{j},t''_{i},t'_{i}$ induce a subgraph of G containing a P ₇. □

5.3 Pairing the N ₃-Neighborhoods of Vertices in S ₂

Claim 1

For all i=1,…,k, there is at most one j with j≠i such that a vertex in T _i sees a vertex in T _j .

Proof of Claim 1

By contradiction assume that there are two indices j≠h such that some vertices in T _i see vertices in T _j and T _h .

Case 1. If there is a vertex t _i ∈T _i which sees a vertex t _j ∈T _j and t _h ∈T _h then, since there is no triangle in N ₃, t _j misses t _h , and then x,y,N ₁,u _h ,t _h ,t _j ,t _i induce a subgraph of G containing a P ₇ (recall the existence of a P ₃ with x,y and vertex r∈N ₁).

Case 2. Thus, assume that there are two vertices $t'_{i},t''_{i} \in T_{i}$ such that $t'_{i}$ sees a vertex t _j ∈T _j and $t''_{i}$ sees a vertex t _h ∈T _h . Clearly, by (13), $t'_{i}t''_{i} \notin E$, and by Case 1, $t'_{i}t_{h} \notin E$, $t''_{i}t_{j} \notin E$. Moreover, t _j t _h ∉E, otherwise we are in Case 1 again. Now $u_{j},t_{j},t'_{i},u_{i},t''_{i},t_{h},u_{h}$ induce a P ₇-contradiction. □

Let us say that T _i sees T _j if there are vertices in T _i and T _j which see each other. Now by Claim 1, for every i=1,…,k, T _i either sees no T _j , j≠i, and in this case let us say that T _i is isolated, or sees exactly one T _j , j≠i, in which case we say that T _i and T _j are paired.

Claim 2

If T _i and T _j are paired then G[T _i ∪T _j ] contains at most two components among the four following ones: Y _i (defined above), Y _j (defined above), $Y'_{i}$ which is a star with center in T _i and the other vertices in T _j , $Y'_{j}$ which is a star with center in T _j and the other vertices in T _i ; in particular, at most one from {Y _i ,Y _j } does exist.

Proof of Claim 2

By (11) and since each edge of G must be matched by M, G[T _i ∪T _j ] contains at most two components among the above ones. By (12) and (13) it is enough to focus on the possible components of G[T _i ∪T _j ] with vertices in both T _i and T _j . In particular, by (12) each such component is a star with center in T _i (in T _j , respectively) and the other vertices in T _j (in T _i , respectively); if any of such stars contains a P ₃ then its center c belongs to V(M ₃) (in fact otherwise, c would have two neighbors in T _i or in T _j , and such neighbors should belong to V(M), a contradiction to (11)); then if such stars exist and contain P ₃, their centers belong to T _i and T _j respectively; then one obtains the stars described in the claim. Finally, since G[T _i ∪T _j ] contains at most two components, by (13) and by definition of paired sets one has that at most one from {Y _i ,Y _j } does exist. □

Claims 1 and 2 are useful tools to detect M ₃. Observe that:

• (i) if a vertex t _i ∈T _i sees a vertex of S ₃∪S ₄, then u _i t _i ∈M ₃;

• (ii) if a vertex t _i ∈T _i is the center of the star Y _i or $Y'_{i}$ (in case of paired sets), with a P ₃ then u _i t _i ∈M ₃.

Let us say that a vertex t _i ∈T _i is green if it enjoys one of the above two conditions (i), (ii). Then the following statement holds for all i=1,…,k:

$$ G[T_i] \mbox{ contains at most one green vertex, say } t_i^* $$

(14)

and

$$ G\bigl[T_i \setminus N\bigl(t_i^* \bigr)\bigr] \mbox{ is edgeless.} $$

(15)

6 Procedure Check(xy)

In our algorithm P ₇-Free-DIM in Sect. 8, we carry out a fixed number of times the subsequent

Procedure Check(xy)

Given: A (candidate) edge xy which is in an induced P ₃ of G.

Task: Determine a minimum weight d.i.m. M of G with xy∈M or unsuccessfully STOP, i.e., return a proof that G has no d.i.m. M with xy∈M or G is not P ₇-free.

• (a) Determine the distance levels N ₁,N ₂,… with respect to xy.

• (b) Check if all the conditions (1), (2), (4), (6), (8), (10)–(13) of Sects. 5.1 and 5.2 are fulfilled. If one of them is not fulfilled then unsuccessfully STOP. Otherwise, set M:={xy}∪M ₂∪M ₄. If S ₂=∅, then STOP and return M.

• (c) Check if Claim 1 of Sect. 5.3 holds. If not, then unsuccessfully STOP. Otherwise classify the T _i sets into isolated ones and paired ones.

• (d) Check if Claim 2 of Sect. 5.3 holds. If not, then unsuccessfully STOP.

• (e) Color green every vertex t _i of T _i such that either t _i sees a vertex of S ₃∪S ₄ or t _i is the center of the star Y _i or $Y'_{i}$ (in case of paired sets) with Y _i or $Y'_{i}$ containing P ₃.

• (f) Check if conditions (14)–(15) of Sect. 5.3 hold. If not, then unsuccessfully STOP.

  Notation. For any subset $T'_{i}$ of any T _i set introduced in Sect. 5.3, let us say that a vertex $t'_{i}$ is a best vertex in $T'_{i}$ if $w(u_{i}t'_{i}) \leq w(u_{i}t''_{i})$ for any $t''_{i} \in T'_{i}$.

• (g) For all isolated T _i , proceed as follows: If T _i has a green vertex $t_{i}^{*}$, then set $M: = M \cup\{u_{i}t^{*}_{i}\}$. Otherwise set $M: = M \cup\{u_{i}t'_{i}\}$ where $t'_{i}$ is a best vertex in Y _i (if Y _i does exist) or is a best vertex in T _i (otherwise).

• (h) For all paired T _i and T _j , proceed as follows.

• (h.1) If T _i and T _j have a green vertex, respectively $t^{*}_{i}$ and $t^{*}_{j}$, then: if $t^{*}_{i}$ misses $t^{*}_{j}$, and if $G[(T_{i} \cup T_{j}) \setminus(N(t^{*}_{i}) \setminus N(t^{*}_{j}))]$ is edgeless then set $M: = M \cup\{u_{i}t^{*}_{i}\} \cup\{u_{j}t^{*}_{j}\}$; otherwise unsuccessfully STOP.

• (h.2) If T _i has a green vertex $t^{*}_{i}$, and if T _j has no green vertex, then: If $G[(T_{i} \cup T_{j}) \setminus N(t^{*}_{i})]$ has at least one vertex and contains most one component (i.e., $Y'_{j}$ or Y _j ), then set $M: = M \cup\{u_{i}t^{*}_{i}\} \cup\{u_{j}t_{j}\}$ where t _j is, in this order, either the vertex in $Y'_{j} \cap T_{j}$ (if), or a best vertex in Y _j (if), or a best vertex in T _j . Otherwise unsuccessfully STOP. If T _j has a green vertex $t^{*}_{j}$, and if T _i has no green vertex, then proceed similarly by symmetry.

• (h.3) If T _j and T _j has no green vertex (according to Claim 2 and to the above, G[T _i ∪T _j ] contains isolated vertices, at most two isolated edges, and at least one isolated edge, say t _i t _j , between T _i and T _j ), then proceed as follows:

  • If there exists another edge, say pq, in T _i or T _j then: If p,q∈T _i (or p,q∈T _j ) then set M:=M∪{u _i z}∪{u _j t _j } where z is a best vertex in {p,q} (or M:=M∪{u _i t _i }∪{u _j z} where z is a best vertex in {p,q}); if p∈T _i and q∈T _j , then either set M:=M∪{u _i p}∪{u _j t _j } or set M:=M∪{u _i t _i }∪{u _j q}, depending on the best alternative.

  • Otherwise: If (T _i ∖{t _i })∪(T _j ∖{t _j })=∅, then unsuccessfully STOP; if T _i ∖{t _i }≠∅ and T _j ∖{t _j }=∅, then set M:=M∪{u _i z _i }∪{u _j t _j } where z _i is a best vertex in T _i ∖{t _i }; if T _i ∖{t _i }=∅ and T _j ∖{t _j }≠∅, then set M:=M∪{u _i t _i }∪{u _j z _j } where z _j is a best vertex in T _j ∖{t _j }; if T _i ∖{t _i }≠∅ and T _j ∖{t _j }≠∅, then either set M:=M∪{u _i z _i }∪{u _j t _j } where z _i is a best vertex in T _i ∖{t _i }, or set M:=M∪{u _i t _i }∪{u _j z _j } where z _j is a best vertex in T _j ∖{t _j }, depending on the best alternative.

• (j) STOP and return M.

Theorem 1

Procedure Check(xy) is correct and runs in linear time.

Proof

Correctness: The correctness of Procedure Check(xy) follows from the structural analysis of P ₇-free graphs with d.i.m. described in Sects. 5.1, 5.2 and 5.3.

Time bound: (a): Determining the distance levels N _i with respect to edge xy can be done in linear time, e.g. by using BFS.

(b): Likewise, concerning conditions (1), (2), (4), (6), (8), (10)–(13), we can test in linear time if N ₁ is a stable set, N ₂ is the disjoint union of edges and isolated vertices, N ₅=∅, N ₄ is the disjoint union of edges and isolated vertices and N ₃∪S ₄ is bipartite. The assignments can be done in linear time: This is obvious for M,S ₂ and S ₄. Then determine the degree of all vertices in N ₃ with respect to S ₂, and assign degree one vertices to T _one and degree ≥2 vertices to T _two. Obviously, a vertex in N ₃ which misses S ₂ has a predecessor in M ₂, and thus S ₃ and $T^{*}_{\mathrm{one}}=T_{\mathrm{one}} \setminus S_{3}$ form a partition of N ₃. Obviously, it can be checked in linear time whether N ₃∪S ₄ is a bipartite subgraph and whether S ₃∪S ₄ is a stable set.

(c)–(j): All these steps can obviously be done in linear time. □

In the other case when an edge xy is not in any P ₃, it follows that x and y are true twins, and this case will be treated by determining the maximal homogeneous sets of G.

7 DIM for P ₇-Free Bipartite Graphs in Linear Time

In this section, as a further preparing step for the general case, we show how to solve the DIM problem on P ₇-free bipartite graphs in linear time. A domino (see Fig. 1) is a bipartite graph having six vertices, say x ₁, x ₂, x ₃, y ₁, y ₂, y ₃ such that x ₁, y ₁, x ₂, y ₂, x ₃ induce a P ₅ with edges x ₁ y ₁,y ₁ x ₂,x ₂ y ₂,y ₂ x ₃ and y ₃ sees exactly x ₁,x ₂ and x ₃.

Observation 6

Let M be a d.i.m. of a bipartite P ₇-free graph B.

• (i) If C is a C ₆ in B then exactly two C-edges are in M.

• (ii) B is domino-free.

Proof

(i): Assume to the contrary that the statement is not true. Let C be a C ₆ in B with vertices v ₁,…,v ₆ and edges v _i v _i+1, i∈{1,…,6} (index arithmetic modulo 6). Then by Observation 2(iii), none of the C-edges are in M. Then since every edge of B is matched by M, exactly three vertices of C, say v ₁,v ₃,v ₅, belong to V∖V(M), while v ₂,v ₄,v ₆ belong to V(M): let $v'_{2},v'_{4},v'_{6}$ be respectively their M-mates. Then by definition of M and since B is bipartite, $v'_{2},v_{2},v_{3},v_{4},v_{5},v_{6},v'_{6}$ induce a P ₇-contradiction.

(ii): If D is a domino in B then by Observation 2(ii), the edges of the two C ₄’s of D must be matched from outside but now obviously there is a P ₇-contradiction. □

If moreover, B is C ₆-free, it is (6,2)-chordal bipartite, i.e., distance hereditary and bipartite (see e.g. [2]). In this case, DIM can be easily solved in linear time by using the clique-width argument [12, 13] since the clique-width of distance-hereditary graphs is at most 3 (and 3-expressions can be determined in linear time). We want to give a robust linear-time algorithm for P ₇-free bipartite graphs for solving the DIM problem. If a bipartite graph B is given, the algorithm either solves the DIM problem optimally or shows that there is a domino or P ₇ in B. The algorithm constructs the distance levels starting from an arbitrarily chosen vertex. Then it checks whether B is distance hereditary as in [2]. If a domino or P ₇ is found, the algorithm unsuccessfully stops, and if a C ₆ C is found, one of the pairs of opposite edges in C must be in M, say v ₁ v ₂ and v ₄ v ₅, and in this case, it is checked by Check(v ₁ v ₂) whether the distance levels starting from v ₁ v ₂ have the required properties.

For making this paper self-contained, we repeat Corollary 5 of [2]:

Corollary 4

(Bandelt, Mulder [2])

Let G be a connected graph, and let u be any vertex of G. Then G is bipartite and distance hereditary if and only if all distance levels N _k (u) are edgeless, and for any vertices v,w∈N _k (u) and neighbors x and y of v in N _k−1(u), we have

(∗):

N(x)∩N _k−2(u)=N(y)∩N _k−2(u), and further,

(∗∗):

N(v)∩N _k−1(u) and N(w)∩N _k−1(u) are either disjoint, or one is contained in the other.

We have to check level by level beginning with the largest index, whether conditions (∗) and (∗∗) are fulfilled. If one of them is violated, we obtain a hole or domino.

This leads to the following procedure for the bipartite case which includes a certifying recognition algorithm:

Procedure P ₇-Free-Bipartite-DIM

Given: A connected bipartite graph B with edge weights.

Task: Determine a d.i.m. M in B of minimum weight (if existent) or unsuccessfully STOP, i.e., find out that B has no d.i.m. or is not P ₇-free.

• (a) Choose a vertex u∈V and determine the distance levels N ₁(u),N ₂(u),… with respect to u. If N ₆(u)≠∅ then STOP-B is not P ₇-free.

• (b) For all levels N _k (u), k≤5, beginning with N ₅(u), check whether conditions (∗) and (∗∗) are fulfilled. If one of them is violated, we obtain an obstruction which is either a hole C ₈ or C ₁₀ (in the case of a C ₈ or C ₁₀ STOP-B is not P ₇-free), or a C ₆ C (in which case we have to proceed with C) or a domino-STOP-B has no d.i.m. or is not P ₇-free.

• (c) If for all levels, conditions (∗) and (∗∗) are fulfilled, B is distance hereditary and bipartite. Apply the clique-width approach for solving the DIM problem.

• (d) (Now B is not distance hereditary and C is a C ₆ in B.) For three consecutive edges ab of C, carry out Check(ab). If none of them ends successfully then STOP-B has no d.i.m., otherwise we obtain an optimal d.i.m. (among the at most three solutions).

Procedure Check(ab) assumes that ab is in a C ₆ of the bipartite graph B. In this case we have some additional properties, and the procedure could be simplified:

Let N _1a =N(a)∩N ₁(ab) (N _1b =N(b)∩N ₁(ab), respectively). Obviously, the following is a partition of N ₁(ab) if B is bipartite:

$$ N_1(ab)=N_{1a} \cup N_{1b} $$

(16)

As before, N ₁(ab) has to be stable, and N ₂(ab) is a disjoint union of edges M ₂ and isolated vertices S ₂. Since ab is in a C ₆, we have that M ₂≠∅.

Since B is P ₇-free and assuming that ab∈M, obviously:

$$ S_2 = \emptyset\quad\mbox{and}\quad N_4(ab) = \emptyset. $$

(17)

Moreover:

$$ N_3(ab) \mbox{ is edgeless.} $$

(18)

Finally, since B is P ₇-free, we obtain:

$$ \mbox{Vertices in } M_2 \mbox{ of the same color have the same neighborhood in } N_1(ab). $$

(19)

Proof of (19)

Let ef∈M ₂ and gh∈M ₂ with e and g in the same color class, and suppose that e sees x∈N _1a while g misses x. Then there is y∈N _1b such that yf∈E. Since N ₁(ab) is stable, $xy \not\in E$. Since g misses x, there is a neighbor z∈N _1a of g. Since h,g,z,a,x,e is no P ₇, ze∈E. Again, since N ₁(ab) is stable, $yz \not\in E$. If hy∈E then x,e,z,g,h,y,b is a P ₇. Thus, $hy \not\in E$ but now h,g,z,a,b,y,f is a P ₇—a contradiction which shows (19). □

Obviously, {ab}∪M ₂ is a d.i.m. of B if all conditions are fulfilled.

Lemma 3

Procedure P ₇-Free-Bipartite-DIM is correct and runs in linear time.

Proof

The correctness of the procedure follows from the structural analysis of bipartite P ₇-free graphs with d.i.m. The time bound follows from the fact that procedure Check(xy) is carried out only for a fixed number of candidate edges, and each step of the procedure can be done in linear time. □

8 The DIM Algorithm for the General P ₇-Free Case

In the previous chapters we have analyzed the structure of P ₇-free graphs having a d.i.m. Now we are going to use these properties for an efficient algorithm for solving the DIM problem on these graphs.

Algorithm P ₇-Free-DIM

Given: A connected graph G=(V,E) with edge weights.

Task: Determine a d.i.m. in G of finite minimum weight (if existent) or find out that G has no d.i.m. or is not P ₇-free.

• (a) If G is bipartite then carry out procedure P ₇-Free-Bipartite-DIM.

• (b) (Now G is not bipartite.) If G is a cograph then apply procedure Cograph-DIM. If G is not a cograph but $\overline {G}$ is not connected then STOP-G has no d.i.m.

• (c) (Now G is neither bipartite nor a cograph, and $\overline{G}$ is connected.) Let M:=∅. Determine the maximal homogeneous sets H ₁,…,H _k of G. For all i∈{1,…,k} do the following steps (c.1), (c.2):

• (c.1) If |N(H _i )|=1 and H _i is not a stable set then carry out procedure Hom-1-DIM(H _i ).

• (c.2) In the case when |N(H _i )|≥2 and H _i is not a stable set then check whether N(H _i ) is stable and H _i is a disjoint union of edges; if not then STOP-G has no d.i.m., otherwise, for all edges xy in H _i , let M:=M∪{xy}.

• (d) If M≠∅ then construct G′=Reduced(G,M) as described in Sect. 3.1.

• (e) For every connected component C of G′, do:

  • (e.1) If C is bipartite then carry out procedure P ₇-Free-Bipartite-DIM for C. Otherwise:

  • (e.2) Construct C ^∗ as described in Sect. 3.2 (where the singular triangle leaf blocks are temporarily omitted) and carry out Find-Odd-Cycle-Or-P ₇ for C ^∗.

  • (e.3) If an odd cycle C ₃, C ₅ or C ₇ is found, carry out Check(ab) in the component C for all (at most seven) edges of the odd cycle. Add the resulting edge set to the mandatory edges from steps (c.1), (c.2), respectively.

  • (e.4) If however, C ^∗ is bipartite then with procedure P ₇-Free-Bipartite-DIM for C ^∗, find out if the procedure unsuccessfully stops or if there is a C ₆ in C ^∗; in the last case, do Check(ab) in the component C for all edges of the C ₆.

  • (e.5) Finally, if C ^∗ is distance hereditary bipartite, construct $\operatorname{Tr}(C)$ as described in Sect. 3.2 (the omitted triangle leaf blocks are attached as P ₃’s and the resulting graph is distance hereditary bipartite) and solve DIM for this graph using the clique-width argument (or using the linear time DIM algorithm for chordal bipartite graphs given in [4]).

• (f) Finally check once more whether M is a d.i.m. of G. If not then G has no d.i.m., otherwise return M.

Theorem 2

Algorithm P ₇-Free-DIM is correct and runs in linear time.

Proof

Correctness: The correctness of the algorithm follows from the structural analysis of P ₇-free graphs with d.i.m. In particular, if G is bipartite (a cograph, respectively) then procedure P ₇-Free-Bipartite-DIM (Cograph-DIM, respectively) correctly solves the DIM problem.

If $\overline{G}$ is not connected, i.e., $G = G_{1} \text {\textcircled {{\footnotesize 1}}}G_{2}$ for some nonempty G ₁,G ₂ and G has a d.i.m. then by Corollary 2, G must be a cograph.

For the maximal homogeneous sets H ₁,…,H _k of G, there are two cases |N(H _i )|=1 or |N(H _i )|≥2. By Proposition 1 and Lemma 1, steps (c.1) and (c.2) are correct, and G can be correctly reduced by using the obtained set M of forced edges. Since in procedure Hom-1-DIM, in the last case, the corresponding singular triangle leaf blocks are postponed, in the reduced graph, every odd cycle contains only edges in P ₃’s. Thus, it is correct to apply Check(ab) for the edges of some odd cycle in the (non-bipartite) reduced graph. Finally one has to add the postponed edges and solve the DIM problem on these graphs.

Time bound: Step (a) can be done in linear time since procedure P ₇-Free-Bipartite-DIM takes only linear time. Step (b) can be done in linear time since it can be recognized in linear time whether G is a cograph (see [8, 11]) and procedure Cograph-DIM can be done in linear time. Step (c) can be done in linear time since modular decomposition can be done in linear time and finds the maximal homogeneous sets [19]. There is only a linear number of true twins, and the corresponding reduced graph can be determined in linear time.

In the reduced graph G′=Reduced(G,M), procedure Check(xy) is carried out only for a fixed number of edges xy, and the procedures P ₇-Free-Bipartite-DIM and Find-Odd-Cycle-Or-P ₇ can be done in linear time. □

9 Conclusion

In this paper we solve the DIM problem in linear time for P ₇-free graphs which answers an open question from [9]. Actually, we solve the minimum weight DIM problem in a robust way in the sense of [20]: Our algorithm either solves the problem correctly or finds out that the input graph has no d.i.m. or is not P ₇-free. This avoids to recognize whether the input graph is P ₇-free; the known recognition time bound is much worse than linear time. It is a challenging open question whether for some k, the DIM problem is ${\mathbb{NP}}$-complete for P _k -free graphs.