Vertex cover

Given a graph G = (V, E) and an integer k, is there a subset of vertices S \subseteq V such that | S | \le k, and for each edge (u, v) either u \in S or v \in S or both?

Finding small vertex covers

Q. VERTEX-COVER is \mathcal{NP}-complete. But what if k is small?

Brute force. O(k n^{k+1}).

• Try all C(n, k) = O(n^k) subsets of size k.
• Takes O(k n) time to check whether a subset is a vertex cover.

Goal. Limit exponential dependency on k, say to O(2^k k n).

Finding small vertex covers

Claim. Let (u, v) be an edge of G. G has a vertex cover of size \le k iff at least one of G - \{ u \} and G - \{ v \} has a vertex cover of size \le k - 1.

Pf. \Rightarrow Suppose G has a vertex cover S of size \le k.

• S contains either u or v (or both). Assume it contains u.
• S - \{ u \} is a vertex cover of G - \{ u \}.

Pf. \Leftarrow Suppose S is a vertex cover of G - \{ u \} of size \le k - 1.

• Then S \cup \{ u \} is a vertex cover of G.

Finding small vertex covers: algorithm

Claim. The following algorithm determines if G has a vertex cover of size \le k in O(2^k kn) time.

Vertex-Cover(G, k)

1. if (G contains no edges) return true;
2. if (G contains \ge kn edges) return false;
3. let (u, v) be any edge of G;
   1. a = Vertex-Cover(G - \{u\}, k-1);
   2. b = Vertex-Cover(G - \{v\}, k-1);
4. return (a or b);

Pf.

• Correctness follows from previous two claims.
• There are \le 2^{k+1} nodes in the recursion tree; each invocation takes O(kn) time.

Finding small vertex covers: recursion tree

T(n,k) = \left\{ \begin{array}{ll} c & \text{if}\ k = 0 \\ cn & \text{if}\ k = 1 \Rightarrow T(n,k) \le 2^k ckn \\ 2T(n,k-1) + ckn & \text{if}\ k > 1 \\ \end{array}\right.

Independent set on trees

Independent set on trees. Given a tree, find a max-cardinality subset of nodes such that no two are adjacent.

Pf. [exchange argument]

• Consider a max-cardinality independent set S.
• If v \in S, we’re done.
• Otherwise, let (u, v) denote the lone edge incident to v.
  • if u \notin S and v \notin S, then S \cup \{ v \} is independent \Rightarrow S not maximum
  • if u \in S and v \notin S, then S \cup \{ v \} - \{ u \} is independent

IS on trees: greedy

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

INDEPENDENT-SET-IN-A-FOREST(F)

1. S = \emptyset;
2. WHILE (F has at least 1 edge)
   1. Let v be a leaf node and let (u, v) be the lone edge incident to v;
   2. S = S \cup \{ v \};
   3. F = F - \{ u, v \};
3. RETURN S \cup { \text{nodes remaining in}\ F };

Remark. Can implement in O(n) time by maintaining nodes of degree 1 in postorder.

Demo: greedy for IS on trees

Weighted independent set on trees

Weighted independent set on trees. Given a tree and node weights w_v \ge 0, find an independent set S that maximizes \sum_{v \in S} w_v.

Observation. If (u, v) is an edge such that v is a leaf node, then either OPT includes u or OPT includes all leaf nodes incident to u.

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

• OPT_{in} (u) = max-weight IS in subtree rooted at u, including u.
• OPT_{out} (u) = max-weight IS in subtree rooted at u, excluding u.
• Goal: \max \{ OPT_{in} (r), OPT_{out} (r) \}.

Weighted IS on trees: DP

Theorem. The DP algorithm computes max weight of an independent set in a tree in O(n) time.

• note: can also find independent set itself (not just value)

WEIGHTED-INDEPENDENT-SET-IN-A-TREE (T)

1. Root the tree T at any node r;
2. S = \emptyset;
3. FOREACH (node u of T in postorder/topological order)
   1. IF (u is a leaf node)
      1. M_{in}[u] = w_u; M_{out}[u] = 0;
   2. ELSE
      1. M_{in}[u] = w_u + \sum_{v \in children(u)} M_{out}[v];
      2. M_{out}[u] = \sum_{v \in children(u)} \max \{ M_{in}[v], M_{out}[v] \};
4. RETURN \max \{ M_{in}[r], M_{out}[r] \};

NP-hard problems on trees: intuition

Independent set on trees. Tractable because we can find a node that breaks the communication among the subproblems in different subtrees.

Graphs of bounded tree width. Elegant generalization of trees that:

• Captures a rich class of graphs that arise in practice.
• Enables decomposition into independent pieces.

Wavelength-division multiplexing

Wavelength-division multiplexing (WDM). Allows m communication streams (arcs) to share a portion of a fiber optic cable, provided they are transmitted using different wavelengths.

Ring topology. Special case is when network is a cycle on n nodes.

Review: interval coloring

Interval coloring (partitioning). Greedy algorithm finds coloring such that number of colors equals depth of schedule.

• Depth. Maximum number that pass over any single point on the time-line.

(Almost) transforming coloring

Circular arc coloring. Given a set of n arcs with depth d \le 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.

Circular arc coloring: DP

Dynamic programming algorithm.

• 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.

Circular arc coloring: running time

Running time. O(k! \cdot n).

• The algorithm has n phases.
• Bottleneck in each phase is enumerating all consistent colorings.
• There are at most k intervals through v_i, so there are at most k! colorings to consider.

Remark. This algorithm is practical for small values of k (say k = 10) even if the number of nodes n (or paths) is large.

Vertex cover

Given a graph G = (V, E) and an integer k, is there a subset of vertices S \subseteq V such that | S | \le k, and for each edge (u, v) either u \in S or v \in S or both?

Vertex cover and matching

Weak duality. Let M be a matching, and let S be a vertex cover. Then, | M | ≤ | S |.
Pf. Each vertex can cover at most one edge in any matching.

König-Egerváry Theorem

Theorem. [König-Egerváry] In a bipartite graph, the max cardinality of a matching is equal to the min cardinality of a vertex cover.

König-Egerváry Theorem: proof

Theorem. [König-Egerváry] In a bipartite graph, the max cardinality of a matching is equal to the min cardinality of a vertex cover.

• Suffices to find matching M and cover S such that | M | = | S |.
• Formulate max flow problem as for bipartite matching.
• Let M be max cardinality matching and let (A, B) be min cut.

König-Egerváry Theorem: proof (cont.)

Theorem. [König-Egerváry] In a bipartite graph, the max cardinality of a matching is equal to the min cardinality of a vertex cover.

• Suffices to find matching M and cover S such that | M | = | S |.

• Formulate max flow problem as for bipartite matching.

• Let M be max cardinality matching and let (A, B) be min cut.

• Define L_A = L \cap A, L_B = L \cap B , R_A = R \cap A, R_B = R \cap B.

• Claim 1. S = L_B ∪ R_A is a vertex cover.

  • consider (u, v) \in E
  • u \in L_A, v \in R_B impossible since infinite capacity
  • thus, either u \in L_B or v \in R_A or both

• Claim 2. | M | = | S |.

  • max-flow min-cut theorem \Rightarrow | M | = cap(A, B)
  • only edges of form (s, u) or (v, t) contribute to cap(A, B)
  • | M | = cap(A, B) = | L_B | + | R_A | = | S |.