61 Branching algorithm for vertex cover

Example

Given an undirected graph $G=(V,E)$ on $n$ vertices and $m$ edges, find a set $X$ of minimum size such that each edge of $G$ has at least one-endpoint in $X$.

Brute Force Algorithm

• Runs in $2^n{n}^2$ time
• Try all subsets of $X\subseteq N$ in increasing order of size of $X\to 2^n$ subsets.
• For each choice $X$, check in $n^2$ time if $X$ is a vertex cover or not

Can we design an $(2-ϵ{)}^n\cdot n^{O(1)}$ algorithm for some $ϵ>0$

• Say $1.999^n\cdot n^{O(1)}$ time algorithm ?
• Does this violate $P\ne NP$
  • No, even if $2^{\sqrt{n}}\cdot n^{O(1)}$ does not violate $P\ne NP$.

Designing an $(2-ϵ{)}^n\cdot n^{O(1)}$ algorithm for some $ϵ>0$

• Observation: No point adding a vertex of degree $1$ in the vertex cover
  • Might as well add it’s unique neighbour
• Pick a vertex $v$ of degree $\ge 2$
  • If we pick $v$ in the vertex cover, then the number of vertices reduces by $1$
  • If we do not pick $v$ in the vertex cover, then the number of vertices reduces by at least $2+1=3$
    • Not picking $v\Rightarrow$ all of its neighbours have to be picked into the vertex cover
    • $v$ has at least two neighbours
• $T(n)=:$ time needed to solve $\text{Vertex Cover}$ on graphs with $n$ vertices
  • Base case $T(2)=1$
• Then, we have the recurrence $T(n)\le T(n-1)+T(n-3)$
  • We solve both instances, and take the minimum of the two values
  • Hence, the running time is $T(n-1)+T(n-3)$
  • This is a linear homogenous recurrence
  • Linear = terms on the right hand side are raise to power one
  • Homogenous = no constants on the right hand side
• The standard way to solve such recurrences is to set $T(n)=x^n$, and then determine the value of $x$
  • Hence, our recurrence reduces to $x^n\le x^{n-1}+x^{n-3}$
  • Taking $x^{n-3}$ out as common term throughout, we get $x^3\le x^2+1$
  • This equation is satisfied for all $x\le 1.46557$
  • Hence, $1.47^n\cdot n^{O(1)}$ is an upper bound for our branching algorithm.

Faster algorithm for 3-SAT

• $3-SAT$ is a special case of the CNF-SAT problem where

  • Each clause has at most three literals
  • Instance of $3-SAT$: Is $(A\vee \neg B)\wedge (\neg A)\wedge (B\vee Z\vee \neg X)$ satisfiable ?
  • $3-SAT$ is also NP-hard

• Simplifying assumptions: Each clause has exactly 3 literals

• Let $N$ be number of variables and $M$ be number of clauses

• Brute Force tries all $2^N$ truth assignments, and for each truth assignment checks in $O(N)$ time if each of the $M$ clauses is satisfied

• So, total running time is $O(2^N\cdot N\cdot M)$

• Consider a clause $(l_1\vee l_2\vee l_3)$ for a given instance of $3-SAT$

  • For the instance to be satisfiable at least one out of $l_1,l_2,l_3$ has to be TRUE