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