Topics in computational complexity

Thesis

This thesis concerns the computational complexity of several combinatorial problems.

Chapter 1 is notation and definitions. In Chapter 2 the subgraph homeomorphism problem, for fixed pattern graphs H, is considered. For the cases H and#x2245; C₆,C₇,W₄ or W₅, we obtain exact characterizations of graphs with no subgraph homeomorphic from H, and derive efficient algorithms for recognizing such graphs. We then consider counting homeomorphs, and show that if H is any finite nontrivial family of graphs then the problem of determining the number of subgraphs of a graph which are homeomorphic from a member of H is and#x2245; P-complete.

In Chapter 3 we consider languages in NP whose certificate size is bounded by a fixed, slowly growing function (say f(n)) of the input size. The classes f(n)-NP are defined in order to classify such languages; this is related to work of Kintala and Fischer. We show that several natural problems, involving Boolean satisfiability, graph colouring and Hamiltonian circuits are complete for f(n)-NP, and obtain in passing some new languages which are logspace complete for P.

Multicolouring is a natural generalization of graph colouring. We prove in Chapter 4 that determining whether a graph is (r,s)-colourable is NP-complete whenever s > 2r. This extends a result of Irving concerning the case s = 2r + 1. We also consider the complexity of some graph homomorphism problems.

In Chapter 5 we first give a polynomial time algorithm for 3-colouring graphs G whose minimum degree is > (8/ 15)|V(G)|. We then consider separability of disjoint pairs of languages, and obtain NP-hardness results for certain promise problems involving colouring.

The final Chapter concerns a problem of partitioning graphs subject to certain restrictions. We prove that several subproblems are NP-complete.

Authors: Farr, G; Farr, Graham

• Publication date: 1986
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Subjects: Percolation (Statistical physics); Computational complexity; Combinatorial enumeration problems