Partial Answer to Puzzle #21: Getting rid of cycles in directed graphs

(Return to main page)

Puzzle #21 – how many arcs must be deleted from an n-node directed graph to get rid of all cycles? Let F(n) denote the maximum, over all n-node directed graphs G (note: singly-directed arcs only; bidirected arcs not allowed), of the minimum number of arcs you need to remove from G in order to cause G to become acyclic. Find values of F(n), upper and lower bounds on F(n), and asymptotics.

Motivation: This problem arises in the theory of Condorcet-like voting schemes. It is also relevant to the theory of the minimum feedback arc set problem, a known APX-hard NP-complete graph problem.

Answer: This innocent-looking puzzle turns out to lie rather deep... The current best known upper and lower bounds on F(n) for n<30 are shown below.

Note on computer aid: I originally proved 8≤F(8)≤10 and 12≤F(9)≤13 and conjectured F(8)=8 and F(9)=12. I then proved the theorem that these two conjectures are equivalent (and they would imply F(10)≤16, F(11)≤20, F(12)≤25, etc). I then noted that the value of F(8) should be within the reach of computers. I then used a computer with the aid of Brendan McKay's files of "tournaments" to prove the conjecture. Also, the computer found the values of F(n) for all n≤8 as a side effect, confirming the values I found by hand (and F(5)=3 is achieved by a unique tournament). The computer would also have been able to confirm F(9)=12 directly, but it would have taken it about a day, so I killed the job after 40 minutes. I estimate that F(10) could be determined by the current program in about 1-2 years. By only searching the semi-regular tournaments (i.e. performing a nonexhaustive search which probably will be good enough), my computer found F(9)≥12, F(10)≥15, and F(11)≥20 (achieved by a unique semi-regular tournament but 55 others reach 19). Although these might be thought only to prove lower bounds because of the non-exhaustive nature of the search, we shall see below with a little extra reasoning how they really prove equality in all three cases. Also, it turns out my values of F(n) for n≤10 had already been proven by A.Kotzig in Discrete Maths. 12 (1975) 17-25, also with the aid of a computer. With a better program (branch and bound search with "early cutoffs"), it would be possible to process all semi-regular tournaments with 12 and 13 nodes in about 1 week, which probably would suffice to determine F(12) and F(13), although I do not see how or why the word "probably" could be replaced by "definitely." Finally, the computer can be used to prove lower bounds by finding the best way to remove arcs from specific graphs devised by human inventors. This was how I proved many lower bounds listed in the next table. It would be good to do an exhaustive search of all cyclic graphs of each size, and of all "cyclic plus one extra vertex" graphs ditto; and to search all possible ways of extending record-showing graphs by adding one extra vertex (and to search all possible ways to remove their vertices). I have not carried out any of those ideas.

In much of the below, however, we shall disregard the computer and work by hand.

News flash: Irene Charon and Olivier Hudry noted that on the 20th page of their paper Aggregation of preferences into a linear order: a survey on the linear ordering problem for weighted or unweighted tournaments, are stated the following results got from [J-C. Bermond & Y. Kodratoff: Une heuristique pour le calcul de l'indice de transitivite' d'un tournoi, RAIRO 10,3 (1976) 83-92] which are sometimes worse than our results above, but mostly better:

F(12)=22 F(13)=28 n = 14 15 16 17 18 19 20 21 22 23 24 25 F(n) lower bound 31 38 40 47 55 64 64 72 81 92 92 103 F(n) upper bound 32 39 44 52 58 67 73 83 91 102 110 122

(End of news flash.)

The results for n≤4 are by exhaustive manual consideration of every possible directed graph.

QRgraph(P): A construction of an infinite family of directed graphs:

Let P be any prime of form 4k-1 (P=3,7,11,19,...). Let G be the directed graph with P vertices got by joining X→X+S whenever S is a nonzero square modulo P. (Note that this is self-consistent because -1 is not a square mod such P.) This directed graph is extremely symmetric. Namely, it is invariant under the group of (P-1)P linear transformations that map X to AX+B mod P with A nonzero (where if A is nonsquare the graph gets orientation-reversed). Note the symmetry group is arc-transitive. Perhaps, for an infinite subset of such P, this digraph maximizes (over all digraphs with the same number of nodes) the minimum number of arcs you need to remove to get acyclicity.

More generally, we can permit P to be any prime power of form 4k-1, not merely a prime – but then arithmetic has to be done in the finite field with P elements. The first interesting case of that is P=27=3³, in which case we can use this finite field.

Lower bounds on F(n) from QRgraphs and related graphs (usually with cyclic symmetries):

Side remark for group-theorists: My conjecture that F(8)=8 (later proved with computer aid) was inspired by the following. Consider extending QRgraph(7) by adding one more node. We claim that no matter how one directs the 7 arcs that connect the 7 old to the one new vertex, it is always possible to remove 8 arcs from the resulting graph to make it acyclic. To see that: First of all, at least 2 of the 7 new arcs must be ingoing (and at least 2 outgoing), otherwise we could simply delete the ≤1 ingoing new arcs plus the 7 old deleted arcs and our claim that 8 deletions suffice would be proven. So suppose wlog there are either 2 ingoing and 5 outgoing among the new arcs, or there are 3 ingoing and 4 outgoing. We now shall use the fact that the 7-vertex digraph is arc-transitive; each of its 21 arcs can be mapped to each other. Select an ingoing arc and (by means of a symmetry transformation of the 7-vertex graph to renumber its vertices) make its source vertex be vertex 0. Now delete all 7 arcs i→j of the 7-graph with j<i. If there is only one more ingoing new arc, we are done since it can be deleted to render the graph acyclic. So assume there are two. In that case, it is easy to see that at least one pair among the three old source-endpoints of the three ingoing arcs, must be connected by an old graph-arc. So by a symmetry we can wlog assume those two endpoints are vertices 0 and 1. Then the remaining ingoing new arc can be deleted to render the graph acyclic. Q.E.D. We also claim (which proves F(8)≥8) that any way whatever to connect an 8th vertex to the 7-node graph by 3 ingoing and 4 outgoing arcs (or their global direction-reversal) requires removal of 8 arcs to make it acyclic. Because: there are 3·4=12 in-out node-pairs among the 7, and 7·6/2=21 arcs in the 7-node graph. Since 12+14>21 by the pigeonhole principle at least some of those pairs must be connected by nondeleted arcs (even after 7 deletions) in the 7-node graph, and in the right direction to make a 3-cycle though the extra vertex. Hence more than 7 deletions are required. Q.E.D. This analysis suggests the conjecture that F(8)=8.

The highly-transitive Mathieu sporadic groups lurk underneath the hood of QRgraph(11) and QRgraph(23) and might enable one to prove some better bounds using similar techniques.

SkewHadamardGraph(N): Another construction of an infinite family of directed graphs: If N=4k-1 and a 4kX4k skew Hadamard matrix exists, then you can try "normalizing" the matrix so its first row is all "-" and first column is all "+" (that is, change signs of rows and columns bodily until this is true), removing this first row and column, and using the rest (ignoring the diagonal) as the adjacency matrix of our N-node directed graph. In fact our QRgraph(P) construction above can be interpreted as merely a special case of this Hadamard construction. (I have only tried a few instances of the skew Hadamard construction and in no case was a new record discovered.)

Superadditivity: F(a+b)≥F(a)+F(b).

A proof of a quadratic lower bound on F(n): Employ a Steiner Triple System on n points [which exists iff n=1 or n=3 mod 6, and contains (n-1)n/6 triples, any pair of triples overlapping at ≤1 points]; we can thus force an n-vertex directed graph to contain (n-1)n/6 edge-disjoint 3-cycles. I.e, make a directed 3-cycle on each Steiner triple.

Hence we get this lower bound: F(n)≥(n-1)n/6 if n=1 or n=3 mod 6. More generally you can use a maximum triple-packing ["A(n,4,3)" in the terminology of constant-weight codes rather than a Steiner Triple System (thus extending the method to also handle n=0,2,4,5 mod 6). One can indeed show F(n)≥floor(n*floor((n-1)/2)/3), see Chartrand et al. J.Combinatorial Theory 10 (1971) 12-41. However, these lower bounds are not always optimal, as is shown by the fact that the cyclic Steiner Triple System on 13 nodes (increments 1,3,9,2,6,5) proves F(13)≥26 but no more, whereas our (different) cyclic graph proves F(13)≥27.

Examples: F(7)≥7: consider the graph with vertex set Z mod 7, where there are arcs from X to X+1, X to X+2, and X to X+4 all mod 7. Then the triangles X→X+1→X+3→X all are edge-disjoint so you need to remove at least one arc from each to make it acyclic.

F(8)≥8= A(8,4,3); F(9)≥12 because of the Steiner triple system on 9 points arising from the rows, columns, and generalized diagonals of a 3x3 matrix; F(10)≥13= A(10,4,3); F(11)≥17= A(11,4,3); F(12)≥20= A(12,4,3); F(14)≥28= A(14,4,3); F(16)≥37= A(16,4,3); etc.

To consider the case F(9)≥12 in more detail: Make this graph G: it has 9 vertices arranged in a 3x3 grid (with periodic boundary conditions). Each grid point emits four arcs: to its North, East, NorthEast, and SouthEast neighbors. You can acyclify this graph by deleting the East, SouthEast, and NorthEast arcs emanating from the three West-column nodes, plus the North arcs emanating from the three South-row nodes (12 arcs deleted in all). That proves F(9)≥12. It also suggests the conjecture F(9)=12. One can further see that if any vertex is deleted from this 9-vertex digraph, the resulting 8-vertex digraph can be made acyclic by deleting 8 arcs. That reinforces our previous conjecture that F(8)=8. Also in the other direction, if F(8)=8 then the divide-and-conquer upper bound would prove the conjecture F(9)≤12, so the two conjectures are equivalent.

Increasing nature of F(n): Obviously, F(n+1)≥F(n).

A trivial quadratic upper bound on F(n): Order the n vertices arbitrarily from 1 to n. Now delete all the arcs ij with j>i or delete the ones with j<i, whichever arc-set is smaller. Hence F(n)≤(n-1)n/4.

A proof of some upper bounds on F(n): (Actually, some of these inequalities also can be used "in the other direction" to get lower bounds.) F(n+1)≤F(n)+floor( n/2 ), because use the best way to delete arcs from the graph on the first n vertices, and then remove either all ingoing or all outgoing arcs from the final vertex (whichever set is smaller).

A slightly better version of the above argument is this: F(n+1)≤F(n-1)+n-1 which you can see by adding two vertices and deleting all the arcs that enter that pair (or leave it, whichever arc-set is smaller).

Even better is this: F(n+3)≤F(n)+floor(3n/2), To see that, add three vertices which are not linked in a directed 3-cycle. (Three such vertices must exist in G if n>0, as you can see by drawing 4-vertex configurations, so wlog make them be the "last three" vertices of G.) Then delete all the arcs incoming from the n-vertex outside world, to these 3 (or delete the ones leaving, whichever is smaller).

Examples: F(5)≤F(4)+2=1+2=3, F(6)≤F(4)+4=1+4=5, F(7)≤F(4)+6=1+6=7, F(8)≤F(5)+7=3+7=10, F(8)≤F(6)+6=4+6=10, F(8)≤F(7)+3=7+3=10, F(9)≤F(6)+9=4+9=13, F(10)≤F(9)+4=12+4=16, F(10)≤F(8)+8=8+8=16, F(10)≤F(7)+10=7+10=17, F(11)≤F(8)+12=8+12=20, F(12)≤F(9)+13=12+13=25, F(13)≤F(10)+15=15+15=30.

By employing induction on the lattermost bound starting from the computer-aided result F(9)=12 as basis, we find the following quadratic upper bound (there are actually 6 cases depending on n mod 6, but we only give the n=0 mod 6 case): F(6k)≤(9k-5)k-1. This is slightly stronger than the trivial upper bound (6k+1)3k/2, by an additive improvement of 13k/2+1.

It is possible to do better than all that by using "directed graph Ramsey numbers." Namely, let R(n) be the least number so that any tournament with at least R(n) nodes contains an acyclic n-node subtournament, where trivially R(2)=2, and (as we just noted) R(3)=4, but going further, R(4)=8, R(5)=14, R(6)=28, and R(7)≥32. (These values of R(n) are deducible from page 167 in the article on Tournaments by K. Brooks Reid in The Handbook of Graph Theory CRC Press 2004, or see our puzzle 27.) The sequence R(n) plainly exists for every n because

1. If the statement "any tournament with exactly R(n) nodes contains an acyclic n-node subtournament" is true, then the statement with "exactly" changed to "at least" also is true (by considering a subtournament).
2. But that statement is true for each n and some R(n), because consider some fixed ordering of the V vertices and consider only the arcs directed consistently with that ordering; we then have an undirected graph and by the usual Ramsey numbers R(n,n) for undirected graphs there must exist, if V≥R(n,n), a complete subgraph (i.e. acyclic tournament, with arc-orientations restored) on n nodes. Here R(1,1)=1, R(2,2)=2, R(3,3)=6, R(4,4)=18, and R(5,5) is not presently known aside from 43≤R(5,5)≤49.

Examples: F(8)≤F(4)+8=1+8=9, F(9)≤F(5)+10=3+10=13, F(10)≤F(6)+12=4+12=16, F(11)≤F(7)+14=7+14=21, F(12)≤F(8)+16=8+16=24, F(13)≤F(9)+18=12+18=30, F(14)≤F(9)+22=12+22=34, F(15)≤F(10)+25=15+25=40, F(16)≤F(11)+27=20+27=47, F(17)≤F(12)+30≤54, F(18)≤F(13)+32≤62, F(19)≤F(14)+35≤69, F(20)≤F(15)+37≤77, F(21)≤F(16)+40≤87, F(22)≤F(16)+48≤47+48=95, F(23)≤F(17)+51≤105, F(24)≤F(18)+54≤116, F(25)≤F(19)+57≤126, F(26)≤F(20)+60≤137, F(27)≤F(21)+63≤150, F(28)≤F(22)+66≤161, F(29)≤F(23)+69≤174.

About tournaments: Don Coppersmith, Lisa Fleischer, and Atri Rudra showed in a 7-page SODA 2006 paper Ordering by weighted number of wins gives a good ranking for weighted tournaments (pages 776-782) that the following algorithm will come within a factor of 5 of finding the minimum number of arcs to delete in a "tournament" (i.e. directed graph with every possible singly-directed arc): order the vertices according to their indegree (that is, in voting terminology, in order of their Borda, or in our case Copeland, scores) breaking ties randomly, and then delete all the arcs ij with j>i or delete the ones with j<i, whichever arc-set is smaller. This does not produce anywhere near as good bounds as our results here, but it does have the advantage of being an algorithmic, i.e. constructive, proof, as compared to our proofs which are "nonconstructive." We shall later see that random graphs are (usually nearly) extremal.

More: these papers follow up on Coopersmith et al. (I thank Warren Schudy for this remark): N.Ailon, M.Charikar, A.Newman: Aggregating Inconsistent Information: Ranking and Clustering, appeared in STOC (Sympos. Theor. Computer Sci.) 05. Warren Schudy & Claire Kenyon-Matheiu: How to Rank with Few Errors: A PTAS for Weighted Feedback Arc Set on Tournaments, Brown Univ. Dept. Computer Science Report TR06-144, Nov 2006; Another version appeared in STOC.

Using my Hoeffding tail bound for sums of random variables (paper #85 here) we see that an n-node tournament (a "tournament" is a commonly used name for an n-node directed graph with every possible arc) with randomly directed arcs chosen by (n choose 2) coin tosses will have a number of arcs crossing a given cut into X-node and Y-node pieces (X+Y=n), that is, with probability >1-exp(-2n), at most √(XYn) away (additively) from its expectation.

Therefore if we now consider all (n choose Y) possible ways to thus-cut the graph (which is less than 2ⁿ=exp(0.69...n) ways) then even the one which leads to the most extreme deviation from expectation, will still, with probability >1-exp(-1.3n), (for all sufficiently large n) be at most √(XYn) away (additively) from its expectation.

Now, consider bisecting (X=Y=n/2), then recursively bisecting the two resulting hemi-tournaments, etc. The result will be an ordering of the n nodes. Now the claim is that even with the most-extreme of the n! orderings, the number of not-going-in-the-right-direction tournament arcs will be equal to (n+1)n/4 plus a deviation which is small. Specifically, it is smaller than

Now it is a well known fact that the minimum feedback arc set problem is equivalent to the problem of ordering the nodes to minimize the number of not-going-in-the-ordering's-direction arcs. [To see that, realize that an acyclic directed graph has an ordering called a "topological sort," whch may be found by successive removal of zero-invalence nodes, which is free of wrong-way arcs.] Therefore, we conclude that, with high probability (exponentially near 1 as n→∞) a random tournament digraph will have the property that you need to remove at least (n+1)n/4-Cn^3/2 arcs in order to get rid of its cycles. In this result, the best (i.e. least) possible value of C we can get with this proof technique is C=π/8/√(2-ln2)+ε<0.34351567. This is not good enough to improve on any of the lower bounds on F(n) in the table at top, because n=29 is not large enough to reach asymptopia.

Our bound F(n)≥(n+1)n/4-Cn^3/2 matches the trivial upper bound (n+1)n/4 asymptotically and thus solves the problem of determining the asymptotic behavior of F(n). It also proves as a side effect that the Coppersmith-Fleischer-Rudra algorithm – and also the trivial algorithm – both will, on random n-node tournaments, be optimal not merely to within a factor of 5, but with high probability actually optimal to within a factor of 1+O(n^-1/2). I also find it very plausible that my (nonrandom) graph construction based on quadratic residues will achieve these same asymptotics. That conjecture may or may not be within the reach of modern number theory.

Bounding the second term of the asymptotic behavior – Joel Spencer

Joel Spencer on page 136-137 of Networks 1 (1971) gave an incomprehensible argument to show the upper bound F(n)≤(n+1)n/4-Kn^3/2 for some constant K>10^-10, and on page 137 then claimed without proof that by "more careful" reasoning one somehow could improve this to K>0.1577989. If we accept that, then it would match our upper bound (except for the unequal values of the constants K and C).

Later, Spencer's claim (but with the constant K unspecified aside from noting that it is positive) was proved in only one paragraph on page 42 of P.Erdös & J.Spencer: Probabilistic methods in combinatorics (Academic Press 1974), by using their "quasi-Ramsey theorem."

Oddly enough, Erdös & Spencer were unable to get a matching upper bound (as we have done) and said that "the gap seems difficult to eliminate." But the way we did eliminate it, was precisely by using the "probabilistic method" so beloved of these authors – and it was quite simple and nice! So why did we succeed while they did not? The answer is that we used the probabilistic method in a better way, employing a Hoeffding tail bound. They did not try to use a tail bound – and that mistake cost them.

Later note: Erdös & Spencer's gap was closed (aside from C≠K), by Spencer himself rather poorly, and then by W. Fernandez de la Vega: On the maximum cardinality of a consistent set of arcs in a tournament, J. Combin. Theory B 35 (1983) 328-332 who showed C>1.72 (for sufficiently large n) by a tail bound based argument similar to ours. This is not as good a value for the constant C as our value, which is because he used a worse tail bound than we did (or because one of us made an arithmetic error). Spencer, according to WFdlV, had shown it for the far weaker C=4000.

Moral

As a consequence of our and the Spencer bound,

Return to puzzles

Return to main page