Important Cuts

100 %
0 %
Information about Important Cuts

Published on March 5, 2014

Author: ASPAK2014

Source: slideshare.net

I MPORTANT CUTS, I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS Saket Saurabh Institute of Mathematical Sciences Chennai, India ASPAK 2015 IMSc, India March 3–8, 2014 Based on slides of Dániel Marx I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 1/33

Overview Main message: Small cuts/separators in graphs have interesting extremal properties that can be exploited in combinatorial and algorithmic results. Bounding the number of “important” cuts/separators. Edge/vertex versions, directed/undirected versions. Algorithmic applications: FPT algorithm for M ULTIWAY F EEDBACK V ERTEX S ET. CUT and D IRECTED I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 2/33

Cuts An (X , Y )-cut is a set S of edges that separate X and Y for each other, that is, G S has no X − Y path. An (X , Y )-cut S is a minimum (X , Y )-cut if there is no (X , Y )-cut S ′ with |S ′ | < |S|. An (X , Y )-cut is (inclusionwise) minimal if there is no (X , Y )-cut S ′ with S′ ⊂ S I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 3/33

Characterizing Cuts Want to view them as edges on the boundary of a certain set of vertices. If G is an undirected graph and R ⊆ V (G ) is a set of vertices, then we denote by ∆G (R) the set of edges with exactly one endpoint in R . Let S be a minimal (X , Y )-cut in G and let R be the set of vertices reachable from X in G S; clearly, we have X ⊆ R ⊆ V (G ) Y . Then it is easy to see that S is precisely ∆(R). I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 4/33

Characterizing Cuts If S is a minimal (X , Y )-cut, then S = ∆(R), where R is the set of vertices reachable from X in G S. Proof on board. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 5/33

Menger’s Theorem The well-know Max-Flow Min-Cut duality implies that the size of the minimum (X , Y )-cut is the same as the maximum number of pairwise edge-disjoint X − Y paths. ALGORITHM Given a graph G , disjoint sets X , Y ⊆ V (G ), and an integer k, there is an O(k(|V (G )| + |E (G )|)) time algorithm that either correctly concludes that there is no (X , Y )-cut of size at most k, or returns a minimum (X , Y )-cut ∆(R) and a collection of |∆(R)| pairwise edge-disjoint X − Y paths. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 6/33

Submodular We say that f is submodular if it satisfies the following inequality for every X , Y ⊆ V (G ): f (A) + f (B) ≥ f (A ∩ B) + f (A ∪ B). (1) Let δG (or δ) denote the function from 2V (G ) → N such that δ(X ) is the number of edges with one endpoint in X and other in V (G ) X . I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 7/33

Submodularity Fact: The function δ is submodular: for arbitrary sets A, B, |δ(A)| + |δ(B)| ≥ |δ(A ∩ B)| + |δ(A ∪ B)| I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 8/33

Submodularity Fact: The function δ is submodular: for arbitrary sets A, B, |δ(A)| + |δ(B)| ≥ |δ(A ∩ B)| + |δ(A ∪ B)| Proof: Determine separately the contribution of the different types of edges. A B I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 8/33

Submodularity Fact: The function δ is submodular: for arbitrary sets A, B, |δ(A)| + |δ(B)| 0 ≥ |δ(A ∩ B)| 1 1 + |δ(A ∪ B)| 0 Proof: Determine separately the contribution of the different types of edges. A B I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 8/33

Submodularity Fact: The function δ is submodular: for arbitrary sets A, B, |δ(A)| + |δ(B)| 1 ≥ |δ(A ∩ B)| 0 1 + |δ(A ∪ B)| 0 Proof: Determine separately the contribution of the different types of edges. A B I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 8/33

Submodularity Fact: The function δ is submodular: for arbitrary sets A, B, |δ(A)| + |δ(B)| 0 ≥ |δ(A ∩ B)| 1 0 + |δ(A ∪ B)| 1 Proof: Determine separately the contribution of the different types of edges. A B I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 8/33

Submodularity Fact: The function δ is submodular: for arbitrary sets A, B, |δ(A)| + |δ(B)| 1 ≥ |δ(A ∩ B)| 0 0 + |δ(A ∪ B)| 1 Proof: Determine separately the contribution of the different types of edges. A B I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 8/33

Submodularity Fact: The function δ is submodular: for arbitrary sets A, B, |δ(A)| + |δ(B)| 1 ≥ |δ(A ∩ B)| 1 1 + |δ(A ∪ B)| 1 Proof: Determine separately the contribution of the different types of edges. A B I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 8/33

Submodularity Fact: The function δ is submodular: for arbitrary sets A, B, |δ(A)| + |δ(B)| 1 ≥ |δ(A ∩ B)| 1 0 + |δ(A ∪ B)| 0 Proof: Determine separately the contribution of the different types of edges. A B I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 8/33

Submodularity Consequence: Let λ be the minimum (X , Y )-cut size. There is a unique maximal Rmax ⊇ X such that δ(Rmax ) is an (X , Y )-cut of size λ. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 9/33

Submodularity Consequence: Let λ be the minimum (X , Y )-cut size. There is a unique maximal Rmax ⊇ X such that δ(Rmax ) is an (X , Y )-cut of size λ. Proof: Let R1 , R2 ⊇ X be two sets such that δ(R1 ), δ(R2 ) are (X , Y )-cuts of size λ. Y |δ(R1 )| + |δ(R2 )| ≥ |δ(R1 ∩ R2 )| + |δ(R1 ∪ R2 )| λ λ ≥λ R1 ⇒ |δ(R1 ∪ R2 )| ≤ λ R2 X Note: Analogous result holds for a unique minimal Rmin . I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 9/33

Figure 1: A graph G with 3 edge-disjoint (X , Y )-paths and the (X , Y )cuts Rmin and Rmax . I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 10/33

Important cuts Definition: δ(R) is the set of edges with exactly one endpoint in R. Definition: A set S of edges is an (X , Y )-cut if there is no X − Y path in G S and no proper subset of S breaks every X − Y path. Observation: Every (X , Y )-cut S can be expressed as S = δ(R) for some X ⊆ R and R ∩ Y = ∅. δ(R) Y X R I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 11/33

Important cuts Definition: An (X , Y )-cut δ(R) is important if there is no (X , Y )-cut δ(R ′ ) with R ⊂ R ′ and |δ(R ′ )| ≤ |δ(R)|. Note: Can be checked in polynomial time if a cut is important. δ(R) Y X R I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 11/33

Important cuts Definition: An (X , Y )-cut δ(R) is important if there is no (X , Y )-cut δ(R ′ ) with R ⊂ R ′ and |δ(R ′ )| ≤ |δ(R)|. Note: Can be checked in polynomial time if a cut is important. δ(R) Y X δ(R ′ ) R R′ I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 11/33

Important cuts Definition: An (X , Y )-cut δ(R) is important if there is no (X , Y )-cut δ(R ′ ) with R ⊂ R ′ and |δ(R ′ )| ≤ |δ(R)|. Note: Can be checked in polynomial time if a cut is important. δ(R) Y X R I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 11/33

Some Properties Let G be an undirected graph and X , Y ⊆ V (G ) two disjoint sets of vertices. Let S be an (X , Y )-cut and let R be the set of vertices reachable from X in G S. Then there is an important (X , Y )-cut S ′ = ∆(R ′ ) (possibly, S ′ = S) such that |S ′ | ≤ |S| and R ⊆ R ′ . Proof on board. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 12/33

Some Properties Let G be a graph, X , Y ⊆ V (G ) be two disjoint sets of vertices, and S = ∆(R) be an important (X , Y ) cut. 1. For every e ∈ S, the set S {e} is an important (X , Y )-cut in G e. 2. If S is an (X ′ , Y )-cut for some X ′ ⊃ X , then S is an important (X ′ , Y )-cut. Proof on board. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 13/33

Important cuts The number of important cuts can be exponentially large. Example: Y 1 k/2 2 X This graph has exactly 2k/2 important (X , Y )-cuts of size at most k. Theorem: There are at most 4k important (X , Y )-cuts of size at most k. (Proof is implicit in [Chen, Liu, Lu 2007], worse bound in [M. 2004].) I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 14/33

Important cuts Theorem: There are at most 4k important (X , Y )-cuts of size at most k. Proof: Let λ be the minimum (X , Y )-cut size and let δ(Rmax ) be the unique important cut of size λ such that Rmax is maximal. First we show that Rmax ⊆ R for every important cut δ(R). I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 15/33

Important cuts Theorem: There are at most 4k important (X , Y )-cuts of size at most k. Proof: Let λ be the minimum (X , Y )-cut size and let δ(Rmax ) be the unique important cut of size λ such that Rmax is maximal. First we show that Rmax ⊆ R for every important cut δ(R). By the submodularity of δ: |δ(Rmax )| + |δ(R)| ≥ |δ(Rmax ∩ R)| + |δ(Rmax ∪ R)| λ ≥λ ⇓ |δ(Rmax ∪ R)| ≤ |δ(R)| ⇓ If R = Rmax ∪ R, then δ(R) is not important. Thus the important (X , Y )- and (Rmax , Y )-cuts are the same. ⇒ We can assume X = Rmax . I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 15/33

Important cuts Theorem: There are at most 4k important (X , Y )-cuts of size at most k. Search tree algorithm for enumerating all these separators: An (arbitrary) edge uv leaving X = Rmax is either in the cut or not. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 16/33

Important cuts Theorem: There are at most 4k important (X , Y )-cuts of size at most k. Search tree algorithm for enumerating all these separators: An (arbitrary) edge uv leaving X = Rmax is either in the cut or not. Branch 1: If uv ∈ S, then S uv is an important (X , Y )-cut of size at most k − 1 in G uv . dsfsdfds Branch 2: If uv ∈ S, then S is an important (X ∪ v , Y )-cut of size at most k in G . X = Rmax u v Y dsfsdfds I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 16/33

Important cuts Theorem: There are at most 4k important (X , Y )-cuts of size at most k. Search tree algorithm for enumerating all these separators: An (arbitrary) edge uv leaving X = Rmax is either in the cut or not. Branch 1: If uv ∈ S, then S uv is an important (X , Y )-cut of size at most k − 1 in G uv . ⇒ k decreases by one, λ decreases by at most 1. Branch 2: If uv ∈ S, then S is an important (X ∪ v , Y )-cut of size at most k in G . X = Rmax u v Y ⇒ k remains the same, λ increases by 1. The measure 2k − λ decreases in each step. ⇒ Height of the search tree ≤ 2k ⇒ ≤ 22k important cuts of size ≤ k. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 16/33

Important cuts Example: The bound 4k is essentially tight. X Y I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 17/33

Important cuts Example: The bound 4k is essentially tight. X Y Any subtree with k leaves gives an important (X , Y )-cut of size k. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 17/33

Important cuts Example: The bound 4k is essentially tight. X Y Any subtree with k leaves gives an important (X , Y )-cut of size k. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 17/33

Important cuts Example: The bound 4k is essentially tight. X Y Any subtree with k leaves gives an important (X , Y )-cut of size k. The number of subtrees with k leaves is the Catalan number Ck−1 = 1 2k − 2 k k −1 ≥ 4k /poly(k). I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 17/33

Simple application Lemma: At most k · 4k edges incident to t can be part of an inclusionwise minimal s − t cut of size at most k. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 18/33

Simple application Lemma: At most k · 4k edges incident to t can be part of an inclusionwise minimal s − t cut of size at most k. Proof: We show that every such edge is contained in an important (s, t)-separator of size at most k. v s t R Suppose that vt ∈ δ(R) and |δ(R)| = k. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 18/33

Simple application Lemma: At most k · 4k edges incident to t can be part of an inclusionwise minimal s − t cut of size at most k. Proof: We show that every such edge is contained in an important (s, t)-separator of size at most k. v s t R R′ Suppose that vt ∈ δ(R) and |δ(R)| = k. There is an important (s, t)-cut δ(R ′ ) with R ⊆ R ′ and |δ(R ′ )| ≤ k. Clearly, vt ∈ δ(R ′ ): v ∈ R, hence v ∈ R ′ . I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 18/33

Anti isolation Let s, t1 , ... , tn be vertices and S1 , ... , Sn be sets of at most k edges such that Si separates ti from s, but Si does not separate tj from s for any j = i. It is possible that n is “large” even if k is “small.” t1 t2 t4 t3 t5 t6 s I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 19/33

Anti isolation Let s, t1 , ... , tn be vertices and S1 , ... , Sn be sets of at most k edges such that Si separates ti from s, but Si does not separate tj from s for any j = i. It is possible that n is “large” even if k is “small.” t1 t2 t3 t4 t5 t6 S1 s I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 19/33

Anti isolation Let s, t1 , ... , tn be vertices and S1 , ... , Sn be sets of at most k edges such that Si separates ti from s, but Si does not separate tj from s for any j = i. It is possible that n is “large” even if k is “small.” t1 t2 t3 t4 t5 t6 S2 s I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 19/33

Anti isolation Let s, t1 , ... , tn be vertices and S1 , ... , Sn be sets of at most k edges such that Si separates ti from s, but Si does not separate tj from s for any j = i. It is possible that n is “large” even if k is “small.” t1 t2 t4 t3 t5 t6 S3 s I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 19/33

Anti isolation Let s, t1 , ... , tn be vertices and S1 , ... , Sn be sets of at most k edges such that Si separates ti from s, but Si does not separate tj from s for any j = i. It is possible that n is “large” even if k is “small.” t1 t2 t4 t3 t5 t6 S1 s Is the opposite possible, i.e., Si separates every tj except ti ? I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 19/33

Anti isolation Let s, t1 , ... , tn be vertices and S1 , ... , Sn be sets of at most k edges such that Si separates ti from s, but Si does not separate tj from s for any j = i. It is possible that n is “large” even if k is “small.” t1 t2 t4 t3 t5 t6 S2 s Is the opposite possible, i.e., Si separates every tj except ti ? I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 19/33

Anti isolation Let s, t1 , ... , tn be vertices and S1 , ... , Sn be sets of at most k edges such that Si separates ti from s, but Si does not separate tj from s for any j = i. It is possible that n is “large” even if k is “small.” t1 t2 t4 t3 t5 t6 S3 s Is the opposite possible, i.e., Si separates every tj except ti ? I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 19/33

Anti isolation Let s, t1 , ... , tn be vertices and S1 , ... , Sn be sets of at most k edges such that Si separates ti from s, but Si does not separate tj from s for any j = i. It is possible that n is “large” even if k is “small.” t1 t2 t4 t3 t5 t6 S3 s Is the opposite possible, i.e., Si separates every tj except ti ? Lemma: If Si separates tj from s if and only j = i and every Si has size at most k, then n ≤ (k + 1) · 4k+1 . I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 19/33

Anti isolation t t1 t2 t3 t4 t5 t6 S3 s Is the opposite possible, i.e., Si separates every tj except ti ? Lemma: If Si separates tj from s if and only j = i and every Si has size at most k, then n ≤ (k + 1) · 4k+1 . Proof: Add a new vertex t. Every edge tti is part of an (inclusionwise minimal) (s, t)-separator of size at most k + 1. Use the previous lemma. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 19/33

Anti isolation t t1 t2 t3 t4 t5 t6 S2 s Is the opposite possible, i.e., Si separates every tj except ti ? Lemma: If Si separates tj from s if and only j = i and every Si has size at most k, then n ≤ (k + 1) · 4k+1 . Proof: Add a new vertex t. Every edge tti is part of an (inclusionwise minimal) (s, t)-separator of size at most k + 1. Use the previous lemma. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 19/33

Anti isolation t t1 t2 t3 t4 t5 t6 S1 s Is the opposite possible, i.e., Si separates every tj except ti ? Lemma: If Si separates tj from s if and only j = i and every Si has size at most k, then n ≤ (k + 1) · 4k+1 . Proof: Add a new vertex t. Every edge tti is part of an (inclusionwise minimal) (s, t)-separator of size at most k + 1. Use the previous lemma. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 19/33

M ULTIWAY C UT Definition: A multiway cut of a set of terminals T is a set S of edges such that each component of G S contains at most one vertex of T . t1 M ULTIWAY C UT Input: Graph G , set T of vertices, integer k Find: t2 t3 t5 A multiway cut S of at most k edges. t4 t4 Polynomial for |T | = 2, but NP-hard for any fixed |T | ≥ 3 [Dalhaus et al. 1994]. Trivial to solve in polynomial time for fixed k (in time nO(k) ). Theorem: M ULTIWAY CUT can be solved in time 4k · nO(1) , i.e., it is fixed-parameter tractable (FPT) parameterized by the size k of the solution. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 20/33

M ULTIWAY C UT Intuition: Consider a t ∈ T . A subset of the solution S is a (t, T t)-cut. t I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 21/33

M ULTIWAY C UT Intuition: Consider a t ∈ T . A subset of the solution S is a (t, T t)-cut. t There are many such cuts. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 21/33

M ULTIWAY C UT Intuition: Consider a t ∈ T . A subset of the solution S is a (t, T t)-cut. t There are many such cuts. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 21/33

M ULTIWAY C UT Intuition: Consider a t ∈ T . A subset of the solution S is a (t, T t)-cut. t There are many such cuts. But a cut farther from t and closer to T t seems to be more useful. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 21/33

M ULTIWAY C UT and important separators Pushing Lemma: Let t ∈ T . The M ULTIWAY C UT problem has a solution S that contains an important (t, T t)-cut. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 22/33

M ULTIWAY C UT and important separators Pushing Lemma: Let t ∈ T . The M ULTIWAY C UT problem has a solution S that contains an important (t, T t)-cut. Proof: Let R be the vertices reachable from t in G S for a solution S. t R I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 22/33

M ULTIWAY C UT and important separators Pushing Lemma: Let t ∈ T . The M ULTIWAY C UT problem has a solution S that contains an important (t, T t)-cut. Proof: Let R be the vertices reachable from t in G S for a solution S. t R R′ If δ(R) is not important, then there is an important cut δ(R ′ ) with R ⊂ R ′ and |δ(R ′ )| ≤ |δ(R)|. Replace S with S ′ := (S δ(R)) ∪ δ(R ′ ) ⇒ |S ′ | ≤ |S| I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 22/33

M ULTIWAY C UT and important separators Pushing Lemma: Let t ∈ T . The M ULTIWAY C UT problem has a solution S that contains an important (t, T t)-cut. Proof: Let R be the vertices reachable from t in G S for a solution S. t u R v R′ If δ(R) is not important, then there is an important cut δ(R ′ ) with R ⊂ R ′ and |δ(R ′ )| ≤ |δ(R)|. Replace S with S ′ := (S δ(R)) ∪ δ(R ′ ) ⇒ |S ′ | ≤ |S| S ′ is a multiway cut: (1) There is no t-u path in G S ′ and (2) a u-v path in G S ′ implies a t-u path, a contradiction. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 22/33

M ULTIWAY C UT and important separators Pushing Lemma: Let t ∈ T . The M ULTIWAY C UT problem has a solution S that contains an important (t, T t)-cut. Proof: Let R be the vertices reachable from t in G S for a solution S. t u R v R′ If δ(R) is not important, then there is an important cut δ(R ′ ) with R ⊂ R ′ and |δ(R ′ )| ≤ |δ(R)|. Replace S with S ′ := (S δ(R)) ∪ δ(R ′ ) ⇒ |S ′ | ≤ |S| S ′ is a multiway cut: (1) There is no t-u path in G S ′ and (2) a u-v path in G S ′ implies a t-u path, a contradiction. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 22/33

Algorithm for M ULTIWAY C UT 1. If every vertex of T is in a different component, then we are done. 2. Let t ∈ T be a vertex that is not separated from every T t. 3. Branch on a choice of an important (t, T t) cut S of size at most k. 4. Set G := G S and k := k − |S|. 5. Go to step 1. We branch into at most 4k directions at most k times. (Better analysis gives 4k bound on the size of the search tree.) I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 23/33

M ULTICUT M ULTICUT Input: Graph G , pairs (s1 , t1 ), ... , (sℓ , tℓ ), integer k Find: A set S of edges such that G S has no si -ti path for any i. Theorem: M ULTICUT can be solved in time f (k, ℓ) · nO(1) (FPT parameterized by combined parameters k and ℓ). I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 24/33

M ULTICUT M ULTICUT Input: Graph G , pairs (s1 , t1 ), ... , (sℓ , tℓ ), integer k Find: A set S of edges such that G S has no si -ti path for any i. Theorem: M ULTICUT can be solved in time f (k, ℓ) · nO(1) (FPT parameterized by combined parameters k and ℓ). Proof: The solution partitions {s1 , t1 , ... , sℓ , tℓ } into components. Guess this partition, contract the vertices in a class, and solve M ULTIWAY C UT. Theorem: [Bousquet, Daligault, Thomassé 2011] [M., Razgon 2011] M ULTICUT is FPT parameterized by the size k of the solution. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 24/33

Directed graphs Definition: δ(R) is the set of edges leaving R. Observation: Every inclusionwise-minimal directed (X , Y )-cut S can be expressed as S = δ(R) for some X ⊆ R and R ∩ Y = ∅. Definition: An (X , Y )-cut δ(R) is important if there is no (X , Y )-cut δ(R ′ ) with R ⊂ R ′ and |δ(R ′ )| ≤ |δ(R)|. δ(R) X Y R I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 25/33

Directed graphs Definition: δ(R) is the set of edges leaving R. Observation: Every inclusionwise-minimal directed (X , Y )-cut S can be expressed as S = δ(R) for some X ⊆ R and R ∩ Y = ∅. Definition: An (X , Y )-cut δ(R) is important if there is no (X , Y )-cut δ(R ′ ) with R ⊂ R ′ and |δ(R ′ )| ≤ |δ(R)|. δ(R) X δ(R ′ ) Y R R′ I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 25/33

Directed graphs Definition: δ(R) is the set of edges leaving R. Observation: Every inclusionwise-minimal directed (X , Y )-cut S can be expressed as S = δ(R) for some X ⊆ R and R ∩ Y = ∅. Definition: An (X , Y )-cut δ(R) is important if there is no (X , Y )-cut δ(R ′ ) with R ⊂ R ′ and |δ(R ′ )| ≤ |δ(R)|. The proof for the undirected case goes through for the directed case: Theorem: There are at most 4k important directed (X , Y )-cuts of size at most k. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 25/33

D IRECTED M ULTIWAY C UT The undirected approach does not work: the pushing lemma is not true. Pushing Lemma: [for undirected graphs] Let t ∈ T . The M ULTIWAY C UT problem has a solution S that contains an important (t, T t)-cut. Directed counterexample: a s t b Unique solution with k = 1 edges, but it is not an important cut (boundary of {s, a}, but the boundary of {s, a, b} is of the same size). I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 26/33

D IRECTED M ULTIWAY C UT The undirected approach does not work: the pushing lemma is not true. Pushing Lemma: [for undirected graphs] Let t ∈ T . The M ULTIWAY C UT problem has a solution S that contains an important (t, T t)-cut. Directed counterexample: a s t b Unique solution with k = 1 edges, but it is not an important cut (boundary of {s, a}, but the boundary of {s, a, b} is of the same size). I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 26/33

D IRECTED M ULTIWAY C UT The undirected approach does not work: the pushing lemma is not true. Pushing Lemma: [for undirected graphs] Let t ∈ T . The M ULTIWAY C UT problem has a solution S that contains an important (t, T t)-cut. Directed counterexample: a s t b Unique solution with k = 1 edges, but it is not an important cut (boundary of {s, a}, but the boundary of {s, a, b} is of the same size). I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 26/33

D IRECTED M ULTIWAY C UT The undirected approach does not work: the pushing lemma is not true. Pushing Lemma: [for undirected graphs] Let t ∈ T . The M ULTIWAY C UT problem has a solution S that contains an important (t, T t)-cut. Problem in the undirected proof: t u v R R′ Replacing R by R ′ cannot create a t → u path, but can create a u → t path. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 26/33

D IRECTED M ULTIWAY C UT The undirected approach does not work: the pushing lemma is not true. Pushing Lemma: [for undirected graphs] Let t ∈ T . The M ULTIWAY C UT problem has a solution S that contains an important (t, T t)-cut. Problem in the undirected proof: t u v R R′ Replacing R by R ′ cannot create a t → u path, but can create a u → t path. Theorem: [Chitnis, Hajiaghayi, M. 2011] D IRECTED M ULTIWAY C UT is FPT parameterized by the size k of the solution. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 26/33

D IRECTED M ULTICUT D IRECTED M ULTICUT Input: Graph G , pairs (s1 , t1 ), ... , (sℓ , tℓ ), integer k Find: A set S of edges such that G S has no si → ti path for any i. Theorem: [M. and Razgon 2011] D IRECTED M ULTICUT is W[1]-hard parameterized by k. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 27/33

D IRECTED M ULTICUT D IRECTED M ULTICUT Input: Graph G , pairs (s1 , t1 ), ... , (sℓ , tℓ ), integer k Find: A set S of edges such that G S has no si → ti path for any i. Theorem: [M. and Razgon 2011] D IRECTED M ULTICUT is W[1]-hard parameterized by k. But the case ℓ = 2 can be reduced to D IRECTED M ULTIWAY C UT: s1 t1 t2 s2 I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 27/33

D IRECTED M ULTICUT D IRECTED M ULTICUT Input: Graph G , pairs (s1 , t1 ), ... , (sℓ , tℓ ), integer k Find: A set S of edges such that G S has no si → ti path for any i. Theorem: [M. and Razgon 2011] D IRECTED M ULTICUT is W[1]-hard parameterized by k. But the case ℓ = 2 can be reduced to D IRECTED M ULTIWAY C UT: x s1 t1 t2 y s2 I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 27/33

D IRECTED M ULTICUT D IRECTED M ULTICUT Input: Graph G , pairs (s1 , t1 ), ... , (sℓ , tℓ ), integer k Find: A set S of edges such that G S has no si → ti path for any i. Theorem: [M. and Razgon 2011] D IRECTED M ULTICUT is W[1]-hard parameterized by k. But the case ℓ = 2 can be reduced to D IRECTED M ULTIWAY C UT: x s1 t1 t2 y s2 I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 27/33

D IRECTED M ULTICUT D IRECTED M ULTICUT Input: Graph G , pairs (s1 , t1 ), ... , (sℓ , tℓ ), integer k Find: A set S of edges such that G S has no si → ti path for any i. Theorem: [M. and Razgon 2011] D IRECTED M ULTICUT is W[1]-hard parameterized by k. Corollary: D IRECTED M ULTICUT with ℓ = 2 is FPT parameterized by the size k of the solution. ? Open: Is D IRECTED M ULTICUT with ℓ = 3 FPT? Open: Is there an f (k, ℓ) · nO(1) algorithm for D IRECTED M ULTICUT? I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 27/33

S KEW M ULTICUT S KEW M ULTICUT Input: Graph G , pairs (s1 , t1 ), ... , (sℓ , tℓ ), integer k Find: A set S of k directed edges such that G S contains no si → tj path for any i ≤ j. s1 t1 s2 t2 s3 t3 s4 t4 I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 28/33

S KEW M ULTICUT S KEW M ULTICUT Input: Graph G , pairs (s1 , t1 ), ... , (sℓ , tℓ ), integer k Find: A set S of k directed edges such that G S contains no si → tj path for any i ≤ j. s1 t1 s2 t2 s3 t3 s4 t4 Pushing Lemma: S KEW M ULTCUT problem has a solution S that contains an important (s1 , {t1 , ... , tℓ })-cut. Theorem: [Chen, Liu, Lu, O’Sullivan, Razgon 2008] S KEW M ULTICUT can be solved in time 4k · nO(1) . I ,I P – p. 28/33 MPORTANT CUTS MPORTANT SEPARATORS AND ARAMETERIZED ALGORITHMS

D IRECTED F EEDBACK V ERTEX S ET D IRECTED F EEDBACK V ERTEX /E DGE S ET Input: Directed graph G , integer k Find: A set S of k vertices/edges such that G S is acyclic. Note: Edge and vertex versions are equivalent, we will consider the edge version here. Theorem: [Chen, Liu, Lu, O’Sullivan, Razgon 2008] D IRECTED F EEDBACK E DGE S ET is FPT parameterized by the size k of the solution. Solution uses the technique of Smith, Vetta 2004]. iterative compress ion introduced by [Reed, I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 29/33

The compression problem D IRECTED F EEDBACK E DGE S ET C OMPRESSION Input: Directed graph G , integer k, a set S ′ of k + 1 edges such that G S ′ is acyclic Find: A set S of k edges such that G S is acyclic. Easier than the original problem, as the extra input S ′ gives us useful structural information about G . Lemma: The compression problem is FPT parameterized by k. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 30/33

The compression problem Lemma: The compression problem is FPT parameterized by k. −→ − −− −→ −−− Proof: Let S ′ = {t1 s1 , ... , tk+1 sk+1 }. t 4 s4 t 3 s3 t 2 s2 t 1 s1 By guessing and removing S ∩ S ′ , we can assume that S and S ′ are disjoint [2k+1 possibilities]. By guessing the order of {s1 , ... , sk+1 } in the acyclic ordering of G S, we can assume that sk+1 < sk < · · · < s1 in G S [(k + 1)! possibilities]. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 30/33

The compression problem Lemma: The compression problem is FPT parameterized by k. −→ − −− −→ −−− Proof: Let S ′ = {t1 s1 , ... , tk+1 sk+1 }. t 4 s4 t 3 s3 t 2 s2 t 1 s1 Claim: Suppose that S ′ ∩ S = ∅. G S is acyclic and has an ordering with sk+1 < sk < · · · < s1 S covers every si → tj path for every i ≤ j I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 30/33

The compression problem Lemma: The compression problem is FPT parameterized by k. −→ − −− −→ −−− Proof: Let S ′ = {t1 s1 , ... , tk+1 sk+1 }. t 4 s4 t 3 s3 t 2 s2 t 1 s1 Claim: Suppose that S ′ ∩ S = ∅. G S is acyclic and has an ordering with sk+1 < sk < · · · < s1 S covers every si → tj path for every i ≤ j I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 30/33

The compression problem Lemma: The compression problem is FPT parameterized by k. −→ − −− −→ −−− Proof: Let S ′ = {t1 s1 , ... , tk+1 sk+1 }. t 4 s4 t 3 s3 t 2 s2 t 1 s1 Claim: Suppose that S ′ ∩ S = ∅. G S is acyclic and has an ordering with sk+1 < sk < · · · < s1 S covers every si → tj path for every i ≤ j ⇒ We can solve the compression problem by 2k+1 · (k + 1)! applications of S KEW M ULTICUT. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 30/33

Iterative compression We have given a f (k)nO(1) algorithm for the following problem: D IRECTED F EEDBACK E DGE S ET C OMPRESSION Input: Directed graph G , integer k, a set S ′ of k + 1 edges such that G S ′ is acyclic Find: A set S of k edges such that G S is acyclic. Nice, but how do we get a solution S ′ of size k + 1? I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 31/33

Iterative compression We have given a f (k)nO(1) algorithm for the following problem: D IRECTED F EEDBACK E DGE S ET C OMPRESSION Input: Directed graph G , integer k, a set S ′ of k + 1 edges such that G S ′ is acyclic Find: A set S of k edges such that G S is acyclic. Nice, but how do we get a solution S ′ of size k + 1? We get it for free! it Useful trick: erative compression (introduced by [Reed, Smith, Vetta 2004] for B IPARTITE D ELETION). I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 31/33

Iterative compression Let e1 , ... , em be the edges of G and let Gi be the subgraph containing only the first i edges (and all vertices). For every i = 1, ... , m, we find a set Si of k edges such that Gi Si is acyclic.

Iterative compression Let e1 , ... , em be the edges of G and let Gi be the subgraph containing only the first i edges (and all vertices). For every i = 1, ... , m, we find a set Si of k edges such that Gi Si is acyclic. For i = k, we have the trivial solution Si = {e1 , ... , ek }. Suppose we have a solution Si for Gi . Then Si ∪ {ei+1 } is a solution of size k + 1 in the graph Gi+1 Use the compression algorithm for Gi+1 with the solution Si ∪ {ei+1 }. If there is no solution of size k for Gi+1 , then we can stop. Otherwise the compression algorithm gives a solution Si+1 of size k for Gi+1 . We call the compression algorithm m times, everything else is polynomial. ⇒ D IRECTED F EEDBACK E DGE S ET is FPT. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 32/33

Conclusions A simple (but essentially tight) bound on the number of important cuts. Algorithmic results: FPT algorithms for M ULTIWAY C UT in undirected graphs, S KEW M ULTICUT in directed graphs, and D IRECTED F EEDBACK V ERTEX /E DGE S ET. I MPORTANT CUTS , I MPORTANT SEPARATORS AND PARAMETERIZED ALGORITHMS – p. 33/33

Add a comment

Related pages

Important Haircut - TV Tropes

The Important Haircut trope as used in popular culture. When a character cuts off his or her hair, it often symbolizes a rite of passage or bout of ...
Read more

Cut of beef - Wikipedia, the free encyclopedia

Cuts of beef are first divided into primal cuts, ... Argentine cuts. The most important cuts of beef in the Argentine cuisine are: [2] Asado: ...
Read more

Different Types of Cuts: Chop Food Like A Pro

Learn the many different types of cuts that professional chefs the world over use day to day and learn to chop food like a pro
Read more

Microtome - Wikipedia, the free encyclopedia

Important in science, microtomes are used in microscopy, ... The tissue is then cut in the microtome at thicknesses varying from 2 to 50 µm.
Read more

Why Cut is Most Important on Vimeo

maharanijewels.com (604) 727-0149. I’ve always thought that it’s important to have a balance of the 4 C’s when you are selecting that perfect diamond.
Read more

How important are regge cuts? - Home - Springer

How Important are Regge Cuts? 205 very strong cuts are needed, even stronger than those of the Michigan model in some cases. We find that ...
Read more

Cut a great promo is more important than their wrestling ...

They know you've great wrestling skills but, They don't really care about it. If You had cut great promo and get the crowd in your side then ...
Read more

dict.cc Wörterbuch :: important :: Deutsch-Englisch ...

Englisch-Deutsch-Übersetzung für important im Online-Wörterbuch dict.cc (Deutschwörterbuch).
Read more

Important cuts in IMF growth forecasts - Equal Times

Confirming the warnings expressed by the global labour movement and many other critics of the austerity policies promoted by the IMF and other institutions ...
Read more

Diamond Cut - The most important of the Diamond 4C's

Diamond cut is the most important of the 4c's. Learn about diamond cut, cut grading, diamond symmetry, diamond brilliance, GIA and AGS metrics
Read more