# 算法设计与分析笔记0x10 —— Extending the Limits of Tractability

Must sacrifice one of three desired features.

• Solve problem to optimality.
• Solve problem in polynomial time.
• Solve arbitrary instances of the problem.

## Finding Small Vertex Covers in Polynomial Time

• Goal Move k out of exponent on n, e,g,m O(2kkn)
• Claim Let u-v be an edge of G. G has a vertex cover of size k iff at least one of G – {u} and G – {v} has a vertex cover of size k-1.
• Pf. =>
• Suppose G has a vertex cover S of size k.
• S contains either u or v (or both). Assume it contains u.
• S – {u} is a vertex cover of G – {u}.
• Pf. <=
• Suppose S is a vertex cover of G – {u} of size k-1.
• Then S {u} is a vertex cover of G.
• Claim If G has a vetex cover of size k, it has k(n-1) edges.
• Each vertex covers at most n-1 edges.
• Pf.
• There are ≤2k + 1 nodes in the recursion tree; each invocation takes

## Solving NP-Hard Problems on Trees

### Independent Set on Trees

(Maximum cardinality subset)
Fact. A tree of at least two nodes has at least two leaf nodes.
Key observation. If v is a leaf, there exists a maximum size independent set containing v.

Note:

• At least two of leaf nodes
• 任何一个叶节点，存在一个最大Independent Set包含这个叶节点

Pf. (exchange argument)

• Consider a max cardinality independent set S.
• If v S, we’re done.
• If u S and v S, then S {v} is independent => S not maximum.
• If u S and v S, then S {v} – {u} is independent.

Theorem The following greedy algorithm finds a maximum cardinality independent set in forests (and hence trees).

### Weighted Independent Set on Trees

Given a tree and node weights wv > 0, find an independent set S that maximizes maximize v ∈ S(wv)
Dynamic programming solution. Root tree at some node, say r.

• OPTin(u) = max weight independent set rooted at u, containing u.
• OPTout(u) = max weight independent set rooted at u, not containing u.

The dynamic programming algorithm find a maximum weighted independent set in trees in O(n) time.

When the input graph is a tree, NP-hard becomes polynomial.(divide and conquer or dynamic programming)
But if the graph is not a tree, => tree decompositions of graphs.

• represent the graph by a “tree-like” structure
• 去掉个别节点从而形成不连通分离

## Tree Decompositions of Graphs

Definition A tree decomposition of a graph G = (V, E) is a tree T s.t. each node t in T is associated with a piece Vt ⊆ V which satisfies three properties:

• Node Coverage: Every node of G belongs to at least one piece Vt
• Edge Coverage: For every edge e of G, there is some piece Vt containing both ends of e
• Coherence: Let t1, t2 and t3 be three nodes of T such that t2 lies on the path from t1 to t3. Then, if node v of G belongs to both $V_{t1}$ and $V_{t3}$, it also belongs to $V_{t2}$

Also known as:

• Junction tree
• Clique tree
• Join tree.

Special case: G is a tree

• Choose a root a
• Take Xa = {a}, and for each other node i: Xi = {i, parent(i)}

General case(tree)

### Properties

Claim. Suppose deleting a node t from a tree decomposition T produces components T1, …, Td. Then the subgraphs GT1 − Vt, GT2 − Vt, …, GTd − Vt have no node in common and no edge between them

Claim. Let X and Y be the two components of T after the deletion of the edge (x,y). Then deleting the set Vx ∩ Vy from V disconnects G into two subgraphs Gx − (Vx ∩ Vy) and Gy − (Vx ∩ Vy) that have no node in common and no edge between them.

### Tree-width

Def. Width of a tree decomposition (T, {Vt}) is one less than the maximum size of any piece Vt

Width = (T, {Vt}) = maxtVt∥−1

Def. Tree-width of a graph G is the minimum width of any tree decomposition of G
Comment. “-1” in the definition: so that trees have tree-width 1

• G has a tree decomposition (T, {Vt}) with tree-width w.
• Each piece V t has at most w+1 nodes.
• For each t T, the optimal independent set specifies a subset of Vt
• We can enumerate all 2w + 1 possible subsets of Vt.
• Once the optimal subset is fixed, the subtrees below t become independent

Bad news: Given a graph, it is NP-hard to determine its tree-width.
Good news: Given a graph G of tree-width less than w, we can find a tree decomposition of G of width less than 4w in time O(f(w) · mn).

• If the tree-width of G is small, it is fast to find a good tree decomposition.

## Circular Arc Coloring

Wavelength-Division Multiplexing. Allows m communication streams (arcs) to share a portion of a fiber optic cable, provided they are transmitted using different wavelengths.
Q: Do k colors suffice?
Brute force. Can determine if k colors suffice in O(km) time by trying all k-colorings.
Goal. O(f(k)) poly(m, n) on rings.

• Weak duality: number of colors depth.
• Strong duality does not hold.

### Transforming Circular Arc Coloring to Interval Coloring

Circular arc coloring. Given a set of n arcs with depth d k, can the arcs be colored with k colors?
Equivalent problem. Cut the network between nodes v1 and vn. The arcs can be colored with k colors iff the intervals can be colored with k colors in such a way that “sliced” arcs have the same color.

• Assign distinct color to each interval which begins at cut node v0.
• At each node vi, some intervals may finish, and others may begin.
• Enumerate all k-colorings of the intervals through vi that are consistent with the colorings of the intervals through vi − 1.
• The arcs are k-colorable iff some coloring of intervals ending at cut node v0 is consistent with original coloring of the same intervals.

Running time. $O(k!^2 n)$.

• n phases of the algorithm.
• At each node vi, we enumerate all consistent colorings. There are at most k! colorings before vi, each leading to at most k! consistent colorings after vi.