Efficient Algorithms for Listing Combinatorial Structures
Leslie Ann Goldberg
Abstract: This thesis studies the problem of designing
efficient algorithms for listing combinatorial structures. The main
notion of efficiency that we use is due to Johnson, Yannakis, and
Papadimitriou. It is called polynomial delay. A listing
algorithm is said to have delay d if and only if it
satisfies the following conditions whenever it is run with any
input p.
- It executes at most d(p) machine instructions before
either producing the first output or halting.
- After any output it executes at most d(p) machine
instructions before either producing the next output or
halting.
An algorithm is said to have
polynomial delay if its delay
is bounded from above by a polynomial in the length of the input.
In the thesis we also define a weaker notion of efficiency which we
call
cumulative polynomial delay.
There are some families of combinatorial structures for which it
is easy to design a polynomial delay listing algorithm. For
example, it is easy to design a polynomial delay algorithm that
takes as input a unary integer n and list all
n-vertex graphs. In this thesis we focus on more difficult
problems such as the following.
Problem 1 - Listing unlabeled graphs
Design a polynomial delay algorithm that takes as input a unary
integer n and lists exactly one representative from each
isomorphism class in the set of n-vertex graphs.
Problem 2 - Listing Hamiltonian graphs
Design a polynomial delay algorithm that takes as input a unary
integer n and lists all Hamiltonian n-vertex
graphs.
We start the thesis by developing general methods for solving
listing problems such as 1 and 2. Then we apply the methods to
specific combinatorial families obtaining various listing
algorithms including the following.
- A polynomial space polynomial delay listing algorithm for
unlabeled graphs
- A polynomial space polynomial delay listing algorithm for any
first order one property
- A polynomial delay listing algorithm for Hamiltonian
graphs
- A polynomial space polynomial delay listing algorithm for
graphs with cliques of specified sizes
- A polynomial space cumulative polynomial delay listing
algorithm for k-colorable graphs
We conclude the thesis by presenting some related work. First, we
compare the computational difficulty of listing with the difficulty
of solving the existence problem, the construction problem, the
random sampling problem, and the counting problem. Next, we
consider a particular computational counting problem which is
related to a listing problem described earlier in the thesis. The
counting problem that we consider is the problem of evaluating
Polya's
cycle index polynomial. We show that the problem of
determining particular coefficients of the polynomial is #P-hard
and we use this result to show that the evaluation problem is
#P-hard except in certain special cases. We also show that in many
cases it is NP-hard even to evaluate the cycle index polynomial
approximately.
PhD Thesis - Price £8.00
LFCS report ECS-LFCS-92-198 (also published as
CST-89-92)
Previous |
Index |
Next