A polynomial algorithm for hamiltonian-connectedness in semicomplete digraphs

A polynomial algorithm for hamiltonian-connectedness in semicomplete digraphs

JOURNALOF ALGORITHMS 13, 114-127 (1992) A Polynomial Algorithm for Hamiltonian-Connectedness in Semicomplete Digraphs JORGEN BANG-JENSEN * Depart...

885KB Sizes 2 Downloads 31 Views

JOURNALOF

ALGORITHMS

13, 114-127 (1992)

A Polynomial Algorithm for Hamiltonian-Connectedness in Semicomplete Digraphs JORGEN BANG-JENSEN

*

Department of Computer Science, Uniuersity of Copenhagen, Universitetsparken I, DK-2100 Copenhagen, Denmark YANNIS MANOUSSAKIS Uniuersite Paris XI, L.RI. Bat. 490, 91405 Orsay Cedex, France AND CARSTEN THOMASSEN Department of Mathematics, The Technical University of Denmark, Bygning 303, DK-2800 Lyngby, Denmark Received May 1990, revised November 1990

We describe a polynomial algorithm, which either finds a Hamiltonian path with prescribed initial and terminal vertices in a tournament (in fact, in any semicomplete digraph), or decides that no such path exists. o NW Academic PDSS, IX.

1. IN-~+~~DUCTI~N It is well known and easy to show that every tournament has a Hamiltonian path, and that every strongly connected tournament has a Hamiltonian cycle. The known proofs can easily be turned into polynomial time algorithms to find such a path or cycle (the fastest known algorithm for the latter problem is due to Manoussakis [33 and has time complexity O(n2), where II is the number of vertices in the tournament). The problem of deciding the existence of/finding a Hamiltonian path with prescribed initial and terminal vertex (or equivalently a Hamiltonian cycle through a prescribed arc) is considerably more complicated. Thomassen [5] proved that every four-connected tournament is Hamiltonian connected (i.e., for *Present address: Department of Mathematics and Computer Science, Odense University, Compusvej 55, DK-5230, Denmark.

114 0196-6774/92 $3.00 Copyright 0 1992 by Academic Press, Inc. All rights of reproduction in any form resewed.

HAMILTONIAN-CONNECEDNESS

115

any pair of vertices X, y there exists a Hamiltonian path from x to y). Highly non-trivial examples in [5] show that this does not extend to three-connected tournaments. Soroker [4] and others have asked if there exists a polynomial algorithm for deciding the existence of a Hamiltonian path with prescribed initial and terminal vertices in a tournament. In this paper we answer Soroker’s question in the affirmative. We believe that the following stronger result holds: CONJECTURE 1.1. For each fiied k, there exists a polynomial algorithm for deciding if there exists a Hamiltonian cycle through k prescribed arcs in a tournament.

In [l] the first and the third authors proved that the problem is NP-complete when k is not fixed. Here we prove the conjecture for k = 1. The weaker conjecture, where “Hamiltonian cycle” is replaced by “cycle” is unsolved for k 2 3, was verified for k = 2 I,, [l] (for k not fixed the problem is NP-complete, as shown in [l]).

2. TERMINOLOGY

AND PRELIMINARIES

Most of the notation is the same as in [l, 51, but for the sake of completeness we will repeat most of it here, except for the very standard notation, for which we refer to [2]. A digruph D consists of a pair V(D), E(D), where V(D) is a finite set of vertices and E(D) is a set of ordered pairs xy of vertices called urcs. In our definition of a digraph we do not allow multiple arcs in the same direction between two vertices. An oriented graph is a digraph with no cycle of length 2. If xy is an arc of the digraph D, then we say that x dominates y and we will use the notation x + y to denote this. We shall also sometimes denote the arc xy by the symbol x --j y. Similarly, if A and B are disjoint subset of V(D) and all vertices in A dominate all vertices in B, we use the notation A + B to denote this. We shall use the notation x * y to denote that there is no arc from x to y. Similarly, if A and B are disjoint subset of V(D) and no vertex of A dominates any vertex of B, we denote this by A -H B. For any subset A of I’(D) U E(D), D - A denotes the subgraph obtained by deleting all vertices of A and their incident arcs and then deleting the arcs of A still present. We write D - x instead of D - Ix] when x E V(D) u E(D). For a given vertex x of a digraph D, d+(x) (resp. d-(x)) denotes the number of vertices dominated by x in D (resp.

116

BANG-JENSEN,

MANOUSSAKIS,

AND

THOMASSEN

dominating x in 0). We also call d+(x) (resp. d-(x)) the outdegree (resp. the indegree) of x. For a given vertex x of a digraph D, I’+(x) (resp. I-(x)) denotes the set of vertices dominated by x (resp. dominating Xl. The subgraph induced by a vertex set A of D is defined as D (V(D) \A) and is denoted by D(A). We will often write x E D instead of x E V(D) or x E E(D), but the meaning will always be clear. A path is a digraph with vertex set x1,x2,. . .,xn and arc set x1 +x2, x2 +x3 , . . . , x,-i -+ x,, such that all the vertices and arcs shown are distinct. We call such a path an (xi, x,)-path and denote it by x1 + x2 -+ . . . + x,. If P is a path containing a subpath from x to y, then we let P[x, yl denote the part of P from x to y. A path in a digraph D is a Hamiltonian path if it contains all the vertices of D. An (x, y)-Hamiltonian path is a Hamiltonian path with initial vertex x and terminal vertex y. A digraph D is Hamiltonian-connected, if for any pair of vertices x, y E V(D), D has an (x, y)-Hamiltonian path. A cycle is defined analogously to the definition of a path. A k-cycle is a cycle of length k. In this paper the words path and cycle always refer to directed paths and cycles. If x, w, z are distinct vertices of a digraph D, then we use the notation Q,, =, Q.,, to denote two disjoint paths such that the first path has initial vertex x and terminal vertex z, the second path has terminal vertex w, and V(Q,, .) U V(Q.,,) = V(D). Similarly Q,, x and Q,,. denote two disjoint paths, such that the first path has initial vertex z and terminal vertex x, and the second path has initial vertex w, and V(Q,, .) U V(Q,,.) = V(D). A semicomplete digraph is a digraph with no non-adjacent vertices. A tournament is an oriented graph with no non-adjacent vertices. Thus tournaments are a special subclass of the semicomplete digraphs. A component D’ of a digraph D is a maximal subdigraph such that, for any two vertices x, y E D’, D’ contains an (x, y)-path and a (y, x)-path. A digraph D is strong if it has only one component. D is k-connected if for any set A of at most k - 1 vertices, D - A is strong. If a digraph D is not strong, then we can label its (strong) components D,, D,, . . . , D,, k 2 2, such that no vertex of Di dominates any vertex of Dj if j < i. For general digraphs this labeling is not unique, but it is so for semicomplete digraphs. Thus we can talk of the initial component of D namely D, and the terminal component D,. The remaining components (if any) are called intermediate components. Let x and y be vertices of a digraph D such that there is no arc from x to y. An (x, ybeparator of size k is a set S of k vertices of D - {x, y) that separates x from y in D, that is, there is no (x, y&path in D - S. We shall also sometimes denote S as a k-separator of x and y. A k-separator S of x and y is called triuial if either x has outdegree zero or y has indegree zero in D - S.

HAMILTONIAN-CONNECTEDNESS

117

We conclude this section with some results that will be used extensively during the rest of this paper. LEMMA 2.1. Let T be a semicompletedigraph with two distinct vertices x, y, such that there are two internally disjoint (x, y&paths P,, P2 in T. P,, Pz can be merged into one (x, y)-path P such that V(P) = V(P,) u V(P,>. P can be found in linear time. Proof. Induction on 1V( PI) U V( P,)I . Let pi, i = 1,2 denote the number of vertices of V(Pi) - (x, y). If pl, pz I 1 then the claim is easily verified. Thus we may proceed to the induction step, assuming p1 + pz 2 3. Let zi, i = 1,2, denote the successor of x’ on Pi. We may assume w.1.o.g. that zi + z2. Now apply induction to the paths P,[z,, y] and z1 + z2P2[z2, y]. The proof is easily turned into a linear time algorithm. 0 We shall often use Lemma

2.1 in the following form.

COROLLARY 2.2. Let P, = x1 -B x2 + * * * + xr and Pz = y1 + y, + . . . -+ y, be disjoint paths in a semicompletedigraph T. Zf there exist i, j, 1 I i U V(P,).

Proof. Apply Lemma 2.1 to the paths P,[xi, nj] and xi + y, + y* + xi. 0

** * +

The next theorem is a modification of Theorem 2.1 in [5]. Its proof is easily derived from the proof of the original theorem. THEOREM 2.3. Let T be a strong semicompletedigraph on at least seven vertices, and x, y distinct vertices of T. T has a Hamiltonian path with end vertices x, y, unlesseither T - x is not strong and y belongsto an intermediate component of T - x, or T - y is not strong and x belongs to an intermediate component of T - y, in which casesT has no such path.

The following result.

theorem

(Theorem

5.4 in 151) forms the basis for our

THEOREM 2.4. Let T be a two-connected semicompletedigraph and x, y distinct vertices of T. Zf T has three internally disjoint (x, y)-paths, each of length at least two, then T has an (x, y)-Hamiltonian path.

3. STRUCXJRAL

RESULTS

In this section we will prove a number of structural results, some of which will be of interest in their own right. They are used in the algorithm in the next section.

118

BANG-JENSEN,

MANOUSSAKIS,

AND

THOMASSEN

LEMMA 3.1. Let x, w, z be distinct vertices in a semicomplete digraph T, such that there exist internally disjoint (x, w>-, (x, z)-paths P,, Pz in T. Let R = T - V(P,) u UP,).

1. There are either Q,,,, V(P,)

U

Q.,, or Q,, *, Q.,, in T, unless R, ++ V(P,> \ (x1, where R, is the terminal component of T(R).

2. In the case when there is an arc from R, to V( P,) U V( Pz> \ (x} we can find one of the pairs of paths, such that the path with only one end-vertex specified has length at least one, unless I/(T) = (w, x, z). 3. Moreover, there is a polynomial paths above if they exist.

algorithm

to find one of the pairs of

If R = 0 then both pairs of paths exist. Hence we may assume Proof. that R # 0. Assume there is an arc u + v, where u E R, and v E WV,) u V(P*>)\ (xl. As sume without loss of generality that v E P,. Since u E R,, T(R) has a Hamiltonian path Q ending at u and starting at y, say. By Lemma 2.1, T(R U VCP,) \ Ix)> has a Hamiltonian path starting either at y or the successor of x on P,. This path together with Pz form the desired paths Q,, *, Q.,,. This proves 1. It is easy to verify 2 by the same argument. As the strong components of T(R) and a Hamiltonian cycle in each of them can be found in O(n2) time [3], we can find Q and Q,,,, Q.,, in O(n2) time. q LEMMA 3.2. Let T be a semicomplete digraph and x, y vertices of T, such that there exist two internally disjoint (x, y)-paths and a two-separator (u, v) of x, y in T. Supposethat u, v do not induce a two-cycle, say v * u. Let T’ denote the semicompletedigraph obtained from T, by adding the arc v + u. Then T has an (x, y)-Hamiltonian path if and only T’ has an (x, y)-Hamiltonian path.

Pro05 Suppose that not use the arc v + u assume that P uses u + u is dominated by some vertex z of P[u, yl Corollary 2.2. 0

T’ has an (x, y)-Hamiltonian path P. If P does then P is the desired path in T. Hence we may u. Since T has two internally disjoint (x, y&paths, vertex w of P(x, v 1 - (v}, and v dominates some u. Now T has an (x, y)-Hamiltonian path, by

THEOREM 3.3. Let T be a two-connected semicompletedigraph and x, y vertices of T, such that T - x and T - y are both two-connected, x * y, and neither x nor y is contained in a two-cycle. If T - (x, y} is not two-connected then T has an (x, y)-Hamiltonian path.

Proof. Suppose T - (x, y) is not two-connected. Then the assumption of the lemma implies that 3u E T - (x, y) such that T - (u, x, y) is not strong. Let T,, . . . , T,, t 2 2, denote the strong components of T -

119

HAMILTONLAN-CONNECTEDNESS

(u, X, y}. Since T - X, T - y are two-connected, each of U, X, y dominate a vertex in TI and is dominated by a vertex in T,. Let n = I V(T)1 . T-u has a Hamiltonian path xi +x2 + +*a -+x,-i, where x =x1, y = x,-i. This can be augmented to an (x, y)-Hamiltonian path unless there exists a k E (1,2,. . . , n - l} such that (xi,. . . , xk-J ++ u and u ++ IX k+l,. . . , x,-J. As T - (x, xJ is strong, u + x3. Similarly, x,-~ --$ u. If x,-~ ~6 T, we put q = n - 3. Otherwise we let q be the smallest number such that xq E T,. In any case xq-i + x,-~. Suppose first 3 < q < n - 3. Then T has the (x, y)-Hamiltonian path,

Now suppose q = 3. Since T - x is two-connected and y is not contained in a two-cycle, y is dominated by some vertex xi E T, - x,-~. Now we get the following (x, yl-Hamiltonian path: x --j x2 + xi+i + . * * --) x,-z + u +x3 + * ” + xi --, y. Suppose, finally, that q = n - 3. If xt + xq, then T has the same Hamiltonian path as in the case 3 < q < n - 3. Otherwise, t = 2 and T2 = (n,-,}. Since T is two-connected and x is not contained in a two-cycle, x dominates a vertex xj E T, - x2. Now we obtain the (x, y)-Hamiltonian path,

The next theorem generalizes Theorem

5.4 in [5].

THEOREM 3.4. Let T be a two-connected semicomplete digraph on at least 10 vertices and let x, y be vertices of T such that x * y. Suppose that T - x, T - y are both two-connected. Zf all two-separators of x, y (if any) are trivial, then T has an (x, y)-Hamiltonian path.

Proof: If there are no two-separators of x, y, then T has the desired path, by Theorem 2.4. Hence we may assume that T has a two-separator of x, y. Also, by Theorem 3.3, we may assume that T - (x, y) is two-connected. Let (u, v} be a two-separator of x, y. We may assume w.1.o.g. that I’-(y) = (u, v). By Lemma 3.2, we may assume that u, v induce a two-cycle in T. Suppose first that x dominates u or v. If x + (u, v}, then T has an (x, y)-Hamiltonian path, since T - (x, y} is two-connected and has at least eight vertices; hence by Theorem 2.3, T - (x, y) has a Hamiltonian path with end vertices u, v. Suppose w.1.o.g. x * u, x * v. If there are two internally disjoint (x, v&paths in T - (u, y}, then there are three internally disjoint (x, v&paths, each of length at least two, in T - y, which is two-connected. By Theorem 2.4, there exists an (x, vl-Hamiltonian path

120

BANG-JENSEN,

htANOUSSAKlS,

AND

THOMASSEN

in T - y, and we are done. Thus we may assume that there exists a vertex r E T - {u, U, X, y} such that {u, r) is a two-separator of X, y. Now the assumption of the theorem implies that T+(x) = {u, r). By Lemma 3.2, we may assume that u, r induce a two-cycle in T. If r +-) u then it follows from the assumption that all two-separators of x, y are trivial, that there are two internally disjoint (r, v)-paths in T {u, X, y}. Now T - {x, y) contains three internally disjoint (r, v)-paths of length at least two, and it follows from Theorem 2.4 that T contains an (x,y)-Hamiltonian path. Thus we may assume r + u. Let T’ = T - Ix, y). If T’ - r has a Hamiltonian path with end vertices u, u, then T contains the desired path. Hence we may assume, by Theorem 2.3, that either T’ - {r, u} is not strong and u belongs to an intermediate component, or T’ - {r, v) is not strong and u belongs to an intermediate component. Suppose first that the former case holds. Since T’ is two-connected, r dominates a vertex in the initial component of T’ - {r, u}, and u is dominated by a vertex of the terminal component of T’ - {r, u}. Now we easily see that T’ has an (r, u)-Hamiltonian path, and that is easily extended to an (x, y)-Hamiltonian path in T. Suppose next that T’ - {r, u} is not strong. Then we conclude, by an analogous argument, that T’ has an (r, v)-Hamiltonian path and we are done. Now suppose x * {u, u}. If there are three internally disjoint (x, (u, v&paths in T - y, then T - y contains either three internally disjoint (x, u&paths or three internally disjoint (n, u&paths of length at least two, and we conclude, by Theorem 2.4, that T has the desired path. Thus we may assume that 3, s E T - {x, y, u, U) such that {r,s} is a two-separator of X, y. Now the assumption of the theorem implies that T+(x) = (r, s}. By Lemma 3.2, we may assume that r, s induce a two-cycle in T. Suppose first that {r, sj ++ {u, v}. Then the assumption that all two-separators of X, y are trivial implies that there are three internally disjoint ((r, sj, (u, u})-paths in T - {x, y). This implies that there are three internally disjoint (w, z&paths of length at least two in T - {x, y}, where w E {r, s) and z E {u, u}. Hence we conclude, by Theorem 2.4, that T has the desired path. Thus we may assume w.1.o.g. that r + u. If s + {u, U) then it follows from the assumption that all two-separators of X, y are trivial, that there are three internally disjoint (s, {u, v&paths of length at least two in T - (x, y}, and we again deduce that T has the desired path. Hence we may assume that s + u, or s + U. Suppose first s + u. If T - (x, y, u} has a Hamiltonian path with end vertices r, s, then it is easy to see that T has the desired path. So we may assume, by Theorem 2.3, that T - (x, y, u) is not two-connected, and that either s is in an intermediate component of T - {x, y, u, r}, or r is in an intermediate component of T - (x, y, u, s). Suppose first that the former case holds; r dominates a vertex in the initial component and u is

HAMILTONIAN-CONNECDNESS

121

dominated by a vertex in the terminal component of T - {u, n, y), since T - (x, y) is two-connected. Thus we easily find an (r, u)-Hamiltonian path in T - (x, y) and we are done. Suppose next that T - (x, y, u, s) is not strong. Then we conclude, by an analogous argument, that T - (x, y} has an (s, u)-Hamiltonian path and we are done. We argue similarly if r + u and s + U. Hence we may assume that the only arcs from (r, s} to (1.4,v) are r + U, s -+ v. Let R = T - (r, s, U, v, X, y}. Suppose first that R is strong. Let u1 --) u2 + -*- -+ u, + u1 be a Hamiltonian cycle of R. There are at least two arcs in each direction between R and (u, v, r, s), since T - (x, y) is two-connected. Suppose w.1.o.g. that there is an arc from R to (s, v). If R + s then it is easy to see that T - (r, u) contains an (x, y)-Hamiltonian path, and by Lemma 2.1, the vertices r, u can be included in this path. Hence we may assume w.1.o.g. that ur + s. Now if u or r dominate u2 then we easily find an (x, y)-Hamiltonian path. (For suppose r --) u2. Then x + I + u2 + * =* + u, + u1 + s + v + y is an (x, y)-Hamiltonian path in T - U, and u can be inserted, by Corollary 2.2, since u + y). Thus we may assume that (r, U} ++ u2, which in turn, by an analogous argument, implies that we may assume (s, v} -f, u3, and generally b,ul -H Q+J r , u 1 + uzi. This implies that m is even, since otherwise {r, s, u, v) * R, contradicting the fact that T - Ix, y) is two-connected. If (r, s) + R then it is easy to find an (x, y)-Hamiltonian path: u, v each dominate a vertex of R, since T - (x, y} is two-connected, say u --+ uzi+i for some i, 1 5 i I m/2. Then x + r + u + uzi+l + * +. -+ uzi + s + v + y is the desired path. Hence we may assume w.1.o.g. that r dominates a vertex U*j+l in R. By the argument above, uzj + u, and there is an (x, y)-Hamiltonian path in T - (s, v), by Corollary 2.2. Now, by Lemma 2.1 T has the desired path. Hence we may assume that R is not strong. Let R,, . . . , R,, p 2 2, denote the strong components of R. There are at least two arcs from (r, s, U, v} to R, and at least two arcs from R, to (r,s,u,v}, since T - (x, y} is two-connected. If (r, s} +j R,, then there are arcs from each of u, v to R,. Thus if there is an arc from R, to u or v, say w.1.o.g. to v, then x + r + u + r,Pc,l,,P, r p --) v + y is an (x, y)-Hamiltonian path in T - s, where rl E R,, rP E F,, are chosen such that u --P rl, rP -+ v, and path in R. Now T has the desired path, 4 r,,Tpj is an (rl, r,)-Hamiltoman since s can be inserted, by Corollary 2.2. If R, f-, (u, v), then R, has an arc to each of r, s, and it is easy to see that T has the desired path. Hence we may assume w.1.o.g. that r --, rl for some vertex rl E R,. If T has an arc from R, to u, then we can find an (x, y)-Hamiltonian path in T - (s, v}, and then merge this with the path x + s + v + y to obtain the desired path. Otherwise T has an arc from R, to both v and s. This easily gives the desired path. This completes the proof of the theorem. 0

122

BANG-JENSEN,

MANOUSSAKIS,

AND

THOMASSEN

4. THE ALGORITHM

In this section we will prove the existence of a polynomial algorithm hereafter called the Hamiltonian algorithm for testing the existence of an (x, y)-Hamiltonian path in a semicomplete digraph T. The algorithm is recursive. In each step the algorithm either settles the problem or reduces the problem to one or more smaller problems. In the case where two or more smaller problems have to be considered, at most one of these have size more than n/2 plus a small constant. We shall start out by proving some lemmas that form the substance of the Hamiltonian algorithm. In the rest of this section T denotes a semicomplete digraph on n vertices with two specified vertices X, y and our aim is to test for a Hamiltonian path from x to y. We shall refer to this as the Hamiltonian problem. We may assume, by reversing the arc if necessary, that x ++ y. Also during the rest of this section we shall assume that neither x nor y is contained in a two-cycle. If such a cycle is created at x (resp. y) in one of the reductions below, we shall assume that the arc into x (resp. out of y) is deleted before the execution of the algorithm is continued. Clearly this has no effect on the existence of the desired path. LEMMA 4.1. Zf T is not two-connected then either the desired path exists in T, or we can reduce the problem to one or two smaller problems, such that in the latter case total size of the subproblemsis at most n + 1. Proof. If T is not strong, then T has the desired path if and only if XE TI and y E Tk, where T,,..., Tk, k 2 2, denote the strong components of T. Hence we may assume that T is strong. If T - x (resp. T - y) is not strong then T has the desired path if and only if y (resp. x) belongs to the terminal (resp. initial) component of T - x (resp. T - y). Thus we may assume that T - x, T - y are strong. Suppose now that 3.z E T - {x, y}, such that T - z is not strong. Let T,, . . . , Tk, k 2 2, denote the strong components of T - z. Suppose first that x, y belong to the same component Ti, 1 I i I k. Let T’ be the semicomplete digraph obtained from 1;: u {z} as follows: If i < k, then we add all arcs from q to z that are not already present. If i > 1 then we add all arcs from z to Ti that are not already present. Now it is easy to see that T has the desired path if and only if T’ has an (x, y)-Hamiltonian path. Suppose next that X, y belong to different components, i.e., y E q, x E I;, where 1 I i < j I k, since y + X. If j 2 i + 2 then there is no (x, yl-Hamiltonian path in T. So assume that j = i + 1. Now it is easy to see that T has the desired path if and only if there exists an (x, z)-Hamiltonian path in Ti+l U . . . U Tk U (z) and there exists a (z, y)-Hamiltonian path in {z} u TI u . . . U T. Thus we can reduce to one or two smaller problems of total size at most n + 1 (if 1 < i or j < k then one of

HAMILTONIAN-CONNECTEDNESS

123

the Hamiltonian paths above trivially exists. Hence we only have to make two recursive calls when k = 2). •I LEMMA 4.2. Suppose T is two-connected and there exists a non-trivial two-separator {u, v} of x, y. Let A, B denote a partition of T - {u, v}, such that y E A, x E B, and B ++ A. Let T’ = T(A U {u, v}), T” = T(B U (u, v}). We can reduce the Hamiltonian problem to at most four Hamiltonian problems such that one has size max(JA I, IB 1) + 2 or max(IAl, IBI) + 3 and the others (if any) have size _< min(IAl, IBI) + 3. Proof

By Lemma

3.2 we can assume that u + v and v --) u. Let

T’ = T(A U {u, v)), T” = T(B U (u, v}). By Lemma 3.1 we may assume w.1.o.g. that T’ has Q,,,, Q,,. and T” has QX,.u, Q.,,, such that Q,,. and

Q.,, both have length at least one (if the algorrthm of Lemma 3.1 instead finds Q, u, Q.,,, the four paths in T’, T” can be combined to an (x, y)Hamiltonian path in T). We may also assume that IV(T’)I I jV(T”)I, since otherwise we simply reverse all arcs and rename appropriately. Use one recursive call of the Hamiltonian algorithm to decide the existence of Q,,., Q,, y in T’, such that Q,,. has length at least one. This is done by calling the Hamiltonian algorithm, asking for a (u, y)-Hamiltonian path in the semicomplete digraph T* obtained from T’ by deleting the arc u + v and adding all arcs from A to v that are not present already. Clearly the existence of a (u, y)-Hamiltonian path in T* is equivalent to the existence of the desired paths in T’. If such paths exist in T’, then T has an (x, y)-Hamiltonian path, by our assumption above (these paths will “match” the paths known to exist in T”). Now suppose that there is no (u, y)-Hamiltonian path in T*. Use the Hamiltonian algorithm (as the second call) on the semicomplete digraph T** obtained from T’ by adding a new vertex x’, dominating u, v only. We ask for an (x’, y)-Hamiltonian path in T**. If no such path exists in path if and T **, then it is easy to see that T has an (x, y)-Hamiltonian only if there exist Q,,“, Q.,, in T”, such that Q.,, has length at least one. This can be checked (by the third call), using the Hamiltonian algorithm on a modified version of T” in a way analogous to the way we used it on path. Use the T*. Now suppose that T** has an (x’, y)-Hamiltonian Hamiltonian algorithm (for the third time) to test for a (v, y)-Hamiltonian path in T’ - u. Suppose first that there exists a (v, y)-Hamiltonian path in T’ - u. Now use the Hamiltonian algorithm (for the fourth and last time) to check for an (x, y’)-Hamiltonian path in the semicomplete digraph T+ obtained from T” by adding a new vertex y’ dominated only by u, v and adding all arcs from v to B that are not present already. If there is no (x, y’l-Hamiltonian path in T+, then it is easy to see that T has no (x, y)-Hamiltonian path. Suppose now that Tf has such a path P. If this path contains

124

BANG-JENSEN,

MANOUSSAKIS,

AND

THOMASSEN

Q,,., Q.,w such that Q.,, has length at least one, then T has the desired path, by the assumption in the beginning of this proof. Thus we may assume that P contains an (x, u)-Hamiltonian path in T” - u (if P contains an (x, v)-Hamiltonian path in T” then it follows, from the fact that T’ - u contains a (u, y)-Hamiltonian path, that T has the desired path). Now T - u contains an (x, y)-Hamiltonian path. By Lemma 2.1, T has an (x, y)-Hamiltonian path, since u dominates at least one vertex other than u on the (u, y)-Hamiltonian path in T’ - u. Suppose next that there is no (u, y)-Hamiltonian path in T’ - u. Now use the Hamiltonian algorithm to check for an (x, u)-Hamiltonian path in the semicomplete digraph T++ obtained from T” by adding all arcs from u to B that are not present already. If no such path exists in T++ then it is not difficult to see that T has no (x, y)-Hamiltonian path (the only difference from above is that we do not check for (x, u)-Hamiltonian paths in T”, since these cannot be part of any (x, y)-Hamiltonian path in T, because there is no (u, y)-Hamiltonian path in T’ - u). Now suppose that T ++ has an (x, u)-Hamiltonian path P. As in a previous argument we can assume that P contains an (x, u)-Hamiltonian path in T” - u. Let P’ be an (x’, y)-Hamiltonian path in T**. From the assumptions above, it follows that P’ contains a (u, y)-Hamiltonian path in T’. Then P’ U P - u can be combined to give an (x, y)-Hamiltonian path in T. This completes the proof of the lemma. We have used at most three recursive calls on semicomplete digraphs of size at most I V(T’)I + 1 and at most one recursive call on a semicomplete digraph of size at most I V(T”)I + 1. 0 LEMMA 4.3. Suppose that T is two-connected, 1V(T) I r 6, and all two-separators of x, y are trivial. If T - x or T - y is not two-connected, then either the desired path exists in T, or we can reduce the problem to one or two smaller problems, such that in the latter case, the total size of the subproblems is at most n + 2. Proofi Assume that T - x is not two-connected. The proof in the other case is analogous. If T - Ix, y} is not strong, then it is easy to see that T has the desired path. Thus assume that T - {x, t) is not strong, for some vertex z E T - {x, y}. Let T,, . . . , Tk, k 2 2, denote the strong components of T - {x, z). If there are no two-separators of x, y then T has the desired path, by Theorem 2.4. Hence we may assume that there exists a two-separator of x, y in T. Suppose first that y E & for some i, such that 1 _< i < k. Let T’ = T-CT, u * . * U T1:). Check whether T’ has an (x, z)-Hamiltonian path, using the Hamiltonian algorithm recursively. Suppose first that T’ does not have such a path. Let T” denote the semicomplete digraph obtained from TI u * -- U T U {x, z) by adding all arcs from T, u . . * u IT; to z that do not already exist and inverting the arc x + z if it exists in T. Now

HAMILTONIAN-CONNECTEDNESS

125

T has the desired path if and only if T” has an (x, y)-Hamiltonian path. Indeed if T has an (x, y)-Hamiltonian path x + * *. + w + * * * + w’ -2-b -** +y, where WET,U * * * U q - y and w’ E Tk and the segments x + * * + + w and z --, * * * + y span the vertex set of T”, then we can obtain an (x, y)-Hamiltonian path in T” by replacing the segment w + *. * + w’ --, z, by the arc w + z. The converse direction is proved similarly. Suppose next that T’ has an (x, z)-Hamiltonian path. Let T”’ denote the semicomplete digraph obtained from T, u * . * u T u {x, z), by adding all arcs from Tl u . * * u T to z that are not present already and inverting the arc z -+ x if it exists in T. Then as above it is easy to see that T has the desired path if and only if T’” has an (x, y)-Hamiltonian path. Thus if y @ Tk, then we can reduce the problem to two smaller problems of total size n + 2. Suppose next that y E Tk. Let (u, u} be some trivial two-separator of x, y. By Lemma 3.2, we may assume that u, u induce a two-cycle. We cannot have I’-(y) = (u, ~1, because II/CT - LX, zl>l 2 4 and u, u induce a two-cycle. Thus I’+(X) = {u, ~1. If x + z then it is easy to see that T has the desired path. Hence we may assume x ++ z. u, u E T,, since T is two-connected and u, u induce a two-cycle. Suppose first that z is dominated by some vertex of T,. In T, U (x, z} there is a Hamiltonian path P, starting in x and ending in some vertex s # z, since x dominates two vertices of T,, and z dominates at least one vertex of Tl. Now it is easy to see that T has the desired path. Thus we may assume that Tl * z. If z is dominated by some vertex of T2 U * . * u Tk- r then it is easy to see that T has an (x, y)-Hamiltonian path, because z + Tl. Hence we may assume, since T is two-connected, that 1Tkl 2 2 and 3 t E Tk - y, such that t + z. Let t, + t, + * * * + t, --) y + t1 be a Hamiltonian cycle of Tk such that ti = t for some i. Let w1 --+ . - - --f wr be a Hamiltonian path in Tl such that x + wr. Now, by Corollary 2.2, T2 U . . * U Tkel can be inserted in the path x + wi + t, --) ** * --) tivl --) t + z + wz --f . * * --) w, + ti+l --) . * * -+ t, + y. 0 Now we are ready to describe the Hamiltonian algorithm. The input to the algorithm will be assumed to be a semicomplete digraph T and two vertices X, y of T, such that x +j y. Below it is assumed that we stop as soon as the problem is settled. Otherwise we start again with a reduced version of the problem. THE

HAMILTONIAN

ALGORITHM.

1. If IV(T)1 < 9, then settle the problem in constant time. 2. If T is not two-connected, then we settle the problem, or reduce using Lemma 4.1.

126

BANG-JENSEN,

MANOUSSAKIS,

AND THOMASSEN

3. If there are no two-separators of X, y then T has the desired path, by Theorem 2.4. 4. If all two-separators of X, y are trivial, we check if T - x and T - y are two-connected. Then we settle or reduce the problem using Theorem 3.4 or Lemma 4.3. 5. Let {u, v) be a non-trivial two-separator of X, y, and let A, B form a partition of T - {u, v), such that y E A, x E B and B ++ A. (Such a partition can be found in time O(n2), by finding the vertices which in T - (u, u) can be reached from x by a directed path.) Also, if necessary, add an arc to make u, u induce a two-cycle. This does not change the problem, by Lemma 3.2. 6. Use the algorithmic version of Lemma 3.1 to find Q,, u, Q., v or Q,,,, Q.,, in T” = T(B U {u, u}), and use an analogous algorithm to find Q, y, Q,,. or Q, yFQ,,. in T’ = T(A U (u, u)). These paths exists, since T is two-connected, and the paths with one end vertex unspecified can be chosen of length at least one, since A, B both have size at least 2. 7. If these paths “match” then T has the desired paths. So suppose that we find Q,,., Q.,, in T” and Q,,,, Q,,. in T’ (rename u, u if necessary). 8. Using Lemma 4.2 we can now settle the problem. THEOREM

semicomplete nian path.

4.4. There exists an O(n5> algorithm to check whether a given digraph T with specified vertices x, y has an (x, y I-Hamilto-

Proof By the discussion above, all that is left is to prove the complexity bound of the Hamiltonian algorithm above. The only steps that involve recursion are 2, 4, and 8. The remaining steps require at most O(n4) time, corresponding to the complexity of checking all possible two-separators of X, y. Let k be a fixed constant, such that kn4 is an upper bound of the time complexity for these steps (other than 2, 4, 8). Let T(n) denote the worst-case time requirement for the algorithm on an input on n vertices. Now we see, by inspection of the proofs of Lemmas 4.1-4.3, that T(n) I 3T(x + 2) + T(n - x + 2) + kn4, where x I n/2. Solving this inequality we see that T(n) I O(n5>. q COROLLARY 4.5. There exists an O(n7> algorithm given semicomplete digraph fi Hamiltonian connected.

to check whether a

COROLLARY 4.6. There e&s an O(n7) algorithm to check whether a given semicomplete digraph T with specified vertices x, y has an (x, y )-Hamiltonian path, and which also finds such a path if it exists.

HAMILTONIAN-CONNECTEDNESS

127

proof. Denote by U’ the algorithm of Theorem 4.4. First use LXZ’to check the existence of such a path. If no such path exists, then stop. Now successively reverse all arcs out of X, and each time call JZ’ to check for an (x, y>Hamiltonian path in the current semicomplete digraph. When an arc x --) u is identified, whose reversal destroys the property of having the desired path, then this arc must be part of any LX, y)-Hamiltonian path in the current semicomplete digraph. Now remove X, rename u by X, and repeat the above step for the new X. Eventually we will get a semicomplete digraph with only one vertex. Hence the (x, y)-path given by the sequence of successively removed vertices is an (x, y)-Hamiltonian path in T. 0 Note that by a more detailed analysis it follows from the inequality for algorithm has complexity O(n4Y for any E > 0. T(n) that the Hamiltonian

REFERENCES AND C. THOMASEN, A polynomial algorithm for the 2-path problem for semicomplete digraphs, SIAM /. Discrete M&h., to appear. 2. J. A. BONDY AND U. S. R. MURTY, “Graph Theory with Applications,” Elsevier, New York, 1976. 3. Y. MANOUSSAKIS, “A Linear Algorithm for Finding Hamiltonian Cycles in Tournaments,” Dficrete Math., to appear. 4. D. SOROKER, Fast parallel algorithms for finding Hamiltonian paths and cycles in tournaments, J. Algorithms 9 (19881, 276-286. 5. C. THOMASSEN, Hamiltonian connected tournaments, J. Combin. Theory Ser. B 28 (1980), 142-163. 1. J. BANG-JENSEN