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
-
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)
-
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)
-
Linear time maxim induced matching algorithm for trees
Nordic JNl. of Computing, 7, 58-63, (2000) (M. Zito)
-
An improved upper bound on the non-3-colourability threshold,
Inf. Proc. Letters, 65, 17-23, (1998) (P.E. Dunne, M. Zito)
-
Maximum induced matchings of random cubic graphs,
Proc. 6th COCOON, Springer-Verlag, LNCS 1858, 34-43 (2000) (W.Duckworth, N.C. Wormald, M.Zito)
-
Small maximal matchings in random graphs,
Proc. LATIN 2000 Springer-Verlag, LNCS 1776, 18-27, (2000), (M.Zito)
-
Efficient web searching using temporal factors,
WADS`99, Springer-Verlag, LNCS 1663, 294-305 (1999), (A.M.Gibbons, M.Zito, et al.)
-
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)
-
Induced matchings in regular graphs and trees,
WG'99, Springer-Verlag, LNCS 1665, 89-100, (1999), (M.Zito)
-
On complexity-theoretic models of phase-transitions in search problems,
Proc. 9th AWOCA, 85-96, (1998), (P.E. Dunne, A.M. Gibbons, M. Zito)
-
Phase-transitions in algorithmically undecidable languages,
(Internal report), (P.E. Dunne, A.M. Gibbons, M.Zito)
Research Seminars and Conference Talks (OHP Versions)
-
General Introductory Seminar
-
Overview Talk (Opening presentation at
EPSRC/MathfIT Workshop on Phase-Transition Phenomena.
-
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)