Chapter 10: Extending the Limits of Tractability

Question 1

Vertex degree

Answer 1

The degree of a node is the number of edges that are incident to it.

Question 2

Upper limit on the number of edges in a graph G = (V, E) with n nodes.

Answer 2

If G = (V, E) has
- n nodes,
- the maximum degree of any node is at most d
- and there is a vertex cover of size at most k.

Then

G has at most kd edges.

Since the degree of any node in a graph can be at most n-1, we have:

G has at most k(n-1) ≤ kn edges.

Question 3

Vertex Cover Algorithm:

Main idea formulation

Answer 3

Let e = (u, v) be any edge of G. The graph G has a vertex cover of size at most k if and only if at least one of the graphs G - {u} and G - {v} has a vertex cover size at most k-1.