# Fixed Parameter Tractability 6.854 Notes #22

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

## 0.2 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