Tournaments as Feedback Arc Sets

Garth Isaak^{∗} Department of Mathematics Lehigh University, Bethlehem, PA 18015 gi02@lehigh.edu

Submitted: April 21, 1995; Accepted: October 3, 1995

Abstract

We examine the size s(n) of a smallest tournament having the arcs of an acyclic tournament on n vertices as a minimum feedback arc set. Using an integer linear programming formulation we obtain lower bounds s(n) ≥ 3n − 2 − ⌊log_{2} n⌋ or s(n) ≥ 3n − 1 − ⌊log_{2} n⌋, depending on the binary expansion of n. When n = 2^{k} − 2^{t} we show that the bounds are tight with s(n) = 3n−2−⌊log_{2} n⌋. One view of this problem is that if the ‘teams’ in a tournament are ranked to minimize inconsistencies there is some tournament with s(n) ‘teams’ in which n are ranked wrong. We will also pose some questions about conditions on feedback arc sets, motivated by our proofs, which ensure equality between the maximum number of arc disjoint cycles and the minimum size of a feedback arc set in a tournament. AMS Classification: Primary 05C20; Secondary 68R10

1 Introduction

A feedback arc set in a digraph is a set of arcs whose removal makes the digraph acyclic. J.P. Barthelemy asked whether every acyclic digraph arises as the arcs of a minimum sized feedback arc set of some tournament. In [1] we showed that this was the case and examined the smallest (vertex) size of such a tournament. For a digraph on n vertices, this size is at most s(n) where s(n) is the smallest size of a tournament with ‘the’ acyclic tournament T_{n} on n vertices as a feedback arc set. (In [1] we used the term reversing number, which is the number of additional vertices, i.e., s(n) − n.)

∗Partially supported by a grant from the ONR

In Section 2 we will review an integer linear programming formulation (from [1]) and sketch a proof that s(n) is determined by its optimal value. We obtain lower bounds on s(n) in Section 3 and exact values in Section 4. These can be summarized as

Theorem

s(n) ≥ 3n − 2 − ⌊log_{2} n⌋

if n is Type I or III and

s(n) ≥ 3n − 1 − ⌊log_{2} n⌋

if n is Type II. Furthermore, if n = 2^{k} − 2^{t} then

s(n) = 3n − 2 − ⌊log_{2} n⌋ .

The definitions of Types I,II,III will be given in Section 3. Further upper bounds on s(n) will also be discussed in Section 4. We conjecture that s(n) is equal to the lower bounds above for all n. One way of proving the upper bounds on s(n) involves filling in an upper triangular array with ordered pairs subject to a Latin Square like condition and another condition, with 3n − 2 − ⌊log_{2} n⌋ or 3n − 1 − ⌊log_{2} n⌋ pairs. This will be discussed in Section 4.

Our proofs of upper bounds on s(n) construct collections of arc disjoint cycles in a tournament with size equal to the the number of arcs in a minimum feedback arc set. In general this equality does not hold. In Section 5, we briefly discuss the problem of determining conditions on feedback arc sets that ensure equality. For example, if a tournament has a path as a feedback arc set then equality holds.

Conjecture If T is a tournament with a minimum feedback arc set a set of arcs which form a (smaller) acyclic tournament then the maximum number of arc disjoint cycles in T equals the minimum size of a feedback arc set.

The upper bound proofs in Section 4 show that this is true for certain tournaments T and suggest that it is true in general.

The problem we discuss can be viewed in the following manner. If the ‘teams’ in a tournament are ranked so as to minimize the number of inconsistencies what patterns can these inconsistencies form? The result of [1] mentioned above shows that every acyclic digraph can arise in such a manner. In particular, there exist tournaments on s(n) ‘teams’ for which n ‘teams’ are ranked wrong. For these n ‘teams’, i is ranked ahead of j exactly when j ‘beats’ i. For contrast to the problem considered here, we could also consider weighted version of feedback arc sets. In this case, each deleted arc is assigned a weight equal to the distance between its endpoints in the unique acyclic ordering after the feedback arc set is deleted. (There is a unique ordering if the original digraph is a tournament.) An ordering which minimizes the weighted sum of deleted arcs is equivalent to ranking based on non-increasing outdegrees (i.e., score sequence). While all acyclic tournaments arise as feedback arc sets, the only tournament that arises as a feedback arc set in this weighted version is the tournament on two vertices. See [6] for details. For a related variation see [4].

2 An Integer Programming Formulation

In [1] we examined a particular integer linear programming problem which provided a lower bound on s(n). We speculated that perhaps this bound was tight. In this section we reintroduce the integer program and sketch a proof that indeed its solution does determine s(n).

There are many equivalent versions of the problem of finding a minimum feedback arc set. An early reference is [11]. See [7] for a good summary of these variations. We will be interested in the following version. Given a tournament T, find an ordering π of its vertices which minimizes the number inconsistencies; π(i) < π(j) with (j, i) ∈ A(T). (Where A(T) is the arc set of T.) The inconsistent arcs are a minimum size feedback arc set. Conversely, after removing the arcs of a minimum feedback arc set in a tournament, the remaining graph is acyclic and has a unique acyclic ordering (i.e., it contains a Hamiltonian path). This ordering minimizes inconsistencies.

We now describe tournaments T (x⃗, n) which have the acyclic tournament T_{n} as a feedback arc set. Any tournament which has T_{n} as a feedback arc set will be of this form for some x⃗.

We will then describe conditions on the x_{i} necessary for T_{n} to be a minimum sized feedback arc set in T (x⃗, n). Minimizing ∑ x_{i} subject to these conditions gives a lower bound on s(n). In fact, it turns out that the conditions are also sufficient so that the integer linear program minimizing ∑ x_{i} subject to the conditions has s(n) − n as an optimal solution.

Any tournament with T_{n} as a feedback arc set can be completely described in terms of the numbers of vertices between two vertices of T_{n} in the ordering minimizing inconsistencies. Let V (T_{n}) = {v_{1}, v_{2}, … v_{n}} be the vertices of T_{n} with A(T_{n}) = {(v_{j}, v_{i})|j > i}. The vertex set of T (x⃗, n) is

V (T_{n}) ∪ {u_{i,j}|1 ≤ i ≤ n − 1, 1 ≤ j ≤ x_{i}}.

The arcs of T (x⃗, n) are

A(T_{n}) ∪ {(u_{i,j}, u_{s,t}) : i < s or i = s and j < t} ∪ {(v_{i}, u_{s,t})|i ≤ s} ∪ {(u_{i,j}, v_{s})|i < s}.

We can think of T (x⃗, n) in the following manner. The vertex set is V (T_{n}) along with ‘extra’ vertices u_{i,j} specified by x⃗. The arcs are those consistent with the ordering

v_{1}, u_{1,1}, …, u_{1,x_{1}}, v_{2}, u_{2,1} …, u_{2,x_{2}}, v_{3}, …, v_{n−1}, u_{n−1,1}, …, u_{n−1,x_{n−1}}, v_{n}

except for arcs between v_{i} vertices which are inconsistent with the ordering. We will call this the defining ordering of T (x⃗, n). If U_{i} represents u_{i,1}, u_{i,2}, …, u_{i,x_{i}} the the defining ordering looks like

v_{1}, U_{1}, v_{2}, U_{2}, …, v_{n−1}, U_{n−1}, v_{n}.

Clearly, A(T_{n}) is a feedback arc set in T (x⃗, n) since it is the set of arcs inconsistent with the defining ordering. Note that n+∑_{i=1}^{n−1} x_{i} is the number of vertices in T (x⃗, n). Thus to determine s(n) we must find x_{i} with minimum ∑_{i=1}^{n−1} x_{i} such that T (x⃗, n) has T_{n} as a minimum feedback arc set.

If the defining ordering minimizes inconsistencies then for any other ordering the number of inconsistencies must be at least |A(T_{n})| = \binom{n}{2}. With m = ⌊n/2⌋ one ‘bad’ ordering is

U_{1}, U_{2}, …, U_{m}, v_{n}, v_{n−1}, …, v_{3}, v_{2}, v_{1}, U_{m+1}, …, U_{n−1}.

So we maintain the ordering of the u_{i,j} and shift the v_{i} to the ‘middle’ and reverse their order. The arcs (v_{s}, u_{i,j}) for s ≤ i ≤ m are reversed as are arcs (u_{i,j}, v_{s}) for m + 1 ≤ i < s. So the number of inconsistent arcs is

x_{1} + 2x_{2} + 3x_{3} + ⋯ + \frac{n}{2}x_{n/2} + (\frac{n}{2} − 1)x_{n/2+1} + ⋯ + 2x_{n−2} + x_{n−1}

if n is even and

x_{1} + 2x_{2} + 3x_{3} + ⋯ + ⌊\frac{n}{2}⌋ x_{⌊n/2⌋} + ⌊\frac{n}{2}⌋ x_{⌊n/2⌋+1} + ⋯ + 2x_{n−2} + x_{n−1}

if n is odd. These sums must be at least \binom{n}{2} in order for the defining ordering to minimize inconsistencies.

We can also obtain a ‘bad’ ordering by restricting the ordering above to a segment of T (x⃗, n) from v_{j} to v_{j+h}. For example, the ordering

v_{1}, U_{1}, v_{2}, U_{2}, U_{3}, U_{4}, U_{5}, v_{9}, v_{8}, v_{7}, v_{6}, v_{5}, v_{4}, v_{3}, U_{6}, U_{7}, U_{8}, U_{9}, v_{10} …

yields the inequality x_{3} + 2x_{4} + 3x_{5} + 3x_{6} + 2x_{7} + x_{8} ≥ \binom{7}{2} for any n ≥ 10. So the x_{i} must satisfy

∑_{i=1}^{(h−j)/2} i(x_{j+i−1} + x_{h−i}) ≥ \binom{h − j + 1}{2} for h − j even  (1)

and

( ∑_{i=1}^{(h−j−1)/2} i(x_{j+i−1} + x_{h−i})) + \frac{h − j + 1}{2}x_{j+(h−j−1)/2} ≥ \binom{h − j + 1}{2} for h − j odd

(2)

where the ∑ term is interpreted as 0 if h − j = 1. More details can be found in [1].

Definition 1 Let ILP(n) be the integer linear program, min ∑_{i=1}^{n−1} x_{i} subject to (1),

(2) and x_{i} integral.

Note that if I(n) is the optimal value to ILP(n) then s(n) ≥ n + I(n). In [1] we asked if equality holds. We can in fact show this. However, since the details are lengthy and since only the lower bound is needed for what follows, we will not include the proof here.

3 Lower Bounds

In this section we determine lower bounds on the value of the integer linear programming problem (ILP) of the previous section. We will use the idea of cutting planes. The ideas are similar to those used in [1] however we use a more careful analysis and we believe that the lower bounds obtained here in fact give the value of ILP. We will show in Section 4 that this is the case for n = 2^{k} − 2^{t}.

First, we get a lower bound on ∑_{i=1}^{n−1} ix_{j+i−1} and also on ∑_{i=1}^{n−1} ix_{j−i}.

Definition 2 Let S(1) = 0 and S(2) = 1 for n ≥ 3

S(n) = \binom{n}{2} + S (⌊\frac{n}{2}⌋) + S (⌈\frac{n}{2}⌉) .

Lemma 1 For x_{i} as in ILP and any j such that the x variables below are defined,

∑_{i=1}^{n−1} ix_{j+i−1} ≥ S(n)  (3)

and

∑_{i=1}^{n−1} ix_{j−i} ≥ S(n).  (4)

Proof: For ease of notation we prove ∑_{i=1}^{n−1} ix_{i} ≥ S(n). The general cases of (3) and (4) follow by the symmetry of (1) and (2). The proof is by induction on n. For n = 2 this is just (2).

For n even combine

( ∑_{i=1}^{(n−2)/2} i(x_{i} + x_{n−i})) + \frac{n}{2}x\frac{n}{2} ≥ \binom{n}{2}

from (2) with j = 1 and h = n and

2 ∑_{i=1}^{(n/2)−1} ix_{\frac{n}{2} +i} ≥ 2S (\frac{n}{2})

from induction on (3) with j = \frac{n}{2} + 1 to get

∑_{i=1}^{n−1} ix_{i} ≥ \binom{n}{2} + 2S (\frac{n}{2}) = S(n).

For n odd combine

∑_{i=1}^{(n−1)/2} i(x_{i} + x_{n−i}) ≥ \binom{n}{2}

from (1) with j = 1 and h = n and

∑_{i=1}^{\frac{n+1}{2} −1} ix_{\frac{n−1}{2} +i} ≥ S (\frac{n + 1}{2})

from induction on (3) with j = \frac{n+1}{2} and

∑_{i=1}^{\frac{n−1}{2} −1} ix_{\frac{n+1}{2} +i} ≥ S (\frac{n − 1}{2})

from induction on (3) with j = \frac{n+3}{2} to get

∑_{i=1}^{n−1} ix_{i} ≥ \binom{n}{2} + S (\frac{n − 1}{2}) + S (\frac{n + 1}{2}) = S(n).□

For example, the Lemma gives 5x_{1} + 4x_{2} + 3x_{3} + 2x_{4} + x_{5} ≥ S(6). It also gives x_{3}+2x_{4}+3x_{5}+4x_{6}+5x_{7}+6x_{8} ≥ S(7) from combining x_{3}+2x_{4}+3x_{5}+3x_{6}+2x_{7}+x_{8} ≥ \binom{7}{2} with x_{6} + 2x_{7} + 3x_{8} ≥ S(4) and x_{7} + 2x_{8} ≥ S(3).

We classify each integer n as one of four types. Let k = ⌊log_{2} n⌋.

• Type I: n = 2^{k} + 2^{k−2} + ⋯ + 2^{k−2t} for some 0 ≤ t ≤ ⌊k/2⌋.

• Type II: 2^{k} < n < 2^{k} + 2^{k−2} + ⋯ + 2^{k−2⌊k/2⌋} and n not of type I.

• Type III: n > 2^{k} + 2^{k−2} + ⋯ + 2^{k−2⌊k/2⌋}.

• Type IVo: n = 2^{k} + 2^{k−2} + ⋯ + 2^{3} + 2 + 1 for k odd.

• Type IVe: n = 2^{k} + 2^{k−2} + ⋯ + 2^{2} + 2^{0} + 1 for k even, k ≥ 2.

Types IVo and IVe are needed only as intermediate steps in Lemma 2 and Theorem 1. Hence Types IVo and IVe are also included in Type III to ease the statement of Theorem 1.

Lemma 2 If n is of Type I then S(n) = n^{2} − n − \frac{n}{2} ⌊log_{2} n⌋.

If n is of Type II then S(n) > n^{2} − n − \frac{n}{2} ⌊log_{2} n⌋.

If n is of Type III then S(n) > n^{2} − \frac{3n}{2} − \frac{n}{2} ⌊log_{2} n⌋.

If n is of Type IVo then S(n) = n^{2} − n − \frac{n}{2} ⌊log_{2} n⌋ − \frac{1}{2}.

If n is of Type IVe then S(n) = n^{2} − n − \frac{n}{2} ⌊log_{2} n⌋ − 1.

Proof: We use induction. It is easy to check the necessary base cases n = 1, 2, 3. (The case n = 3 must be checked separately since in this case n = 2 = 2^{0} + 1 would be assumed to be Type IVe in the inductive step, but n = 2 is excluded from Type IVe since k = 0.) Observe also, that the bounds for Types IVo and IVe imply those for Type III. So when proving the bound for Type III we will not check those values that are also Type IVo or IVe.

There are a number of cases to check, all quite similar. Throughout this proof we will use k = ⌊log_{2} n⌋. Let T (n) = n^{2} − n − \frac{n}{2}k. Then for even n

\binom{n}{2} + T (⌊\frac{n}{2}⌋) + T (⌈\frac{n}{2}⌉) = \binom{n}{2} + 2 [(\frac{n}{2})^{2} − (\frac{n}{2}) − (\frac{n}{4}) (k − 1)]
= n^{2} − n − \frac{n}{2}k.  (5)

For odd n ≠ 2^{k+1} − 1

\binom{n}{2} + T (⌊\frac{n}{2}⌋) + T (⌈\frac{n}{2}⌉) = \binom{n}{2} + [(\frac{n − 1}{2})^{2} − (\frac{n − 1}{2}) − (\frac{n − 1}{4}) (k − 1)]

+ [(\frac{n + 1}{2})^{2} − (\frac{n + 1}{2}) − (\frac{n + 1}{4}) (k − 1)]

= n^{2} − n − \frac{n}{2}k + \frac{1}{2}.  (6)

Case 1a: n is even and Type 1. Then \frac{n}{2} is also Type I and

S(n) = \binom{n}{2} + 2S (\frac{n}{2}) = \binom{n}{2} + 2T (\frac{n}{2}) = n^{2} − n − \frac{n}{2}k

by induction and (5).

Case 1b: n is odd and Type 1. Then \frac{n−1}{2} is Type I and \frac{n+1}{2} is Type IVo. So

S(n) = \binom{n}{2} + S (\frac{n − 1}{2}) + S (\frac{n + 1}{2})
= \binom{n}{2} + T (\frac{n − 1}{2}) + (T (\frac{n + 1}{2}) − \frac{1}{2})
= n^{2} − n − \frac{n}{2}k

by induction and (6).

Case 2: n is of Type II. Then ⌊\frac{n}{2}⌋ and ⌈\frac{n}{2}⌉ are either Type I or Type II and at least one is Type II. So

S(n) = \binom{n}{2} + S (⌊\frac{n}{2}⌋) + S (⌈\frac{n}{2}⌉) > \binom{n}{2} + T (⌊\frac{n}{2}⌋) + T (⌈\frac{n}{2}⌉) ≥ n^{2} − n − \frac{n}{2}k

by induction and (5) and (6).

Case 3a: n is of Type III and not of Type IVo or IVe and also n ≠ 2^{k+1} − 1. Then ⌊\frac{n}{2}⌋ and ⌈\frac{n}{2}⌉ are also Type III. So

S(n) = \binom{n}{2} + S (⌊\frac{n}{2}⌋) + S (⌈\frac{n}{2}⌉)
> \binom{n}{2} + (T (⌊\frac{n}{2}⌋) − \frac{1}{2} ⌊\frac{n}{2}⌋) + (T (⌈\frac{n}{2}⌉) − \frac{1}{2} ⌈\frac{n}{2}⌉)
≥ n^{2} − n − \frac{n}{2}k − \frac{1}{2} ⌊\frac{n}{2}⌋ − \frac{1}{2} ⌈\frac{n}{2}⌉
= n^{2} − \frac{3}{2}n − \frac{n}{2}k

by induction and (5) and (6).

Case 3b: n = 2^{k+1} − 1. Then ⌊\frac{n}{2}⌋ = 2^{k} − 1 is Type III and ⌈\frac{n}{2}⌉ = 2^{k} is Type I. So

S(n) = \binom{n}{2} + S (⌊\frac{n}{2}⌋) + S (⌈\frac{n}{2}⌉)

> \binom{n}{2} + (\frac{n − 1}{2}^{2} − \frac{3}{2} (\frac{n − 1}{2}) − \frac{n − 1}{4}(k − 1)) + (\frac{n + 1}{2}^{2} − \frac{n + 1}{2} − \frac{n + 1}{4}k)
= n^{2} − \frac{3}{2}n + \frac{1}{2} − \frac{n}{2}k
> n^{2} − \frac{3}{2}n − \frac{n}{2}k

by induction.

Case 4a: n is Type IVe. Then \frac{n}{2} is Type IVo. So

S(n) = \binom{n}{2} + 2S (\frac{n}{2}) = \binom{n}{2} + 2 (T (\frac{n}{2}) − \frac{1}{2}) = n^{2} − n − \frac{n}{2}k − 1

by induction and (5).

Case 4b: n is Type IVo. Then ⌊\frac{n}{2}⌋ is Type I and ⌈\frac{n}{2}⌉ is Type IVe. So

S(n) = \binom{n}{2} + S (⌊\frac{n}{2}⌋) + S (⌈\frac{n}{2}⌉)
= \binom{n}{2} + T (\frac{n − 1}{2}) + (T (\frac{n + 1}{2}) − 1)
= n^{2} − n − \frac{n}{2} + \frac{1}{2} − 1
= n^{2} − n − \frac{n}{2} − \frac{1}{2}

by induction and (6). □

If α(n) denotes the exponent of the highest power of 2 dividing n then S(n + 1) − 2S(n) + S(n − 1) = α(n) + 1 [5]. From this we get S(n) = ∑_{i=1}^{n−1}(n − i)(α(i) + 1). This may be useful in obtaining more exact estimates of S(n). However, for our purposes, examining upper bounds on S(n) indicates that improved values will not change the results of Theorem 1 based on the bounds of Lemma 2.

The next Theorem improves the lower bound ∑_{i=1}^{n−1} x_{i} ≥ 2n − 4⌊log_{2} n⌋ obtained in [1].

Theorem 1 For x_{i} as in ILP, ∑_{i=1}^{n−1} x_{i} ≥ 2n − 2 − ⌊log_{2} n⌋ if n is Type I or III and ∑_{i=1}^{n−1} x_{i} ≥ 2n − 1 − ⌊log_{2} n⌋ if n is Type II.

Proof: As in the proof of Lemma 2, there are a number of cases to check, all quite similar. In each case we combine an inequality (1) or (2) with an inequality (3) and an inequality (4) to get a lower bound for ∑_{i=1}^{n−1} x_{i} in terms S(n). Then we use the bounds on S(n) from Lemma 2 and round fractions (since ∑_{i=1}^{n−1} x_{i} must be integral) to get the desired results.

When n is even combine

( ∑_{i=1}^{(n−2)/2} i(x_{i} + x_{n−i})) + \frac{n}{2}x\frac{n}{2} ≥ \binom{n}{2}

from (2) with j = 1 and h = n and

∑_{i=1}^{(n/2)−1} ix_{\frac{n}{2} −i} ≥ S (\frac{n}{2})

from (4) with j = \frac{n}{2} and

∑_{i=1}^{(n/2)−1} ix_{\frac{n}{2} +i} ≥ S (\frac{n}{2})

from (3) with j = \frac{n}{2} + 1 to obtain

∑_{i=1}^{n−1} \frac{n}{2}x_{i} ≥ \binom{n}{2} + 2S (\frac{n}{2}) = S(n).

So then

∑_{i=1}^{n−1} x_{i} ≥ \frac{2}{n}S(n).

We now use the bounds of Lemma 2 for S(n) to get

∑_{i=1}^{n−1} x_{i} ≥ \frac{2}{n} (n^{2} − n − \frac{n}{2} ⌊log_{2} n⌋) = 2n − 2 − ⌊log_{2} n⌋ If n is of Type I

∑_{i=1}^{n−1} x_{i} > \frac{2}{n} (n^{2} − n − \frac{n}{2} ⌊log_{2} n⌋) = 2n − 2 − ⌊log_{2} n⌋ If n is of Type II

∑_{i=1}^{n−1} x_{i} > \frac{2}{n} (n^{2} − \frac{3}{2}n − \frac{n}{2} ⌊log_{2} n⌋) = 2n − 3 − ⌊log_{2} n⌋ If n is of Type III.

For Types II and III since the inequality is strict and since ∑_{i=1}^{n−1} x_{i} must be integral we get the desired bounds.

When n is odd combine

∑_{i=1}^{(n−1)/2} i(x_{i} + x_{n−i}) ≥ \binom{n}{2}

from (1) with j = 1 and h = n and

∑_{i=1}^{\frac{n+1}{2} −1} ix_{\frac{n+1}{2} −i} ≥ S (\frac{n + 1}{2})

from (4) with j = \frac{n+1}{2} and

∑_{i=1}^{\frac{n+1}{2} −1} ix_{\frac{n−1}{2} +i} ≥ S (\frac{n + 1}{2})

from (3) with j = \frac{n+1}{2} to obtain

∑_{i=1}^{n−1} \frac{n + 1}{2}x_{i} ≥ \binom{n}{2} + 2S (\frac{n + 1}{2}) = −n + \binom{n + 1}{2} + 2S (\frac{n + 1}{2}) = S(n + 1) − n.

So then

∑_{i=1}^{n−1} x_{i} ≥ \frac{2}{n + 1} (S(n + 1) − n) .

We now use the bounds of Lemma 2 for S(n). Note that when n is odd and Type I then n+1 is Type IVe. If n is Type II then n+1 is Type I or II. If n is Type III and n ≠ 2^{k}−1 then n+1 is Type III. In each of the previous cases ⌊log_{2}(n+1)⌋ = ⌊log_{2} n⌋. If n = 2^{k} −1 then n+1 is Type I and ⌊log_{2}(n+1)⌋ = ⌊log_{2} n⌋+1. With some algebra we get

∑_{i=1}^{n−1} x_{i} ≥ \frac{2}{n + 1} ((n + 1)^{2} − (n + 1) − \frac{n + 1}{2}⌊log_{2}(n + 1)⌋ − 1 − n)
= 2n − 2 − ⌊log_{2} n⌋ If n is of Type I
∑_{i=1}^{n−1} x_{i} > \frac{2}{n + 1} ((n + 1)^{2} − (n + 1) − \frac{n + 1}{2}⌊log_{2}(n + 1)⌋ − n)
= 2n − 2\frac{n}{n + 1} − ⌊log_{2} n⌋ If n is of Type II
∑_{i=1}^{n−1} x_{i} > \frac{2}{n + 1} ((n + 1)^{2} − \frac{3}{2}(n + 1) − \frac{n + 1}{2}⌊log_{2}(n + 1)⌋ − n)
= 2n − 1 − 2\frac{n}{n + 1} − ⌊log_{2} n⌋ If n ≠ 2^{k} − 1 is of Type III
∑_{i=1}^{n−1} x_{i} ≥ \frac{2}{n + 1} ((n + 1)^{2} − (n + 1) − \frac{n + 1}{2}⌊log_{2}(n + 1)⌋ − n)
= 2n − 1 − 2\frac{n}{n + 1} − ⌊log_{2} n⌋ If n = 2^{k} − 1

Rounding since ∑_{i=1}^{n−1} x_{i} must be integral we get the desired bounds. □

Since s(n) ≥ n + ∑_{i=1}^{n−1} x_{i} we get

Corollary 1 If n is Type I or III then s(n) ≥ 3n − 2 − ⌊log_{2} n⌋. If n is Type II then s(n) ≥ 3n − 1 − ⌊log_{2} n⌋.

For example, to get a bound on s(9) we combine x_{1} +2x_{2} +3x_{3} +4x_{4} +4x_{5} +3x_{6} + 2x_{7} + x_{8} ≥ \binom{9}{2} = 36 from (1) with 4x_{1} + 3x_{2} + 2x_{3} + x_{4} ≥ S(5) = 15 from (4) and x_{5} + 2x_{6} + 3x_{7} + 4x_{8} ≥ S(5) = 15 from (3) to obtain 5 ∑_{i=1}^{8} x_{i} ≥ 66 or ∑_{i=1}^{8} x_{i} ≥ 13.2. Since the x_{i} must be integral we round up to get ∑_{i=1}^{8} x_{i} ≥ 14. Hence s(9) ≥ 9 + 14. We can in fact show that s(9) = 23 using the methods similar to those in Section 4.

4 Exact Values

In this section we construct tournaments on 3n − 2 − ⌊log_{2} n⌋ vertices having the transitive tournament T_{n} as a minimum feedback arc set when n = 2^{k} − 2^{t}. The details of the proof are a bit long, however, the main ideas can be found in the description of the tables C_{n} below.

We first do this for n = 2^{k}. Let α(i) be the exponent in the highest power of 2 dividing i. We will show that if x_{i} = α(i) + 1 then in T (x⃗, n) we can construct \binom{n}{2}

arc disjoint 3−cycles. Then any minimum feedback arc set has size at least \binom{n}{2} and T_{n} is a minimum feedback arc set. Observing that ∑_{i=1}^{2^{k}−1}(α(i) + 1) = 2^{k+1} − 2 − k then completes the proof. For n = 2^{k} − 2^{t} we simply restrict the tournament above for 2^{k} to the first n vertices of T_{2^{k}}. For other values of n similar restrictions can be used to improve the upper bounds s(n) ≤ 3n − 4 obtained in [1]. However these new upper bounds are not equal to the lower bounds of Theorem 1 in these cases.

A convenient way to view the construction of the triangles is to use an array C_{n} with entries C_{n}(i, j) for 1 ≤ i < j ≤ n integral ordered pairs (a, b). An entry (i, j) in C_{n} will correspond to vertex u_{i,j} in T (x⃗, n). The 3−cycles will be (v_{i}, u_{c(i,j)}, v_{j}). We have the following table for n = 4:

2 3 4
1 1,0 2,1 2,0
2  2,0 2,1
3  3,0

¿From this we get the arc disjoint 3−cycles in T (x⃗, n) (v_{1}, u_{1,0}, v_{2}), (v_{1}, u_{2,1}, v_{3}), (v_{1}, u_{2,0}, v_{4}), (v_{2}, u_{2,0}, v_{3}), (v_{2}, u_{2,1}, v_{4}), (v_{3}, u_{3,0}, v_{4}) containing the arcs of T_{4}. In this case we need x_{2} ≥ 2 since there are two pairs with first entry 2. Similarly x_{1} ≥ 1 and x_{3} ≥ 3.

Next is the table C_{8}.

2 3 4 5 6 7 8
1 1,0 2,1 2,0 4,2 3,0 4,1 4,0
2  2,0 2,1 3,0 4,2 4,0 4,1
3  3,0 4,1 4,0 4,2 5,0
4  4,0 4,1 5,0 4,2
5  5,0 6,1 6,0
6  6,0 6,1
7  7,0

The entry C_{8}(2, 6) = (4, 2) gives the 3−cycle (v_{2}, u_{4,2}, v_{6}). Also, ∑ x_{i} = 11 since there are 11 ordered pairs. This shows that s(8) ≤ 11.

In order for the 3−cycles to be well defined we must have

if C_{n}(i, j) = (a, b) then i ≤ a < j.  (7)

In order that the arcs of the cycles be disjoint

Each ordered pair appears at most once in each row and in each column (8)

To construct C_{2n} from C_{n} we do the following: The upper left triangular block is C_{n}. The lower right triangular block is C_{n} with n added to the first entry of each pair. For the remaining n by n upper right square (rows 1, 2 … n and columns n+1, … 2n) start with upper right square (rows 1, 2, … n/2 and columns n/2 + 1, … n) in C_{n}. Replace each entry (a, b) by a 2 by 2 square whose diagonal elements are (2a, b + 1). For example the entries (4, 2) in positions C_{8}(1, 5) and C_{8}(2, 6) are obtained from the entry (2, 1) in position C_{4}(1, 3). The off diagonal entries in the 2 by 2 square are determined by their position as described below.

More formally

C_{2n}(i, j) = C_{n}(i, j) if j ≤ n (and hence i < n).  (9)
C_{2n}(i, j) = C_{n}(i − n, j − n) + (n, 0) if i > n + 1 (and hence j > n + 1).  (10)
C_{2n}(i, j) = (\frac{i + j − 1}{2}, 0) if i ≤ n and j > n and i + j odd.  (11)

C_{2n}(i, j) = (2a, b+1) if i ≤ n and j > n and i+j even where C_{n} (⌈\frac{i}{2}⌉ , ⌈\frac{j}{2}⌉) = (a, b).

Examining the construction from the tables above reveals that the C_{n} satisfy (7) and (8) and that there are pairs (a, b) for 1 ≤ a < n and for a given a, for 0 ≤ b ≤ α(a). In order to prove this carefully, there are a number of details to check. Some extra notation will be useful.

If an ordered pair (a, b) appears exactly once in each row and each column of the sub-array of C_{n} in rows r, r + 1, …, r + m and columns s, s + 1, …, s + m then we will say that (a, b) is a transversal on C_{n}[r, r + m; s, s + m].

Lemma 3 If (a, b) is a transversal on C_{n}[r, r+m; s, s+m] with r ≤ n/2 and s > n/2 then (2a, b + 1) is a transversal on C_{2n}[2r − 1, 2r + 2m; 2s − 1, 2s + 2m].

Proof: The entries of the form (2a, b+1) on C_{2n}[2r −1, 2r +2m; 2s−1, 2s+2m] come from entries (a, b) in C_{n}[r, r + m; s, s + m] using (12). The entries in C_{2n} with i + j odd have second term 0. So we need to show that there is a transversal on entries with i + j even. For 2r − 1 ≤ 2i − 1 < 2r + 2m and 2s − 1 ≤ 2j − 1 < 2s + 2m, (2a, b + 1) appears in C_{2n}(2i − 1, 2j − 1) if and only if (a, b) appears in C_{n}(i, j). For 2r − 1 < 2i ≤ 2r + 2m and 2s − 1 < sj ≤ 2s + 2m (2a, b + 1) appears in C_{2n}(2i, 2j) if and only if (a, b) appears in C_{n}(i, j). Then the transversal property in C_{n} and (12) ensures the transversal property in C_{2n}. □

Lemma 4 For n = 2^{k}, the following hold for C_{n}:

(a) C_{n}(i, j) = (a, 0) if and only if i + j is odd and a = (i + j − 1)/2.

(b) For 1 ≤ a < n, if (a, b) is an entry then 0 ≤ b ≤ α(a). (c1) If 1 ≤ a ≤ n/4 and 0 ≤ b ≤ α(a) then (a, b) is a transversal on C_{n}[1, a; a + 1, 2a] and there are no other (a, b) entries. (c2) If 3n/4 ≤ a ≤ n − 1 and 0 ≤ b ≤ α(a) then (a, b) is a transversal on C_{n}[2a − n + 1, a; a + 1, n] and there are no other (a, b) entries. (d1) If n/4 < a < n/2 and 0 ≤ b ≤ α(a) then (a, b) is a transversal on C_{n}[1, a; a + 1, 2a]. This transversal can be decomposed into disjoint transversals on C_{n}[2a−n/2+ 1, a; a + 1, n/2] and on C_{n}[1, 2a − n/2; n/2 + 1, 2a]. There are no other (a, b) entries. (d2) If n/2 < a < 3n/2 and 0 ≤ b ≤ α(a) then (a, b) is a transversal on C_{n}[2a − n + 1, a; a + 1, n]. This transversal can be decomposed into disjoint transversals on C_{n}[n/2 + 1, a; a + 1, 2a − n/2] and on C_{n}[2a − n + 1, n/2; 2a − n/2 + 1, n]. There are no other (a, b) entries.

(e) If a = n/2 and 0 ≤ b ≤ α(a) then (a, b) is a transversal on C_{n}[1, a; a + 1, n] and there are no other (a, b) entries.

Proof: We will use induction. The conditions hold for C_{2}, which consists of the single entry C_{2}(1, 2) = (1, 0).

Assume that (a), (b), (c), (d) and (e) hold for C_{n} and consider C_{2n}. We will say that (a, b) is a (*) entry if it arises from (*) in the definition of C_{2n}.

Entries (a, 0) are not created by (12). Using (11) and inductively (9) and (10) it is straightforward to check that (a) holds.

For a odd, (b) follows immediately from (a). For a even, if (a, b) is a (9) entry then b ≤ α(a) by induction. If (a, b) is a (10) entry then b ≤ α(n − a) = α(a) by induction and since n = 2^{k}. If (a, b) is a (12) entry then b ≤ α(a/2) since it comes from (a/2, b − 1) in C_{n}. So (b + 1) ≤ α(a) and (b) holds.

Using (a) (and i < j) it is straightforward to check (c), (d) and (e) for pairs of the form (a, 0) and hence C_{2n}(i, j) with i + j odd. So we assume b ≥ 1 and i + j even.

If a is odd then the only pair using a is (a, 0). So we assume a is even. Thus we will write 2a instead of a.

Case c1: If 2a ≤ 2a ≤ n/2 then (2a, b) does not appear as a (10) entry. Also, if C_{n}(⌈(i/2)⌉, ⌈j/2⌉) = (a, b − 1) then (c1) applies and ⌈(j/2)⌉ ≤ 2a hence j ≤ 4a ≤ n. So (2a, b) does not appear as a (12) entry. Then, (2a, b) appears only as a (9) entry and (c1) and (d1) inductively show that (2a, b) appears only as a transversal on C_{n}[1, a; a + 1, 2a]. Since C_{2n} = C_{n} in this region (2a, b) appears only as a transversal on C_{2n}[1, a; a + 1, 2a] and (c1) holds.

Case c2: Similarly, if 2a ≥ 3n/2 ≤ 2n − 2 then (2a, b) does not appear as a (9) entry. Also, if C_{n}(⌈(i/2)⌉, ⌈j/2⌉) = (a, b−1) then (c2) applies and ⌈(i/2)⌉ ≥ 2a−n+1 hence i > 4a − 2n ≥ n. So (2a, b) does not appear as a (12) entry. Then, (2a, b) appears only as a (10) entry and (c2) and (d2) inductively show that (2a − n, b) appears only as a transversal on C_{n}[4a − 3n + 1, 2a − n; 2a − n + 1, n]. From (10) we add n to the indices of each of the rows and columns to get the appearances of (2a, b) in C_{2n}. So (2a, b) appears only as a transversal on C_{2n}[4a − 2n + 1, 2a; 2a + 1, 2n], which is (c2).

Case d1: If n/2 < 2a < n then (2a, b) appears as a (9) and a (12) entry. When (2a, b) appears as a (9) entry (c2) and (d2) inductively give a transversal on C_{n}[4a−n+ 1, 2a; 2a+1, n]. By (9) this gives a transversal of (2a, b) on C_{2n}[4a−n+1, 2a; 2a+1, n]. The first of the disjoint transversal in (d1). The (12) appearances of (2a, b) arise from appearances of (a, b − 1) in C_{n}(i, j) with i < n/2 and j > n. Inductively, (c1) or (d1) shows that (a, b − 1) is a transversal on C_{n}[1, 2a − n/2; n/2 + 1, 2a]. Lemma 3 then gives a (2a, b) transversal on C_{2n}[1, 4a − n; n + 1, 4a]. The second disjoint transversal in (d1).

Case d2: If n < 2a < 3n/2 then (2a, b) appears as a (10) and a (12) entry. When (2a, b) appears as a (10) entry (c1) and (d1) inductively show that (2a − n, b) is a transversal on C_{n}[1, 2a − n; 2a − n + 1, 4a − 2n]. Adding n to each of these entries for (10) we get a (2a, b) transversal on C_{2n}[n + 1, 2a; 2a + 1, 4a − n]. The first disjoint transversal in (d2). The (12) appearances of (2a, b) arise from appearances of (a, b−1) in C_{n}(i, j) with i ≤ n/2 and j > n. Inductively (c2) or (d2) shows that (a, b − 1) is a transversal on C_{n}[2a − n + 1, a; a + 1, n]. Lemma 3 then gives a (2a, b) transversal on C_{2n}[4a − 2n + 1, 2a; 2a + 1, 2n]. The second disjoint transversal in (d2).

Case e: For 2a = n the proof is the same as the second part of the proof of (d1). So (e) holds. □

Theorem 2 For 0 ≤ t ≤ k − 1, if n = 2^{k} − 2^{t} then s(n) = 3n − 2 − ⌊log_{2} n⌋.

Proof: Corollary 1 gives s(n) ≥ 3n − 2 − ⌊log_{2} n⌋.

For s(n) ≤ 3n − 2 − ⌊log_{2} n⌋ we first consider the case n = 2^{k+1} − 2^{k} = 2^{k}. Construct T (x⃗, 2^{k}) with x_{i} = α(i) + 1. Conditions (c), (d) and (e) of Lemma 4 give (7) and (8). Thus (v_{i}, u_{c(i,j)}, v_{j}) are arc disjoint 3−cycles. ¿From the construction of C_{n} there are \binom{2^{k}}{2} of these cycles. So T (x⃗, 2^{k}) has T_{2^{k}} as a minimum feedback arc set. (Note, we need to use these cycles since we have not shown that x⃗ is feasible for ILP. Our proof using C_{2^{k}} in fact shows this.)

Condition (b) of Lemma 4 gives x_{i} = α(i) + 1. Since T (x⃗, 2^{k}) has n + ∑_{i=1}^{2^{k}−1} x_{i} vertices, it remains to show that ∑_{i=1}^{2^{k}−1}(α(i) + 1) = 2^{k+1} − 2 − k. Observe that for 1 ≤ i < 2^{k}, α(i) = α(2^{k} − i). So by induction

∑_{i=1}^{2^{k}−1}(α(i)+1) = 2 ( ∑_{i=1}^{2^{k−1}−1} α(i))+α(2^{k−1})+1 = 2 (2^{k} − 2 − (k − 1))+k = 2^{k+1}−2−k.

For n = 2^{k} − 2^{t} when 0 ≤ t ≤ k − 2 delete v_{1}, …, v_{2^{t}} and u_{i,j} for 1 ≤ i ≤ 2^{t} from T (x⃗, 2^{k}). Then T_{n} is a minimum feedback arc set of the new tournament since the arc disjoint cycles from C_{2^{k}} can still be used. The number of deleted vertices is

2^{t} + ∑_{i=1}^{2^{t}}(α(i)+1) = 2^{t} + (2^{t+1} − 2 − t)+(α(2^{t})+1) = 3·2^{t} −2−t+(t+1) = 3·2^{t} −1.

The number of remaining vertices is

3 · 2^{k} − 2 − k − (3 · 2^{t} − 1) = 3 · (2^{k} − 2^{t}) − 2 − (k − 1) = 3n − 2 − ⌊log_{2} n⌋.□

For other values of n we can obtain upper bounds on s(n) in a manner similar to the previous proof, but these bounds will not equal the lower bounds of Corollary 1. If ⌊log_{2} n⌋ = k and t is such that 2^{k+1} − 2^{t+1} < n < 2^{k+1} − 2^{t} let m = 2^{k+1} − n. Using the tournament for 2^{k+1} − 2^{t} from the proof of Theorem 2 and using the lower bound for s(m + 1) from Corollary 1 and calculating as above we get

s(n) ≤ 3n − 2 − ⌊log_{2} n⌋ + ⌊log_{2}(2^{k+1} − 2^{t} − n + 1)⌋ .

For values of n other than 2^{k}+1 and those covered by Theorem 2 this bound is at least as good as the bound s(n) ≤ 3n − 4 found in [1] and it is better when m + 1 < 2^{k−2}.

5 Conclusion

There are a number of questions that remain. The proof of Theorem 2 could be shortened by showing directly that x_{i} = α(i) + 1 satisfies ILP without resorting to the tables C_{n}. However, using the approach of such tables may prove useful in showing that the lower bounds give s(n) in general. As we have noted before, we have the following conjecture

Conjecture If n is Type I or III then s(n) = 3n − 2 − ⌊log_{2} n⌋ and if n is Type II then s(n) = 3n − 1 − ⌊log_{2} n⌋.

As in Section 4 this conjecture can be answered with a positive answer to

Conjecture Let t(n) denote the minimum number of ordered pairs needed to fill a strictly upper triangular array C_{n}(i, j) (1 ≤ i < j ≤ n) such that the pairs in each row are distinct, the pairs in each column are distinct and if C_{n}(i, j) = (a, b) then i ≤ a < j. If n is Type I or III then t(n) = 3n − 2 − ⌊log_{2} n⌋ and if n is Type II then t(n) = 3n − 1 − ⌊log_{2} n⌋.

If the conjecture below is true then these first two conjectures are equivalent. In a digraph the number of arc disjoint cycles is at most the minimum size of a

feedback arc set. All of our proofs have used tournaments in which equality holds. In general, even for tournaments, the minimum size of a feedback arc set may be strictly larger than the maximum number of arc disjoint cycles. In fact, for large m a random tournament on m vertices has minimum size of a feedback arc set \frac{1}{2} \binom{m}{2} − cm^{3/2} with

probability approaching one [10] while it has at most ⌊m/3⌊(m − 1)/2⌋⌋ ≤ \frac{1}{3} \binom{m}{2} arc disjoint cycles (since each cycle has at least three arcs) [3]. When the host graph is not a tournament, but a planar digraph, then the Luchesi-Younger Theorem [8] shows that equality does hold. For feedback vertex sets, [9] establishes that for any finite digraph with s (vertex-) disjoint circuits, there exists a feedback vertex set of size at most some function f(s). See the survey [2] for related work. However, if a tournament has a minimum feedback arc set whose arcs form an acyclic tournament on n vertices then it must be of the form T (x⃗, n) for x⃗ satisfying ILP. The conditions for ILP lead us to the following conjecture mentioned in the introduction:

Conjecture If T is a tournament with a minimum feedback arc set a set of arcs which form a (smaller) acyclic tournament then the maximum number of arc disjoint cycles in T equals the minimum size of a feedback arc set.

If D is any digraph containing a Hamiltonian path, a similar table to the C_{n} in Section 4 can be constructed (with blocks corresponding to missing arcs in D left blank) to get tournaments with D as a minimum feedback arc set. Any tournament with D as a minimum feedback arc set will have a structure similar to T (x⃗, n); it is completely determined by the sizes x_{i}. Then, lower bounds on the smallest size of such a tournament can be obtained by the analogue of ILP with the right hand sides of the inequalities replaced with the number of arcs of D in the segment. We do not know if this ILP gives the exact value of the size of the tournament. It may be possible that analogues of the questions above hold in this case. For example it is not hard to show that if T has a feedback arc set whose arcs are the arcs of a (Hamiltonian) path then the minimum size of a feedback arc set in T equals the maximum number of arc disjoint cycles.

Question: If T is a tournament with a minimum feedback arc set a set of arcs which form an acyclic digraph with a Hamiltonian path is it true that the maximum number of arc disjoint cycles in T is equal to the minimum size of a feedback arc set? Given a digraph D which contains a Hamiltonian path, is it possible to efficiently compute the size of a smallest tournament with a minimum feedback arc set whose arcs are the arcs of D?

Acknowledgement: The author would like to thank a referee for bringing [9] to his attention.

References

1. J.P. Barthelemy, O. Hudry, G. Isaak, F.S. Roberts and B. Tesman, The Reversing Number of a Digraph, Discrete Applied Mathematics to appear (1995)

2. J.C. Bermond and C. Thomassen, Cycles in Digraphs – a Survey, J. Graph Theory 5 (1981), 1–43.

3. G. Chartrand, D. Geller and S. Hedetniemi, Graphs with Forbidden Subgraphs, J. Combinatorial Theory B, 10 (1971) 12–41.

4. W. Gu, K.B. Reid and W. Schnyder, Realization of Digraphs by Preferences Based on Distances in Graphs, J. Graph Theory, 19 (1995) 367–373.

5. G. Hurlbert, personal communication.

6. G. Isaak and B. Tesman, The Weighted Reversing Number of a Digraph, Congressus Numerantium, 83 (1991) 115–124.

7. M. Jünger, Polyhedral Combinatorics and the Acyclic Subdigraph problem, Heldermann Verlag, Berlin, 1985.

8. C.L. Lucchesi and D.H. Younger, A Minimax Theorem for Directed Graphs, J. London Math. Soc. (2), 17 (1978) 369-374.

9. P.D. Seymour, G.N. Robertson and R. Thomas, unpublished

10. W. F. de la Vega, On the Maximum Cardinality of a Consistent Set of Arcs in a Random Tournament, J. Combinatorial Theory B 35 (1983) 328–332.

11. D.H. Younger, Minimum feedback arc sets for a directed graph, IEEE Transactions, CT-10 (1963), No. 2, 240-245.