Advanced Graph Theory and Combinatorics

2A Glimpse at Complexity Theory

Many problems in graph theory are considered as “hard” from an algorithmic point of view. In this chapter, we present the minimal theoretical background necessary to understand the usual classification of “hard” problems (from the point of view of a “worst-case scenario”). In the last section of this chapter, we introduce the reader to a few of these problems.

2.1. Some complexity classes

Turing machines are a useful model of computation providing a formal definition for algorithms. We will not present this model but we will assume that the reader has a reasonable understanding of what an algorithm is¹. Our aim is to give a rough presentation of what are the classes P, NP and what are NP-hard and NP-complete decision problems. For references, see, for instance, [SUD 06, ARO 09].

A decision problem can be formulated as a general question depending on some input parameters for which the answer is either yes or no. An instance of a decision problem is the specific values given to the parameters. As an example, given any integer n > 1, decide whether n is prime. Or given any digraph G, decide whether G is Hamiltonian. The instances for which the answer is yes (respectively, no) are the positive instances (respectively, the negative ones). Consider a convenient coding that contains all the relevant information about an instance, i.e. a finite description of the input parameters using prescribed rules. We assume that such a coding always exists – we ...