Fixed Parameter Tractability

We've talked about approximation algorithms that do well on all instances. How about on some instances?

• For any one instance, there is polytime alg.
• Look for interesting (natural, common) “easy” classes of instances

Vertex cover

• Suppose solution has $k$ vertices
• Try all possibilities? $O(mn^k)$
• Polynomial for any fixed $k$, but in a bad way (like PAS, not FPAS).
• Of course, cannot really have FPAS since $k \leq n$ would mean it gives exact solution in polynomial time

Bounded search tree method

• Consider search space as a search tree
• Argue you can cut it short, so exponential in levels isn't too bad
• Pick any edge
  • one end is in VC
  • try each
  • each “branch” of search tree is binary
  • but after $k$ branchings you are done (success or failure clear)
  • So, $2^k$ leaves in search tree
  • $O(m)$ work per path
  • time $O(2^k m)$

Kernelization

• In polytime (independent of $k$) find a subproblem of size confined with a function of $k$ such that the solution of this subproblem extends to the whole problem
• Gives runtime of $p(n)+f(k)$, “better” than $p(n)\cdot f(k)$
• eg vertex cover
  • any vertex of degree $>k$ must be in cover
  • mark, remove with incident edges
  • remainder is covered by at most $k$ vertices of degree $< k$
  • so at most only $k^2$ edges
  • find opt in $f(k)$
  • e.g. $2^k \cdot k^2$ using bounded search tree method.

Equivalence

• Actually, kernelization is no better
• these three are equivalent:
  • algorithm with runtime $f(k)\cdot p(n)$
  • algorithm with runtime $f(k)+p(n)$
  • algorithm to reduce to kernel of size $f(k)$
• Proof is nonconstructive, however.

Treewidth

Imagine a canonical recursive solution on a graph

• Pick a vertex
• For each possible setting of it, compute optimum solution on rest of graph
• Kind of what we did in bounded search tree for FPT
• What goes wrong? Exponential search space. New problem for each setting of variable

Perhaps we can “memoize” the recursion, turn into dynamic programming?

• In many graph problems, feasibility is determined by “local” constraints on vertices and who they interact with
  • Graph coloring
  • Max independent set
  • vertex cover
  • matching
• edges in graph represent “interactions” constraining joint behavior of neighboring variables
• Perhaps only need to memoize one answer for each state of neighbors, ignoring rest of the graph
• get something exponential in the degree
• Intuition: maximum matching in a tree
  • Root tree anywhere
  • Compute, for subtree $T$ with root $v$, max matching in $T$ with $v$ matched and unmatched
  • Can evaluate for $v$ given tables of children of $v$
• intuition: vertex cover

Elimination orderings

• Represent an “unraveling” of the graph one vertex at a time, with plans to memoize
• Problem to be solved: when I eliminate a vertex, I create hidden interactions between neighbors of that vertex
• To represent those interactions, need to add edges between all neighbors.
• If can do so without ever creating large neighbor set, there is hope!

Treewidth

• Induced Treewidth: For a given graph, for any elimination ordering, induced treewidth of that ordering is the size of the largest neighbor set created by that elimination ordering
• Graph Treewidth: For any graph, its treewidth is the induced treewidth of the best elimination ordering (the one with smallest induced treewidth)
• Treewidth 1: tree
• Treewidth 2: series-parallel graphs

SAT

• Treewidth not just for problems on graphs
• Use graph to reflect interactions between any variables
• eg, edge between two variables if they share a clause
• Maintain truth-table for each clause---list of satisfying assignments for it
• Take eliminated vertex/variable $v$
• Combine its clause's truth tables---combined clause is happy with a given assignments if original set are all happy for some setting of $v$
• Reduced formula is SAT iff original is
• Size of new clause: degree of $v$
• So, if small treewidth, never create large clause
• In which case, easy to maintain tables
• Runtime: $n$ eliminations, each involving about $O(2^k)$ work, where k is the treewidth of the graph.
• When unwinding, always have satisfying assignment that can be extended to remove vertex