Important Cuts and (p,q)-clustering

50 %
50 %
Information about Important Cuts and (p,q)-clustering
Education

Published on March 7, 2014

Author: ASPAK2014

Source: slideshare.net

Randomized Selection of Important Separators Saket Saurabh The Institute of Mathematical Sciences, India ASPAK 2014, March 3-8

Some Basic Definitions C ⊆ V (G ) is a (p, q)-cluster if |C | ≤ p and d(C ) ≤ q. A (p, q)-partition of G is a partition of V (G ) into (p, q)-clusters.

Problem (p, q)-Partition Parameter: q Input: An undirected graph G and integers p and q. Question: Does G has a (p, q)-partition?

Problem (p, q)-Partition Parameter: q Input: An undirected graph G and integers p and q. Question: Does G has a (p, q)-partition? Goal is to show that (p, q)-Partition problem is FPT parameterized by q.

Necessary Condition

Necessary Condition A necessary condition for the existence of (p, q)-partition is that for every vertex v ∈ V (G ) there exists a (p, q)-cluster that contains v .

Is this sufficient?

Is this sufficient? Very surprisingly, it turns out that this trivial necessary condition is actually sufficient for the existence of a (p, q)-partition. HOW?

Posimodularity We say that a set function f : 2|V (G )| → R is posimodular if it satisfies the following inequality for every A, B ⊆ V (G ): f (A) + f (B) ≥ f (A B) + f (B A) (1)

Posimodularity We say that a set function f : 2|V (G )| → R is posimodular if it satisfies the following inequality for every A, B ⊆ V (G ): f (A) + f (B) ≥ f (A B) + f (B A) The function dG is posimodular. (1)

Let us move forward? Lemma Let G be an undirected graph and let p, q ≥ 0 be two integers. If every v ∈ V (G ) is contained in some (p, q)-cluster, then G has a (p, q)-partition. Furthermore, given a set of (p, q)-clusters C1 , . . . , Cn whose union is V (G ), a (p, q)-partition can be found in polynomial time. Proof. Proof on the board :).

What did we achieve? We have reduced the problem of (p, q)-Partition to (p, q)-Cluster Parameter: q Input: An undirected graph G , a veretx v ∈ V (G ) and integers p and q. Question: Does G has (p, q)-cluster containing v ?

What did we achieve? We have reduced the problem of (p, q)-Partition to (p, q)-Cluster Parameter: q Input: An undirected graph G , a veretx v ∈ V (G ) and integers p and q. Question: Does G has (p, q)-cluster containing v ?

Algorithms for (p, q)-Cluster For every fixed q, there is an nO(q) time algorithm for (p, q)-Cluster. What about parameterized by p + q?

Algorithms for (p, q)-Cluster For every fixed q, there is an nO(q) time algorithm for (p, q)-Cluster. What about parameterized by p + q?

Algorithms for (p, q)-Cluster For every fixed q, there is an nO(q) time algorithm for (p, q)-Cluster. What about parameterized by p + q? There is a 2O(p+q) nO(1) time algorithm for (p, q)-Cluster.

Towards the FPT algorithm Satellite Problem Parameter: q Input: An undirected graph G , integers p and q, a vertex v ∈ V (G ), and a partition (V0 , V1 , . . . , Vr ) of V (G ) such that v ∈ V0 and there is no edge between Vi and Vj for any 1 ≤ i < j ≤ r . Question: The task is to find a (p, q)-cluster C satisfying V0 ⊆ C such that for every 1 ≤ i ≤ r , either C ∩ Vi = ∅ or Vi ⊆ C .

Towards the FPT algorithm Satellite Problem Parameter: q Input: An undirected graph G , integers p and q, a vertex v ∈ V (G ), and a partition (V0 , V1 , . . . , Vr ) of V (G ) such that v ∈ V0 and there is no edge between Vi and Vj for any 1 ≤ i < j ≤ r . Question: The task is to find a (p, q)-cluster C satisfying V0 ⊆ C such that for every 1 ≤ i ≤ r , either C ∩ Vi = ∅ or Vi ⊆ C . For every Vi (1 ≤ i ≤ r ), we have to decide whether to include or exclude it from the solution cluster C . If we exclude Vi from C , then d(C ) increases by, d(Vi ), the number of edges between V0 and Vi . If we include Vi into C , then |C | increases by |C |.

Figure : Instance of Satellite Problem with a solution C . Excluding V2 and V4 from C decreased the size of C by the gray area, but increased d(C ) by the red edges.

Satellite Problem Lemma The Satellite Problem can be solved in polynomial time. Proof. We will come back to the proof.

Satellite Problem Lemma The Satellite Problem can be solved in polynomial time. Proof. We will come back to the proof. Hint: Think Knapsack problem.

Objective We will give a randomized algorithm for (p, q)-Cluster by reducing it to Satellite Problem.

Important Sets Definition We say that a set X ⊆ V (G ), v ∈ X is important 1. d(X ) ≤ q, 2. G [X ] is connected, 3. there is no Y ⊃ X , v ∈ Y such that d(Y ) ≤ d(X ) and G [Y ] is connected.

Important Sets The following definition connects the notion of important cuts with our problem. Definition We say that a set X ⊆ V (G ), v ∈ X is important 1. d(X ) ≤ q, 2. G [X ] is connected, 3. there is no Y ⊃ X , v ∈ Y such that d(Y ) ≤ d(X ) and G [Y ] is connected. It is easy to see that X is an important set if and only if ∆(X ) is an important (u, v )-cut of size at most q for every u ∈ X .

Enumerating Important Cuts and Important Sets Theorem Let X , Y ⊆ V (G ) be two disjoint sets of vertices in graph G , let k ≥ 0 be an integer, and let Sk be the set of all (X , Y )-important cuts of size at most k. Then |Sk | ≤ 4k and Sk can be constructed in time |Sk | · k · (|V (G )| + |E (G )|).

Minimal (p, q)-cluster Lemma Let C be an inclusionwise minimal (p, q)-cluster containing v . Then every component of G C is an important set. Proof. On board.

Main Result Lemma Given a graph G , vertex v ∈ V (G ), and integers p and q, we can construct in time 2O(q) · nO(1) an instance I of the Satellite Problem such that If some (p, q)-cluster contains v , then I is a yes-instance with probability 2−O(q) (or some 2−O(f (q)) ), If there is no (p, q)-cluster containing v , then I is a no-instance.

Algorithm For every u ∈ V (G ), u = v , enumerate every important (u, v )-cut of size at most q. For every such cut S, put the component K of G S containing u into the collection X .

Algorithm For every u ∈ V (G ), u = v , enumerate every important (u, v )-cut of size at most q. For every such cut S, put the component K of G S containing u into the collection X . Let X be a subset of X , where each member K of X is 1 chosen with probability 2 independently at random.

Algorithm For every u ∈ V (G ), u = v , enumerate every important (u, v )-cut of size at most q. For every such cut S, put the component K of G S containing u into the collection X . Let X be a subset of X , where each member K of X is 1 chosen with probability 2 independently at random. Let Z be the union of the sets in X , let V1 , . . . , Vr be the connected components of G [Z ], and let V0 = V (G ) Z . It is clear that V0 , V1 , . . . , Vr describe an instance I of the Satellite Problem, and a solution for I gives a (p, q)-cluster containing v . Thus we only need to show that if there is a (p, q)-cluster C containing v , then I is a yes instance with desired probability.

Let us ZOOM in :D Let Z be the union of the sets in X , let V1 , . . . , Vr be the connected components of G [Z ], and let V0 = V (G ) Z . It is clear that V0 , V1 , . . . , Vr describe an instance I of the Satellite Problem, and a solution for I gives a (p, q)-cluster containing v . Thus we only need to show that if there is a (p, q)-cluster C containing v , then I is a yes instance with desired probability.

What do we need? We show that the reduction works if the union Z of the selected important sets satisfies two constraints: it has to cover every component of G C and it has to be disjoint form the vertices on the boundary of C . The probability of the event that these constraints are satisfied is 2−O(f (q)) .

Let C be an inclusionwise minimal (p, q)-cluster containing v . Let S be the set of vertices on the boundary of C , i.e., the vertices of C incident to ∆(C ). Let K1 , . . . , Kt be the components of G C .

Let C be an inclusionwise minimal (p, q)-cluster containing v . Let S be the set of vertices on the boundary of C , i.e., the vertices of C incident to ∆(C ). Let K1 , . . . , Kt be the components of G C . Consider the following two events: (E1) Every component Ki of G C is in X (and hence Ki ⊆ Z ). (E2) Z ∩ S = ∅.

Let us do the probability computation on board :).

Add a comment

Related presentations

Related pages

dict.cc Wörterbuch :: cut :: Deutsch-Englisch-Übersetzung

A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z . ... a cut | cuts: VERB : to cut | cut | cut cutting ...
Read more

The austerity question: ‘How’ is as important as ‘how much ...

P; Q; R; S; T; U; V; W; X; Y; Z; Debates. ... ‘how’ is as important as ‘how ... adjustments achieved through spending cuts are less recessionary than ...
Read more

Truth table - Wikipedia, the free encyclopedia

A truth table is a mathematical table used in logic ... (also written as p ∧ q, ... as it significantly cuts down on combinatoric explosion of the ...
Read more

P&O Ferries Freight - home

a better experience. As one of Europe's leading ferry operators we recognise how important it is for our customers to have an easy and ... short-cuts ...
Read more

Factor Cuts - blif.org

Factor Cuts Satrajit Chatterjee ... Cut enumeration is an important step in many synthesis ... Nodes p,q,b,c, and d are primary inputs. modified to use ...
Read more

Fast Approximate Energy Minimization via Graph Cuts

Fast Approximate Energy Minimization via Graph Cuts ... its own distinct penalty Vp,q. This turns out to be important in many applications, ...
Read more

On Disjunctive Cuts for Combinatorial Optimization

On Disjunctive Cuts for Combinatorial Optimization ... we analyse disjunctive cuts for six important combinatorial ... ,Pq is also valid for P I ...
Read more

P A Q | LinkedIn

OM''' _9'''M'''P''Q'''2''namah...+..environment. the utter negligence of mankind towards environment is creating dangerous consequences in our life , ...
Read more

Why is strength important in basketball? - Quora

Why is strength important in basketball? ... It is important to be as strong as you can without the expense of size, ... A B C D E F G H I J K L M N O P Q ...
Read more

Show Me the Science - Why Wash Your Hands? | Handwashing | CDC

P; Q; R; S; T; U; V; W; X; Y; Z # ... Why Wash Your Hands? Language ... Keeping hands clean is one of the most important steps we can take to avoid getting ...
Read more