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.
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