Decomposing Semi-complete Multigraphs and Directed Graphs into Paths of Length Two

Abstract

A $P_3$-decomposition of a graph is a partition of the edges of the graph into paths of length two. We give a simple necessary and sufficient condition for a semi-complete multigraph, that is a multigraph with at least one edge between each pair of vertices, to have a $P_3$-decomposition. We show that this condition can be tested in strongly polynomial-time, and that the same condition applies to a larger class of multigraphs. We give a similar condition for a $P_3$-decomposition of a semi-complete directed graph. In particular, we show that a tournament admits a $P_3$-decomposition iff its outdegree sequence is the degree sequence of a simple undirected graph.

1 Introduction

A decomposition of a graph (multigraph, directed graph) G is a collection of edge-disjoint subgraphs $G_1, G_2, \ldots , G_k$ of G, whose union is G. A decomposition in which each subgraph $G_i$ is isomorphic to a fixed graph H, is called an H-decomposition of G.

Decompositions of complete graphs have been studied for a long time, in the context of combinatorial designs. A $(v, k, \lambda )$-design is a collection of k element subsets of a v-element set, such that every pair of distinct elements is contained in exactly $\lambda$ subsets. A $(v, k, \lambda )$-design can be easily seen to be equivalent to a $K_k$-decomposition of the $\lambda$-complete multigraph of order v, in which there are $\lambda$ edges between each pair of vertices. Perhaps the most significant result on designs is Wilson’s theorem [13], that if $v, k, \lambda$ satisfy some obvious necessary divisibility conditions, and if v is large enough for fixed k and $\lambda$, then a $(v, k, \lambda )$-design always exists.

There are many other problems on decomposition of complete graphs. The Oberwolfach problem [1] was to characterize 2-regular graphs of order $2n+1$ that decompose $K_{2n+1}$. An old conjecture of Ringel [11] states that $K_{2n+1}$ has a T-decomposition for any tree T with n edges. Another conjecture of Gyarfas [6] states that if $T_1, T_2,\ldots ,T_n$ are trees with $T_i$ having i edges, then $K_{n+1}$ has a decomposition into subgraphs $G_1, G_2,\ldots ,G_n$ such that $G_i$ is isomorphic to $T_i$, for $1 \le i \le n$.

On the other hand, for general graphs, Dor and Tarsi [4] showed that the H-decomposition problem is NP-Complete for any fixed graph H having a connected component with at least 3 edges. Brys and Lonc [2], showed that H-decomposition is polynomial-time solvable for graphs H in which each component has at most 2 edges.

In this paper, we consider decomposition problems for semi-complete multigraphs and directed graphs. A multigraph or directed graph is said to be semi-complete if there is at least one edge between every pair of vertices. These are more general than complete graphs, but with sufficient structure that may enable decomposition problems to be solved efficiently. In particular, we consider the simplest non-trivial decomposition problem, that of decomposing a graph into paths of length 2.

A $P_3$-decomposition of an arbitrary graph or directed graph can be found in polynomial-time by a reduction to the perfect matching problem in the line graph. In the case of multigraphs also, the problem can be solved in strongly polynomial-time by a reduction to the b-matching problem. However, the line graphs may contain $\varOmega (n^2)$ vertices and $\varOmega (n^3)$ edges for a graph with n vertices. This gives an inefficient algorithm, although it runs in polynomial-time. In the case of simple undirected graphs, a much simpler characterization is given by the classical theorem of Kotzig [9], that a $P_3$-decomposition exists iff each connected component has an even number of edges. No such simple condition is known for multigraphs or directed graphs, although some partial results can be found in [3, 10].

We give a simpler condition, not involving the line graph, and a faster algorithm to decide whether a given semi-complete multigraph or directed graph has a $P_3$-decomposition. In the case of multigraphs, we show that the same condition applies to a larger class of multigraphs, characterized by forbidden induced subgraphs. Our hope is that studying the simplest case of $P_3$-decomposition would help in generalizing some of the classical results on decomposition of complete graphs to semi-complete multigraphs and directed graphs.

2 Multigraphs

We consider a multigraph of order n to be the complete graph on n vertices with a non-negative integer weight $w_{ij}$, called the multiplicity, assigned to each edge ij. A multigraph is said to be semi-complete if $w_{ij} > 0$ for all edges ij. We call it semi-complete to emphasize the fact that the multiplicities of edges could be different, although all are positive. The size of a multigraph is the sum of the weights of all edges in the complete graph. The degree of a vertex u in a multigraph G is the sum of weights of edges incident with u, and is denoted $d_G(u)$. The underlying simple graph of a multigraph is obtained by deleting all edges of weight 0 and ignoring weights of other edges.

Let $\mathcal {P}_3$ denote the set of all paths of order 3 in the complete graph. For an edge ij, let $\mathcal {P}_{ij}$ denote the set of paths of order 3 that contain the edge ij. A $P_3$-decomposition of a multigraph is a function $f :\mathcal {P}_3 \rightarrow \mathbb {N}$, such that for every edge ij,

$$ \sum _{P \in \mathcal {P}_{ij}} f(P) = w_{ij}. $$

A matching M in a graph is a collection of disjoint edges. For any matching M, let N(M) denote the set of edges in the graph that are not in M but have an endpoint in common with some edge in M. For any subset S of edges, let V(S) denote the subset of vertices that are incident with some edge in S. Let $w(S) = \sum _{e \in S} w_e$ denote the sum of weights of edges in S.

Lemma 1

A semi-complete multigraph G of even size has a $P_3$-decomposition iff for every matching S in G, $w(N(S)) \ge w(S)$.

Proof

Suppose G has a $P_3$-decomposition f. Any path of order 3 that contains an edge in S must contain an edge in N(S). Also, it cannot contain any other edge in S. Therefore,

$$w(S) = \sum _{e \in S} w_e = \sum _{e \in S} \left( \sum _{P \in \mathcal {P}_e} f(P)\right) \le \sum _{e \in N(S)} \left( \sum _{P \in \mathcal {P}_e} f(P)\right) = w(N(S).$$

To prove the converse, we use Tutte’s 1-factor theorem [12]. Consider a new graph L(G) which contains $w_{ij}$ distinct vertices $V_{ij}$ corresponding to each edge ij in G. For every path i, j, k in G, all vertices in $V_{ij}$ are adjacent to all vertices in $V_{jk}$. It is then easy to see that G has a $P_3$-decomposition iff L(G) has a perfect matching. Given a perfect matching in L(G), let f(i, j, k) be the number of vertices in $V_{ij}$ that are matched to vertices in $V_{jk}$, and vice versa.

A subset S of vertices in L(G) is said to be compatible if for all edges ij in G, either $S \cap V_{ij} = \emptyset$ or $S \cap V_{ij} = V_{ij}$. We identify a compatible subset S of vertices in L(G) by the subset E(S) of edges ij in G for which $S \cap V_{ij} = V_{ij}$.

If G does not have a $P_3$-decomposition, then L(G) does not have a perfect matching. By Tutte’s theorem, there exists a subset S of vertices in L(G) such that $O(L(G)-S) > |S|$, where $O(L(G)-S)$ is the number of connected components of odd order in $L(G)-S$. Let S be a minimal such set. Note that since all vertices in $V_{ij}$ have the same neighbors in L(G), S must be a compatible set. If for some vertices $x,y \in V_{ij}$, $x \in S$ but $y \not \in S$, then $O(L(G)-(S \setminus \{x\}))$ $\ge O(L(G)-S)-1$, contradicting the minimality of S. Similarly, we can assume that the vertex set of any non-trivial component of $L(G)-S$, and the set of all isolated vertices in $L(G)-S$, are compatible sets. Let A be the set of isolated vertices in $L(G)-S$. Then E(A) is a matching in G.

Let C be the vertex set of any non-trivial component of $L(G)-S$. No edge in E(A) can have an endpoint in common with an edge in E(C). If an edge in E(S) has both endpoints in V(E(C)), we can remove all vertices corresponding to this edge from S, and get a smaller set that violates Tutte’s condition, contradicting the minimality of S. Thus we can assume that E(C) contains all edges in the subgraph of G induced by V(E(C)).

Now if there are two non-trivial components in $L(G)-S$, say with vertex sets $C_1, C_2$, then $V(E(C_1))$ and $V(E(C_2))$ must be disjoint sets. Since G is semi-complete, there exists an edge in G joining a vertex in $V(E(C_1))$ to a vertex in $V(E(C_2))$. This edge must be in E(S). Again, removing vertices corresponding to this edge from S gives a smaller set violating Tutte’s condition.

Therefore $L(G)-S$ contains at most one non-trivial component containing vertices corresponding to edges in some induced subgraph of G. The number of odd components in $L(G)-S$ is therefore at most $w(E(A))+1$ while every edge in E(S) is incident with some vertex in V(E(A)). Thus $|S| = w(N(E(A)))$. Since G has even size and hence L(G) has even order, we must have $O(L(G)-S) \ge |S| +2$, which implies $w(E(A))+1 \ge w(N(E(A))) + 2$, or $w(E(A)) > w(N(E(A)))$, giving the required matching.    $\square$

While Lemma 1 gives a characterization of semi-complete multigraphs that have a $P_3$-decomposition, it cannot be directly used to get an efficient algorithm to test whether a given semi-complete multigraph has such a decomposition. We strengthen Lemma 1 to get a more efficient strongly polynomial-time algorithm. We show that instead of checking the condition in Lemma 1 for all matchings S, it is sufficient to check it for all matchings that are contained in any fixed maximum weight matching.

Theorem 1

Let G be a semi-complete multigraph of even size and let M be a matching with maximum weight in G. G has a $P_3$-decomposition iff for every subset of edges $S \subseteq M$, $w(N(S)) \ge w(S)$.

Proof

The necessity of the condition follows from Lemma 1. To prove sufficiency, suppose for contradiction, that the condition is satisfied but G does not have a $P_3$-decomposition. By Lemma 1, there exists a matching S in G such that $w(N(S)) < w(S)$. Let S be a minimal such matching. We claim that S must be contained in M. If not, let $A = S \setminus M$ and $B = S \cap M$. By minimality of S, we must have $w(N(B)) \ge w(B)$, and hence $w(N(A) \setminus N(B)) < w(A)$. Let $M_1 = M \cap (N(A) \setminus N(B)$. Then $(M \setminus M_1) \cup A$ is a matching in G of weight greater than M, a contradiction.    $\square$

Theorem 1 can be used to get an $O(n^4\log n)$ time algorithm to test whether a given semi-complete multigraph has a $P_3$-decomposition. First we find an arbitrary maximum matching M in the weighted complete graph, using Edmond’s algorithm [5]. This takes $O(n^3)$ time. Now construct a flow network as follows. For every edge $a \in M$ add a node $v_a$, and for every edge $b \not \in M$, add a node $v_b$. If edges a and b have a common endpoint, add a directed edge from $v_a$ to $v_b$ with infinite capacity. Add a source node s and directed edges from s to $v_a$ of capacity $w_a$, for all edges $a \in M$. Add a sink node t, and edges from $v_b$ to t of capacity $w_b$, for all edges $b \not \in M$. Now, it is easy to verify that G satisfies the condition in Theorem 1 iff this network has a maximum flow value of w(M). Since the network has $O(n^2)$ nodes and edges, the maximum flow can be found in $O(n^4\log n)$ time [8].

We give another simple application of Lemma 1.

Theorem 2

Any semi-complete multigraph of order n, even size and maximum multiplicity at most $n-2$, is $P_3$-decomposable. The bound on the multiplicity is the best possible.

Proof

If G is such a multigraph, then for any matching S of size k in G, $w(S) \le k(n-2)$. However, $w(N(S)) \ge |N(S)| = 2k(k-1) + 2k(n-2k) = 2k(n-k-1)$. Since $k \le n/2$, we have $w(S) \le w(N(S))$, and Lemma 1 implies G has a $P_3$-decomposition. If n is even, and G has a perfect matching with edges of weight $n-1$, and all other edge weights are 1, then G does not have a $P_3$-decomposition.    $\square$

It is possible that similar results could hold for other decompositions of semi-complete multigraphs, with different bounds on the multiplicity.

We next show that Theorem 1 applies to a much larger class of multigraphs. Note that if Lemma 1 holds for a class of multigraphs, then so does Theorem 1, since the proof of the theorem does not use any properties of the multigraph G.

Let $\mathcal {F}$ be the set of graphs with exactly 2 connected components, each of which is either an odd cycle or the claw $K_{1,3}$. Let $\mathcal {G}$ be the set of graphs that do not contain any induced subgraph isomorphic to any graph in $\mathcal {F}$.

Theorem 3

Let G be any multigraph of even size whose underlying simple graph belongs to the class $\mathcal {G}$. Let M be any maximum weight matching in G. Then G has a $P_3$-decomposition iff for any subset $S \subseteq M$, $w(N(S)) \ge w(S)$.

Proof

We only need to show that Lemma 1 holds for this class of multigraphs. We follow the same argument, and choose a set S of vertices in L(G) such that $O(L(G)-S) > |S|$, the number of non-trivial components in $L(G)-S$ is minimum, and subject to this, S is minimal. Following the same argument, each non-trivial component of $L(G)-S$ contains vertices corresponding to edges in some induced subgraph of G. Suppose there are 2 non-trivial components with vertex sets $C_1, C_2$. If there is an edge with positive weight in G joining some vertex in $V(E(C_1))$ to a vertex in $V(E(C_2))$, we can use the same argument and get a smaller set S with the same properties.

Suppose there is no such edge and let $G_1$ and $G_2$ be the underlying simple graphs of the subgraphs of G induced by $V(E(C_1))$ and $V(E(C_2))$, respectively. If both $G_1$ and $G_2$ are either not bipartite or contain a vertex of degree at least 3, then we can find an induced subgraph of $G_1 \cup G_2$ that is in $\mathcal {F}$, contradicting the assumption. Otherwise, at least one of $G_1, G_2$, say $G_1$, is bipartite and has maximum degree 2. Then the edges in $E(C_1)$ can be partitioned into two matchings. Take the matching with smaller weight, and add vertices in L(G) corresponding to edges in it to the set S. The vertices corresponding to edges in the other matching will now be isolated vertices. The new set S will still satisfy $O(L(G)-S) > |S|$, but will have fewer non-trivial components in $L(G)-S$, contradicting the original choice of S. Therefore there must exist an edge in E(S) joining a vertex in $V(E(C_1))$ to a vertex in $V(E(C_2))$, and we can complete the argument as before.    $\square$

Note that the graphs in the family $\mathcal {F}$ themselves satisfy the hypothesis of Theorem 3 but do not have a $P_3$-decomposition. They are thus the minimal graphs for which Theorem 3 fails. The class $\mathcal {G}$ of graphs includes some well-known classes such as complete multipartite graphs, split graphs, complements of planar graphs etc. Theorem 3 is analogous to an old result of Fulkerson et al. [7], who proved an Erdos-Gallai type condition for the existence of an f-factor in certain multigraphs. In particular, the forbidden induced subgraphs in their case were graphs with two disjoint odd cycles, while we need the claw also in this case. Although their proof is quite different, it can also be proved using our approach, by reducing the f-factor problem to a perfect matching problem in the standard way. Again, for this class of multigraphs, the condition for existence of an f-factor can be checked in strongly polynomial-time, using network flows, as shown in [7].

3 Directed Graphs

A directed graph without self-loops is said to be semi-complete if for every pair of distinct vertices u, v, at least one of the ordered pairs (u, v), (v, u) is an edge in the graph. A directed graph is said to be oriented if for any two vertices u, v, at most one of (u, v), (v, u) is an edge in the graph. An oriented semi-complete directed graph is called a tournament.

The outdegree of a vertex u in a directed graph is the number $d^+(u)$ of vertices v such that (u, v) is an edge in the graph. The underlying multigraph M(D) of a directed graph D is obtained by ignoring the directions of edges in the directed graph. If both (u, v) and (v, u) are edges in D, then the edge uv has multiplicity two in M(D). We will denote the edges in M(D) also by the same ordered pair as the corresponding edge in D, although these are undirected edges. A $P_3$-decomposition of a directed graph is a partition of the edges of the graph into directed paths of length two.

Lemma 2

An oriented graph D has a $P_3$-decomposition iff there exists a spanning subgraph H of M(D), such that $d_H(u) = d^+(u)$ for all vertices u in D.

Proof

Suppose D has a $P_3$-decomposition. Let H be the spanning subgraph of M(D) defined by the set of edges (u, v), such that u, v, w is a path in the decomposition for some vertex w. For every edge (u, v) in the directed graph, either (u, v) is an edge in H, or there exists a vertex w such that w, u, v is a path in the decomposition, in which case (w, u) is an edge in H. Thus the degree of u in H is exactly $d^+(u)$.

Conversely, suppose there exists such a subgraph H. For any vertex u, consider the set of incoming edges (w, u) that are in H. If there are k such edges, there must be exactly k outgoing edges (u, v) that are not edges in H. We pair up these edges arbitrarily to form paths of length two in the directed graph. Doing this for all vertices u, gives a $P_3$-decomposition of D.    $\square$

Corollary 1

A tournament has a $P_3$-decomposition iff its outdegree sequence is the degree sequence of a simple undirected graph.

Corollary 1 gives simple necessary and sufficient conditions, in terms of the outdegree sequence, for a tournament to have a $P_3$-decomposition. These also give a simple $O(n^2)$ time algorithm to decide whether a given tournament has a decomposition.

Lemma 2 does not hold if the directed graph has 2-cycles, since pairing an arbitrary incoming edge with an arbitrary outgoing edge may lead to a 2-cycle rather than a path of length 2. However, we show that for semi-complete directed graphs, this can be avoided in almost all cases.

A pair of vertices u, v is said to be an isolated pair in a semi-complete directed graph if both (u, v) and (v, u) are edges in the graph, and for every vertex $w \not \in \{u,v\}$, (u, w), (w, v) are edges but (w, u), (v, w) are not edges in the graph. Clearly, a semi-complete directed graph with an isolated pair of vertices cannot have a $P_3$-decomposition, since the edge (u, v) is not contained in any path of length two.

Theorem 4

Let D be a semi-complete directed graph that is not a complete directed graph on 3 vertices and does not contain an isolated pair of vertices. Then D has a $P_3$-decomposition iff there exists a spanning subgraph H of M(D) such that for every vertex u, $d_H(u) = d^+(u)$.

Proof

One part of the theorem follows in the same way as Lemma 2. If there exists a $P_3$-decomposition of D, take the first edge of each path in the decomposition in H. This satisfies the required property.

Conversely, suppose there exists such a subgraph H. As before, consider the set of incoming edges (w, u) at a vertex u that are in H. If there are at least two such edges, we can pair them with outgoing edges at u that are not in H, such that (w, u) is not paired with (u, w), for any vertex w. The pairs of edges thus form paths of length two. The only case when this is not possible is if for some vertex w, (w, u) is the only incoming edge at u in H, and (u, w) is the only outgoing edge not in H. In this case we call u a bad vertex and w the partner of u.

Choose a subgraph H of M(D) such that $d_H(u) = d^+(u)$ for all vertices u, and the number of bad vertices is minimum. If there are no bad vertices, we get a $P_3$-decomposition.

Let u be a bad vertex with partner w. If we replace the edge (w, u) by the edge (u, w) in H, in the resulting graph $H'$, u is no longer a bad vertex. The choice of H implies that w must be a bad vertex in $H'$. Thus all outgoing edges at w must be in H, and no incoming edge at w is in H.

Case 1. Suppose there is a vertex v such that for some $x \in \{u,w\}$, both (x, v) and (v, x) are edges in D. Without loss of generality, assume $x = u$. Then the edge (u, v) must be in H, but (v, u) is not in H. Replacing (u, v) by (v, u) in H, gives a subgraph $H'$ with the same degrees as H. Since u is not a bad vertex in $H'$, v must be a bad vertex in $H'$. Let $v'$ be the partner of v in $H'$. Then $v' \ne u$ and suppose $v' \ne w$. If the edge $(u,v')$ is present in D, it must also be present in H and $H'$, since u is a bad vertex in H with partner w. But this contradicts the fact that $v'$ is the partner of v in $H'$. A similar argument holds if the edge $(v',u)$ is present in D. Since D is semi-complete, one of these must hold, and we get a contradiction. Therefore, the only remaining possibility is that $v' = w$. Thus $\{u,v,w\}$ induces a complete directed graph in D and a triangle in H. Note that for all $x \in \{u,v,w\}$ and $y \not \in \{u,v,w\}$, any edge (x, y) in D must be in H, while (y, x) will not be in H.

Case 1.1. Suppose there is a vertex $x \in \{u,v,w\}$ such that for some vertex $y \not \in \{u,v,w\}$, both (x, y) and (y, x) are edges in D. Consider the subgraph $H'$ obtained by replacing the edge (x, y) by (y, x) and choosing edges (p, x), (x, q), (p, q) for $\{p,q\} = \{u,v,w\} \setminus \{x\}$. In this subgraph, none of $\{u,v,w\}$ can be a bad vertex, since none of them has exactly one incoming edge in $H'$. Also, y cannot be a bad vertex. If both (y, p) and (y, q) are edges in D, then neither of them is in $H'$, so y must have at least two incoming edges in $H'$. If say (y, p) is not an edge in D, then (p, y) is an incoming edge at y in $H'$, and even if it is the only incoming edge in $H'$ at y, it can be paired with an outgoing edge at y that is not in $H'$. Thus $H'$ has fewer bad vertices than H, a contradiction.

Case 1.2. We may now assume that for every vertex $x \in \{u,v,w\}$ and $y \not \in \{u,v,w\}$, exactly one of the edges (x, y), (y, x) is in D. We say a vertex $y \not \in \{u,v,w\}$ is of type 1 if there are at least two edges (x, y) for $x \in \{u,v,w\}$ in D, otherwise it is of type 2.

Suppose a, b are two distinct vertices of type 1, and without loss of generality (a, b) is an edge in D. Suppose (a, b) is not in H. Since a, b are of type 1, we can find two distinct vertices $p,q \in \{u,v,w\}$ such that (p, a) and (q, b) are edges in D and also in H. Consider the subgraph $H'$ obtained by replacing the edges (p, a) and (q, b) by (a, b), and the edges in the triangle induced by $\{u,v,w\}$ by the edges (p, q), (q, p), (p, r), (q, r), where $r \in \{u,v,w\} \setminus \{p,q\}$. None of $\{u,v,w\}$ can be a bad vertex in this subgraph, and neither can any of a, b, since both have an incoming edge in the subgraph such that the oppositely directed edge is not an edge in D. Again we get a subgraph with fewer bad vertices.

A similar argument holds if there are two vertices a, b of type 2, and (a, b) is an edge in D and also in H. We can find two vertices $p, q \in \{u,v,w\}$ such that (a, p), (b, q) are edges in D but not in H. Replacing the edge (a, b) in H by the edges (a, p), (b, q), and the edges in the triangle $\{u,v,w\}$ by (p, r), (q, r), gives a subgraph with fewer bad vertices.

We may now assume that any edge in D whose endpoints are of type 1 is an edge in H, while any edge in D with endpoints of type 2 is not in H. Let A be the subset of vertices of type 1 and B the subset of vertices of type 2 and let $|A| = n_1$, $|B| = n_2$. Then

$$ \sum _{x \in B} d_H(x) = \sum _{x \in B} d^+(x) \ge 2n_2 + n_2(n_2-1)/2 = n_2(n_2+3)/2$$

since there are at least 2 outgoing edges from each vertex in B to $\{u,v,w\}$ and B itself induces a semi-complete directed graph. Since B is an independent set in H, and there are at most $n_2$ edges in H joining vertices in B to $\{u,v,w\}$, there are at least $n_2(n_2+1)/2$ edges in H joining vertices in B to vertices in A.

Suppose there are m edges in the subgraph of D induced by A. Then

$$\sum _{x \in A} d^+(x) = \sum _{x \in A} d_H(x) \ge 2m + 2n_1 + n_2(n_2+1)/2 .$$

However, a vertex in A has at most one outgoing edge to $\{u,v,w\}$, and at most $n_2$ edges to B. Therefore

$$ \sum _{x \in A} d^+(x) \le m + n_1 + n_1n_2.$$

This implies

$$ m \le n_1n_2-n_1-n_2(n_2+1)/2.$$

But since D is semi-complete $m \ge n_1(n_1-1)/2$. This implies

$$(n_1-n_2)^2 \le -n_1-n_2.$$

This is possible only if $n_1 = n_2 = 0$, which implies D is a complete directed graph of order 3.

Case 2. Now suppose that for every vertex $x \in \{u,w\}$ and $y \not \in \{u,w\}$, exactly one of the edges (x, y), (y, x) is present in D. We say a vertex $y \not \in \{u,w\}$ is of type 1 if neither (y, u) nor (y, w) are edges in D, of type 2 if both of them are edges, of type 3 if (y, w) is an edge but not (y, u), and of type 4 otherwise.

Suppose there exists a vertex a of type 3 and a vertex b of type 4. Without loss of generality, we may assume (a, b) is an edge in D. If (a, b) is in H, we can replace it by the edges (a, w) and (b, u) and delete the edge (w, u) from H, to get a subgraph $H'$ with the same degrees. None of the vertices a, b, u, w can be a bad vertex in $H'$, contradicting the choice of H. On the other hand, if (a, b) is not in H, we can replace the edges (u, a) and (w, b) by the edges (a, b) and (u, w), to get a graph with fewer bad vertices. We may therefore assume, without loss of generality, that there are no vertices of type 4.

Suppose a is a vertex of type 2 or 3 and b is a vertex of type 2. If either edge (a, b) or (b, a) is in H, we can replace it by edges (a, w) and (b, u), and delete the edge (w, u) to get a subgraph with fewer bad vertices. Similarly, suppose a is a vertex of type 1 and b is a vertex of type 1 or 3. If either edge (a, b) or (b, a) is not an edge in H, we can replace the edges (u, b), (w, a) by this edge, and add the edge (u, w) to get a subgraph with fewer bad vertices.

Let A be the set of vertices of type 1, B the vertices of type 2, and C the vertices of type 3. Let $|A| = n_1$, $|B| = n_2$, and $|C| = n_3$. As argued in the previous case,

$$ \sum _{x \in B} d_H(x) = \sum _{x \in B} d^+(x) \ge n_2(n_2+3)/2.$$

All edges in H incident with a vertex in B must also be incident with a vertex in A. Let m be the number of edges in the subgraph of D induced by A, and $m_1$ the number of edges in D with one endpoint in A and one in C. Then

$$\sum _{x \in A} d^+(x) = \sum _{x \in A} d_H(x) \ge 2m + 2n_1 + m_1 + n_2(n_2+3)/2.$$

But

$$\sum _{x \in A} d^+(x) \le m + m_1 + n_1n_2$$

which implies

$$ m \le n_1n_2 - 2n_1 - n_2(n_2+3)/2.$$

Again, since $m \ge n_1(n_1-1)/2$, we get

$$(n_1-n_2)^2 \le -3n_1-3n_2.$$

This is possible only if $n_1 = n_2 = 0$, which implies all vertices are of type 3, and thus $\{u,w\}$ is an isolated pair in D.

This completes the proof of the theorem.    $\square$

Theorem 4 also gives an efficient algorithm to test whether a given semi-complete directed graph has a $P_3$-decomposition. We can first test for isolated pairs of vertices in $O(n^2)$ time. The theorem of Fulkerson, Hoffman and McAndrew [7], gives a simple necessary and sufficient condition for a semi-complete multigraph to contain a spanning subgraph with specified degrees. Further such a subgraph can be found using network flows. The network constructed has O(n) nodes and $O(n^2)$ edges. Thus the maximum flow can be found in $O(n^3)$ time [8]. After finding the subgraph H, if it exists, we can modify it to remove bad vertices, if any. Following the proof of Theorem 4, each removal takes $O(n^2)$ time. Thus, overall, finding the $P_3$-decomposition can be done in $O(n^3)$ time.

4 Conclusion

In this paper we have given simple necessary and sufficient conditions for semi-complete multigraphs and directed graphs to have a $P_3$-decomposition. We have also shown that the conditions can be checked in strongly polynomial-time using network flows. However, we believe there should be faster algorithms to check these conditions, without resorting to general network flows.

We would also like to consider more general decomposition problems for semi-complete multigraphs and directed graphs. We conclude with a specific problem: When can a d-regular semi-complete multigraph of even order be decomposed into d perfect matchings? A necessary condition is that a subgraph induced by any subset of k vertices must contain at most $d\lfloor k/2 \rfloor$ edges. We leave open the question of whether this condition is sufficient.