Dilworth's Theorem and its application for path systems of a cycle---implementation and analysis. one of my recent favorites

by András A. Benczúr, Jörg Förster and Zoltán Király

Proc. European Symp. Alg., Springer Lecture Notes in Computer Science 1643:598--509 (1999)

ps.gz ps pdf

Document in Citeseer database

Abstract

Given a set P of m subpaths of a length n path P, Györi's theorem gives a min-max formula for the smallest set G of subpaths, the so-called generators, such that every element of P arises as the union of some members of G. We present an implementation of Frank's algorithm for a generalized version of Györi's problem that applies to subpaths of cycles and not just paths. The heart of this algorithm is Dilworth's theorem applied for a specially prepared poset.

• We give an O(n^{2.5}\sqrt{\log n}+m\log n) running time bound for Frank's algorithm by deriving non-trivial bounds for the size of the poset passed to Dilworth's theorem. Thus we give the first practical running time analysis for an algorithm that applies to subpaths of a cycle.
• We compare our algorithm to Knuth's O((n+m)^2) time implementation of an earlier algorithm that applies to subpaths of a path only. We apply a reduction to the input subpath set that reduces Knuth's running time to O(n^2\log^2n+m\log n). We note that derivatives of Knuth's algorithm seem unlikely to be able to handle subpaths of cycles.
• We introduce a new ``cover edge'' heuristic in the bipartite matching algorithm for Dilworth's problem. Tests with random input indicate that this heuristic makes our algorithm (specialized to subpaths of a path) outperform Knuth's one for all except the extremely sparse (m\approx n/2) inputs. Notice that Knuth's algorithm (with our reduction applied) is better by a factor of approximately \sqrt n in theory.

Citations

1. András Frank
   Finding minimum weighted generators of a path system
   Contemporary Trends in Discrete Mathemaics (eds.: R.L. Graham, J. Kratochvil, J. Nesetril, and F.S. Roberts), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 49, 1999, pp. 129-138.
2. András Frank
   Finding minimum generators of a path system
   J. Combinatorial Theory, Ser. B., 75, (1999) pp. 237-244.