Home
 

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.

  1. It executes at most d(p) machine instructions before either producing the first output or halting.
  2. 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.
  1. A polynomial space polynomial delay listing algorithm for unlabeled graphs
  2. A polynomial space polynomial delay listing algorithm for any first order one property
  3. A polynomial delay listing algorithm for Hamiltonian graphs
  4. A polynomial space polynomial delay listing algorithm for graphs with cliques of specified sizes
  5. 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