算法设计与分析笔记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

所有片断Vt的大小的最大值减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.

Leave a Reply

Your email address will not be published.