Work with NP-Hard Problems

In this section, we will consider two approaches to the work with

NP-hard problems. The first approach is to study approximate
algorithms for the initial problem.

The second one is a contraction of initial NP-hard problem up to

another NP-hard problem which has good approximate algorithms,
or even up to a problem from P.

In this section, we will work mainly with optimization problems

corresponding to decision problems considered in the previous
sections.

2 / 33
A Compendium of NP Optimization Problems

Continuously updated catalog of approximability results for NP

optimization problems:

http://www.nada.kth.se/⇠viggo/wwwcompendium/node276.html

3 / 33
Set Cover Problem

First, we study an approximate algorithm for Set Cover problem

which is a greedy algorithm.

Let us consider an arbitrary set cover problem U, F where U is a

set containing N > 0 elements, and F = Sp{S1 , . . . , Sp } is a family
of subsets of the set U such that U = i=1 Si .

Stsubfamily {Si1 , . . . , Sit } of the family F is called a cover if

A
j=1 Sij = U. The number t is called the cardinality of this cover.

We consider here the problem of searching for a cover with

minimum cardinality.

4 / 33
Set Cover Problem

Let us consider the following greedy algorithm: during each step

this algorithm chooses a subset Si 2 F with minimal index i which
covers maximum number of elements uncovered during previous
steps (Si covers all elements from U that belong to Si ).

The algorithm will finish the work when all elements from U are
covered.

5 / 33
Set Cover Problem

Example 8.1. Greedy algorithm for Set Cover problem

The constructed cover is {S1 , S2 , S3 , S4 }.

6 / 33
Set Cover Problem

By Cmin we denote the minimum cardinality of a cover.

We denote by Cgreedy the cardinality of the cover constructed by

the greedy algorithm.

Theorem 8.2. Cgreedy  Cmin ln N + 1.

7 / 33
Set Cover Problem

Proof. We denote m = Cmin . If m = 1 then, as it is not difficult

to show, Cgreedy = 1 and the considered inequality holds.

Let m 2, and let Si be a subset with minimum index i for which

N
the cardinality of Si has maximum value. It is clear that |Si | m
(in the opposite case, Cmin > m which is impossible).
N 1
So after the first step we will have at most N m =N 1 m
uncovered elements in the set U.

8 / 33
Set Cover Problem

After the first step we will have the following set cover problem:
the set U \ Si and the family {S1 \ Si , . . . , Sp \ Si }. For this
problem, the minimum cardinality of a cover is at most m.

So after the second step when we choose a set Sj 2 F for which

the cardinality of Sj \ Si is maximum, the number of uncovered
2
elements in the set U will be at most N 1 m1 , etc.

After t steps the number of uncovered elements will be at most

t
N 1 m1 .

9 / 33
Set Cover Problem

Let the greedy algorithm during the process of cover construction

make q steps (and constructs a cover of cardinality q). Then after
the step number q 1 we have at least one uncovered element in
the set U.
⇣ ⌘q 1
1 q 1 1
Therefore N 1 m 1 and N 1+ m 1 . If we take
the natural logarithm
⇣ of both
⌘ sides of this inequality, we obtain
ln N (q 1) ln 1 + m1 1 .

It is known that for any natural r the inequality ln 1 + 1r > r +1

1

holds. Since m 2 we have ln N > (q 1) m1 and q < m ln N + 1.

Taking into account that m = Cmin and q = Cgreedy we obtain
Cgreedy  Cmin ln N + 1.

10 / 33
Set Cover Problem

The first bound was obtained by Nigmatullin in 1969:

Cgreedy  Cmin (1 + ln N ln Cmin ).

Almost exact bounds depending on N only were obtained by Slavik

in 1996. If N 2 then

Cgreedy < Cmin (ln N ln ln N + 0.78).

For any natural N 2 there exists a set cover problem U, F such

that |U| = N and

Cgreedy > Cmin (ln N ln ln N 0.31).

11 / 33
Set Cover Problem

The approximation ratio of the greedy algorithm,

Cgreedy
max ,
U,F :|U|=N Cmin

is almost ln N ln ln N.

The following two results show that, under some natural

assumptions about NP, the greedy algorithm is very close to the
best polynomial approximate algorithms for Set Cover problem.

12 / 33
Set Cover Problem

Feige proved in 1996 that if NP 6✓ DTIME nO(log log n) then for

any ", 0 < " < 1, there is no polynomial algorithm that for a given
set cover problem U, F constructs a cover for U, F which
cardinality is at most

(1 ")Cmin ln |U|.

DTIME nO(log log n) is the class of languages for each of which

there exists an algorithm for language recognition such that the
time complexity of the algorithm is bounded from above by
nO(log log n) , where n is the length of input word.

13 / 33
Set Cover Problem

Ras and Safra proved in 1997 that if P 6= NP then there exists

> 0 such that there is no polynomial algorithm that for a given
set cover problem U, F constructs a cover for U, F which
cardinality is at most
Cmin ln |U|.

14 / 33
Vertex Cover Problem

Vertex Cover problem is a special case of Set Cover problem. So

we can use greedy algorithm to solve Vertex Cover problem.

It is possible to show that for any natural n there exists a graph Gn

with at most
✓ ◆
1 1
n 1 + + ... +  n(ln n + 1)
2 n 1
nodes for which Cgreedy > Cmin (ln n ln 2 1) where Cgreedy is
the cardinality of the vertex cover constructed by the greedy
algorithm and Cmin is the minimal cardinality of vertex cover.

15 / 33
Vertex Cover Problem

However, there exists more accurate approximate algorithm for

Vertex Cover. We will say that a node covers edges for which this
node is one of the ends.

During each step we choose an uncovered edge and add the ends
of this edge to the constructed vertex cover. It is clear that at
least one end of the chosen edge must be in any vertex cover. So
the cardinality of constructed vertex cover is at most 2 times to
the minimum cardinality of vertex cover.

Thus, there exists a polynomial approximate algorithm for Vertex

Cover problem for which the approximation ratio is at most 2.

16 / 33
Vertex Cover Problem

Example 8.3. Approximate algorithm for Vertex Cover

17 / 33
Vertex Cover Problem

Håstad in 1997 proved that if P 6= NP then for any ", 0 < " < 1,
there is no polynomial approximate algorithm for Vertex Cover
problem which approximation ratio is at most 76 ".

18 / 33
Maximum Independent Set

In 1999 Håstad proved that if NP 6= ZPP then, for any ",

0 < " < 1, there is no polynomial approximate algorithm for
Maximum Independent Set with approximation ratio n1 " where n
is the number of nodes.

Here ZPP (Zero-error Probabilistic Polynomial time) is the

complexity class of problems for which a probabilistic Turing
machine exists which always returns the correct answer, and the
running time is polynomial on average for any input.

Note that for Maximum Independent Set the approximation ratio

for some algorithm is the maximum value of the cardinality of
maximum independent set divided by the cardinality of
independent set constructed by the algorithm. We consider
maximum among all graphs with n nodes.

19 / 33
Maximum Independent Set

Let us study now the set of trees instead of the set of all
undirected graphs. In such a case, there exists a polynomial
algorithm for Maximum Independent Set problem. This problem
can be solved for trees in linear time using dynamic programming.

20 / 33
Maximum Independent Set

Let G = (V , E ) be a tree. We choose a node r of G as the root.

Now, each node u of G defines a subtree of G with the root u.

For each u, we consider the subproblem of finding the largest

independent set in the subtree with the root u. We denote by I (u)
the number of nodes in the largest independent set in this subtree.

21 / 33
Maximum Independent Set

Let S be the largest independent set in the considered subtree.

There are two possibilities: u 2 S and u 2
/ S.

In the first case, children of u can not be included into S. In the

second case we can consider all other nodes of the subtree.

One can show that

8 9
< X X =
I (u) = max 1+ I (w ), I (w )
: ;
w 2G (u) w 2C (u)

where G (u) is the set of grandchildren of u and C (u) is the set of

children of u.

22 / 33
Maximum Independent Set

Example 8.4. Maximum independent set in tree

23 / 33
Maximum Independent Set

The number of subproblems is exactly the number of nodes. So

during the run of the algorithm it will be necessary to make at
most |V | comparisons of numbers.

It is not difficult to show that the number of additions is at most

|V | + 2|E |. So the whole number of operations of addition and
comparison of numbers is O(|V | + |E |).

24 / 33
2-SAT

We show that 2-SAT problem belongs to P.

Let F = F (x1 , . . . , xn ) be a conjunctive normal form (CNF) with

variables x1 , . . . , xn in which each clause contains exactly two
literals that are di↵erent and correspond to di↵erent variables.

We should recognize if F is satisfiable, i.e., if there exist values

1 , . . . , n 2 {0, 1} of the variables x1 , . . . , xn such that
F ( 1 , . . . , n ) = 1.

25 / 33
2-SAT

We correspond to F a directed graph G (F ) with nodes

x1 , . . . , xn , x̄1 , . . . , x̄n : for each clause a _ b from F , we draw two
edges: ā ! b and b̄ ! a.

Theorem 8.5. (Aspvall, Plass, and Tarjan, 1979) F is satisfiable

if and only if there is no a strongly connected component in G (F )
which contains both a variable and its negation.

The construction of the graph G (F ), the construction of all

strongly connected components in G (F ), and the check of the
condition of Theorem 1 require a time which is linear depending on
the number of clauses in F .

26 / 33
2-SAT

Lemma 8.6. If F is satisfiable then there is no a strongly

connected component in G (F ) which contains both a variable and
its negation.

Proof. Let F be satisfiable and 1 , . . . , n be values of variables

x1 , . . . , xn , respectively, for which F ( 1 , . . . , n ) = 1.

Let a ! b be an edge in G (F ). Then the clause ā _ b belongs to

F . Since F ( 1 , . . . , n ) = 1, we have ā _ b = 1. Therefore if a = 1
then b = 1.

27 / 33
2-SAT

Let us assume that there exists a strongly connected component in

G (F ) which contains both a variable xi and its negation x̄i .

Let i = 1. Since there is a directed path from xi to x̄i and xi = 1,

we have x̄i = 1 which is impossible.

Let i = 0. Since there is a directed path from x̄i to xi and x̄i = 1,

we have xi = 1 which is impossible.

We obtain a contradiction. Therefore there is no a strongly

connected component in G (F ) which contains both a variable and
its negation.

28 / 33
2-SAT

Lemma 8.7. If there is no a strongly connected component in

G (F ) which contains both a variable and its negation then F is
satisfiable.

Proof. Let there be no a strongly connected component in G (F )

that contains both a variable and its negation.

We now describe an algorithm which constructs values 1, . . . , n

of variables x1 , . . . , xn such that F ( 1 , . . . , n ) = 1.

29 / 33
2-SAT

We construct the graph G (F ), find all strongly connected

components in G (F ), construct corresponding meta-graph G ⇤ (F )
which nodes are strongly connected components of G (F ) (this
graph is a directed acyclic graph), and find a topological ordering
of G ⇤ (F ).

As a result, all strongly connected components of G (F ) will be

ordered: V1 , V2 . . ..

Let i 2 {1, . . . , n}, xi 2 Vl and x̄i 2 Vk . Then i = 0 if l < k and

i = 1 if l > k.

30 / 33
2-SAT

Let x1 = 1 , . . . , xn = n , and a ! b be an edge in G (F ). Let us

show that if a = 1 then b = 1.

Let us assume the contrary: a = 1 and b = 0. Since the edge

a ! b belongs to G (F ), the clause ā _ b is in F . Therefore the
edge b̄ ! ā belongs to G (F ).

Let a 2 Vl , ā 2 Vk , b 2 Vp , and b̄ 2 Vq . Since a = 1, we have

l > k. Since b = 0, we have q > p. Since a ! b and b̄ ! ā
belong to G (F ), we have p l and k q.

From the inequalities l > k , k q, and q > p it follows that

l > p. But it contradicts the inequality p l. Therefore, for each
edge a ! b in G (F ), if a = 1 then b = 1.

31 / 33
2-SAT

Let us show that F ( 1 , . . . , n ) = 1. Let us assume the contrary:

for a clause a _ b from F , a = 0 and b = 0. It is clear that the
edge ā ! b belongs to G (F ), ā = 1 and b = 0, but this is
impossible. Therefore F ( 1 , . . . , n ) = 1.

32 / 33
2-SAT
Example 8.8. Let F0 (x, y , z) = (x _ ȳ ) ^ (y _ z̄) ^ (x̄ _ z) ^ (ȳ _ z̄).
For each variable, the variable and its negation belong to di↵erent
strongly connected components of the graph G (F0 ). The tuple of
variable values ( 1 , 2 , 3 ) described in the proof of Lemma 8.7 is
equal to (0, 0, 0). We have F0 (0, 0, 0) = 1.

33 / 33