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*(2^{k}*k**n*)**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 ≤2
^{k + 1}nodes in the recursion tree; each invocation takes

- There are ≤2

## 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 *w*_{v} > 0, find an independent set S that maximizes maximize ∑_{v ∈ S}(*w*_{v})

**Dynamic programming solution.** Root tree at some node, say r.

*O**P**T*_{in}(*u*) = max weight independent set rooted at u, containing u.*O**P**T*_{out}(*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 *V*_{t} ⊆ *V* which satisfies three properties:

**Node Coverage**: Every node of G belongs to at least one piece*V*_{t}**Edge Coverage**: For every edge e of G, there is some piece*V*_{t}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
*X*_{a}= {a}, and for each other node i:*X*_{i}= {i, parent(i)}

General case(tree)

### Properties

Claim. Suppose deleting a node t from a tree decomposition T produces components *T*_{1}, …, *T*_{d}. Then the subgraphs *G*_{T1} − *V*_{t}, *G*_{T2} − *V*_{t}, …, *G*_{Td} − *V*_{t} 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 *V*_{x} ∩ *V*_{y} from V disconnects G into two subgraphs *G*_{x} − (*V*_{x} ∩ *V*_{y}) and *G*_{y} − (*V*_{x} ∩ *V*_{y}) that have no node in common and no edge between them.

### Tree-width

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

*W**i**d**t**h* = (*T*, {*V*_{t}}) = *m**a**x*_{t}∥*V*_{t}∥−1

所有片断*V*_{t}的大小的最大值减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, {
*V*_{t}}) 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
*V*_{t}- We can enumerate all 2
^{w + 1}possible subsets of*V*_{t}. - Once the optimal subset is fixed, the subtrees below t become independent

- We can enumerate all 2

**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*(*k*^{m}) 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 *v*_{1} and *v*_{n}. 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
*v*_{0}. - At each node
*v*_{i}, some intervals may finish, and others may begin. - Enumerate all k-colorings of the intervals through
*v*_{i}that are consistent with the colorings of the intervals through*v*_{i − 1}. - The arcs are k-colorable iff some coloring of intervals ending at cut node
*v*_{0}is consistent with original coloring of the same intervals.

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

- n phases of the algorithm.
- At each node
*v*_{i}, we enumerate all consistent colorings. There are at most k! colorings before*v*_{i}, each leading to at most k! consistent colorings after*v*_{i}.