NP Complete Graph Problems

Summary

We show that we can reduce from 3SAT to Independent Set, then from IS to Clique and Vertex Cover.

Contents

• Independent Set
  • IS in NP
  • Reduce 3SAT to IS
    • Example
  • Correctness
    • Forward Claim
    • Reverse Claim
• Clique
  • Clique in NP
  • Reduce IS to Clique
• Vertex Cover
  • VC in NP
  • Reduce IS to VC
    • Forward Claim
    • Reverse Claim

Independent Set

For an undirected graph G=(V,E), a subset of vertices S is an independent set if no edges are contained in S

• i.e $\forall x,y \in S, (x,y) \not\in E$

The challenge is to find the maximum IS

The Max IS problem is not known to be in NP since there’s no way to verify the max size in polynomial time.

Change input to include a goal g such that the size of S is at least g

IS in NP

Given input G,g and solution S, in $O(n^2)$ time we can check all pairs $\forall x,y \in S , (x,y) \not\in E$, and in O(n) time check size of S is at least g.

Reduce 3SAT to IS

Consider 3SAT input f with variables $x_1, \ldots, x_n$ and clauses $c_1, \ldots, c_m$, we’ll define a graph G and set g = m

For each clause $c_i$, create $\left\lvert c_i \right\rvert$ vertices

There will be two types of edges

• Clause edges
• Variable edges

Clause $c = \left( x_1 \lor \bar{x_3} \lor x_2 \right)$

$c = \left( \bar{x_4} \lor x_5 \right)$

$c = \left( \bar{x_1} \right)$

IS S has at most 1 vertex per clause. Since g=m, a 3SAT solution has exactly 1 vertex per clause.

We could take 1 vertex per sub-graph and create an assignment

This leads to $x_1 = T, x_5 = T, x_1 = F$

Since we have a contradiction, we need to create new edges from any $x_i \rightarrow \bar{x_i}$

These new edges (yellow in above) are variable edges

Example

$$f = \left( \bar{x} \lor y \lor \bar{z} \right) \land \left( x \lor \bar{y} \lor w \right) \land \left( \bar{x} \lor \bar{w} \right) \land \left( \bar{y} \lor z \lor w \right)$$

Corresponds to x = F, y = F, w = F, and z has no constraints

Correctness

f has a satisfying assignment $\iff$ G has an independent set of size at least g

Forward Claim

Consider a satisfying assignment for f.

For each clause c, take 1 of the satisfied literals

• add corresponding vertex to S
  • $\left\lvert S \right\rvert = m = g$

S has 1 vertex per clause and not both $x_i \text{ and } \bar{x_i}$. This corresponds to not having any clause edges nor any variable edges, so S is an IS. $\blacksquare$

Reverse Claim

Take an independent set S of size at least g.

S has 1 vertex per clause

• set corresponding literal to True
  • every clause is satisfied

No contradictory literals since we added edges $x_i \leftrightarrow \bar{x_i}$

S is a valid assignment that satisfies every clause. $\blacksquare$

Clique

Clique
A fully connected subgraph

For a graph G=(V,E), a subset of vertices S is a clique if $\forall x,y, \in S, (x,y) \in E$

Input: Undirected graph G and goal g

Output: $S \subset V$ where S is a clique of size at least g if it exists, NO otherwise

Clique in NP

Given input (G,g) and S

• $\forall x,y \in S$, check that $(x,y) \in E$
  • $O(n^3)$, trivially, down to $O(n^2)$

Reduce IS to Clique

Clique is opposite of IS.

Given an input for IS, $G=(V,E), \text{ let } \bar{G} = \left( V, \bar{E} \right) \text{ where: } \bar{E}: \left\lbrace (x,y) : (x,y) \not\in E \right\rbrace$

$(x,y) \in \bar{E} \iff (x,y) \not\in E$

S is a clique in $\bar{G} \iff$ S is an IS in $G$

Given an input for IS, $G=(V,E), \text{ let } \bar{G} & g$ be input to the clique problem.

If we get a solution S for clique, return S for IS. If we get NO, return NO.

Vertex Cover

For a graph G, a subset of vertices S is a vertex cover if every edge is touching at least one vertex in S.

$\forall (x,y) \in E, x \in S \lor y \in S$

Input: G and budget b

Output: Vertex cover S of size at most b, if one exists, NO otherwise

VC in NP

Given input (G,b) and solution S,

• $(x,y) \in E$, check x and/or y are in S
  • O(n + m)
• Check that S is at most size of b
  • O(n)

Reduce IS to VC

Claim: $S$ is a VC $\iff \bar{S}$ is an IS

Forward Claim

Take vertex cover S

$\forall (x,y) \in E : \begin{cases} \ge 1 \text{ of } \lbrace x,y \rbrace \in S \ \le 1 \text{ of } \lbrace x,y \rbrace \in \bar{S} \end{cases}$

$\therefore \bar{S}$ is an IS

Reverse Claim

Take an IS $\bar{S}$

$\forall (x,y) \in E, \le 1 \text{ of } \lbrace x,y \rbrace \in \bar{S}$

S covers every edge