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