PhaseTransitions and Combinatorial Search
A General PhaseStructural 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 `realworld' 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

Complexitytheoretic models of phasetransitions in search problems.
Theoretical Computer Science, 249(2), 243263, (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. BenchCapon)

Linear time maxim induced matching algorithm for trees
Nordic JNl. of Computing, 7, 5863, (2000) (M. Zito)

An improved upper bound on the non3colourability threshold,
Inf. Proc. Letters, 65, 1723, (1998) (P.E. Dunne, M. Zito)

Maximum induced matchings of random cubic graphs,
Proc. 6th COCOON, SpringerVerlag, LNCS 1858, 3443 (2000) (W.Duckworth, N.C. Wormald, M.Zito)

Small maximal matchings in random graphs,
Proc. LATIN 2000 SpringerVerlag, LNCS 1776, 1827, (2000), (M.Zito)

Efficient web searching using temporal factors,
WADS`99, SpringerVerlag, LNCS 1663, 294305 (1999), (A.M.Gibbons, M.Zito, et al.)

Algorithms and complexity issues concerning phasetransition phenomena in
combinatorial problems, Proc. 10th AWOCA, 7690, (1999), (P.E. Dunne, A.M. Gibbons, M. Zito)

Induced matchings in regular graphs and trees,
WG'99, SpringerVerlag, LNCS 1665, 89100, (1999), (M.Zito)

On complexitytheoretic models of phasetransitions in search problems,
Proc. 9th AWOCA, 8596, (1998), (P.E. Dunne, A.M. Gibbons, M. Zito)

Phasetransitions 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 PhaseTransition Phenomena.

Sharp Theshold for restricted horn clause satifiability
EPSRC/MathfIT Workshop on
Phase Transition Phenomena
January 25th27th 1999
University of Liverpool
Report on above
Bulletin of the EATCS, 68, 180188, (June 1999)