Phase-Transitions and Combinatorial Search

A General Phase-Structural Study of Computationally Hard Problems and Efficient Algorithmics

EPSRC Funded Project: Grant Reference: GR/L/77089

Participants: Paul E. Dunne, Alan Gibbons, Michele Zito

Summary
The primary concern of this work is to produce a sound general basis for the analytic study and exploitation of phase transition effects in hard combinatorial decision problems. The two principal benefits that will result from such a basis are: an understanding of how such phenomena may be exploited in the design of classes of fast algorithms for such problems; and, secondly, a general model within which novel phase transition results can be derived. In order to address two potential objections to existing experimental studies - that these do not reflect the properties of `real-world' data and are unsuited to problems lacking an `obvious' parameter that characterises a phase transition - the work will also examine different empirical frameworks for predicting phase transitions and develop models of probability distributions that go some way to capturing properties of `real' data for selected important combinatorial problems.

Publications and Reports

  1. Complexity-theoretic models of phase-transitions in search problems. Theoretical Computer Science, 249(2), 243-263, (2000) (P.E. Dunne, A.M. Gibbons, M.Zito)
  2. A sharp threshold for the phase transition of a restricted satisfiability problem for horn clauses (to appear: Jnl. of Logic and Algebraic Prog.) (P.E. Dunne, T.J.M. Bench-Capon)
  3. Linear time maxim induced matching algorithm for trees Nordic JNl. of Computing, 7, 58-63, (2000) (M. Zito)
  4. An improved upper bound on the non-3-colourability threshold, Inf. Proc. Letters, 65, 17-23, (1998) (P.E. Dunne, M. Zito)
  5. Maximum induced matchings of random cubic graphs, Proc. 6th COCOON, Springer-Verlag, LNCS 1858, 34-43 (2000) (W.Duckworth, N.C. Wormald, M.Zito)
  6. Small maximal matchings in random graphs, Proc. LATIN 2000 Springer-Verlag, LNCS 1776, 18-27, (2000), (M.Zito)
  7. Efficient web searching using temporal factors, WADS`99, Springer-Verlag, LNCS 1663, 294-305 (1999), (A.M.Gibbons, M.Zito, et al.)
  8. Algorithms and complexity issues concerning phase-transition phenomena in combinatorial problems, Proc. 10th AWOCA, 76-90, (1999), (P.E. Dunne, A.M. Gibbons, M. Zito)
  9. Induced matchings in regular graphs and trees, WG'99, Springer-Verlag, LNCS 1665, 89-100, (1999), (M.Zito)
  10. On complexity-theoretic models of phase-transitions in search problems, Proc. 9th AWOCA, 85-96, (1998), (P.E. Dunne, A.M. Gibbons, M. Zito)
  11. Phase-transitions in algorithmically undecidable languages, (Internal report), (P.E. Dunne, A.M. Gibbons, M.Zito)

Research Seminars and Conference Talks (OHP Versions)

  1. General Introductory Seminar
  2. Overview Talk (Opening presentation at EPSRC/MathfIT Workshop on Phase-Transition Phenomena.
  3. Sharp Theshold for restricted horn clause satifiability

EPSRC/MathfIT Workshop on Phase Transition Phenomena
January 25th-27th 1999
University of Liverpool

Report on above Bulletin of the EATCS, 68, 180-188, (June 1999)