O'Reilly logo

Advanced Graph Theory and Combinatorics by Michel Rigo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 is1. 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required