6.854 Notes #22

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