Exact Algorithms for Variants of Satisfiability and Colouring Problems

Bjarke Skjernaa

November 2004

Abstract:

This dissertation studies exact algorithms for various hard problems and give an overview of not only results but also the techniques used.

In the first part we focus on Satisfiability and several variants of Satisfiability. We present some historical techniques and results. Our main focus in the first part is on a particular variant of Satisfiability, Exact Satisfiability. Exact Satisfiability is the variant of Satisfiability where a clause is satisfied if it contains exactly one true literal. We present an algorithm solving Exact Satisfiability in time $O(2^{0.2325n})$, and an algorithm solving Exact 3-Satisfiability, the variant of Exact Satisfiability where each clause contains at most three literals, in time $O(2^{0.1379n})$. In these algorithms we use a new concept of $k$-sparse formulas, and we present a new technique called splitting loosely connected formulas, although we do not use the technique in the algorithms.

We present a new program which generates algorithms and corresponding upper bound proofs for variants of Satisfiability, and in particular Exact Satisfiability. The program uses several new techniques which we describe and compare to the techniques used in three other programs generating algorithms and upper bound proofs.

In the second part we focus on another class of NP-complete problems, colouring problems. We present several algorithms for 3-Colouring, and discuss $k$-Colouring in general. We also look at the problem of determining the chromatic number of a graph, which is the minimum number, $k$, such that the graph is $k$-colourable. We present a technique using maximal bipartite subgraphs to solve $k$-Colouring, and prove two bounds on the maximum possible number of maximal bipartite subgraphs of a graph with $n$ vertices: a lower bound of $\Omega(1.5926^n)$ and an upper bound of $O(1.8612^n)$. We also present a recent improvement of the upper bound by Byskov and Eppstein, and show a number of applications of this in colouring problems.

In the last part of this dissertation we look at a class of problems unrelated to the above, Graph Distinguishability problems. DIST$_k$ is the problem of determining if a graph can be coloured with $k$ colours, such that no non-trivial automorphism of the graph preserves the colouring. We present some results on determining the distinguishing number of a graph, which is the minimum $k$, such that the graph is in DIST$_k$. We finish by proving a new result which shows that DIST$_k$ can be reduced to DIST$_l$ for various values of $k$ and $l$

Available as PostScript, PDF.

Last modified: 2005-04-06 by webmaster.