Purcell, Christopher (2013) Cliques, colouring and satisfiability : from structure to algorithms. PhD thesis, University of Warwick.

Preview

PDF WRAP_THESIS_Purcell_2013.pdf - Submitted Version - Requires a PDF viewer. Download (867Kb) | Preview

Request Changes to record.

Abstract

We examine the implications of various structural restrictions on the computational
complexity of three central problems of theoretical computer science
(colourability, independent set and satisfiability), and their relatives. All problems
we study are generally NP-hard and they remain NP-hard under various restrictions.
Finding the greatest possible restrictions under which a problem is computationally
difficult is important for a number of reasons. Firstly, this can make it easier to
establish the NP-hardness of new problems by allowing easier transformations. Secondly,
this can help clarify the boundary between tractable and intractable instances
of the problem.
Typically an NP-hard graph problem admits an infinite sequence of narrowing
families of graphs for which the problem remains NP-hard. We obtain a number
of such results; each of these implies necessary conditions for polynomial-time
solvability of the respective problem in restricted graph classes. We also identify
a number of classes for which these conditions are sufficient and describe explicit
algorithms that solve the problem in polynomial time in those classes. For the
satisfiability problem we use the language of graph theory to discover the very first
boundary property, i.e. a property that separates tractable and intractable instances
of the problem. Whether this property is unique remains a big open problem.

Item Type:	Thesis (PhD)
Subjects:	Q Science > QA Mathematics
Library of Congress Subject Headings (LCSH):	Graph coloring, Graph theory, NP-complete problems, Polynomials
Official Date:	October 2013
Dates:	Date Event October 2013 Submitted
Institution:	University of Warwick
Theses Department:	Mathematics Institute
Thesis Type:	PhD
Publication Status:	Unpublished
Supervisor(s)/Advisor:	Lozin, Vadim V.
Sponsors:	University of Warwick. Centre for Discrete Mathematics and its Applications (DIMAP); Engineering and Physical Sciences Research Council (EPSRC) (EP/D063191/1)
Extent:	viii, 129 leaves.
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads