WWW.ABSTRACT.DISLIB.INFO FREE ELECTRONIC LIBRARY - Abstracts, online materials

<< HOME
CONTACTS

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 7 |

# «Fixed-parameter tractability of multicut parameterized by the size of the cutset∗ D´niel Marx† Igor Razgon‡ a August 27, 2013 Abstract Given ...»

-- [ Page 4 ] --

Next we show that every vertex r reachable from u in G \ S is reachable from u in G \ S. Let P be an u − r path in G \ S and suppose that it contains a vertex q ∈ S \ S. As S is a minimal v − W separator, there is a q − W path Q that intersects S only in q. The concatenation of the preﬁx of P ending at q and Q is a u − W walk, hence Q has to contain a vertex q ∈ S. Vertex q cannot be on P ; in particular, q = q. By the deﬁnition of Q, this vertex q has to be in S \ S and hence it is reachable from v in G \ S. However, the subpath of Q from q to W does not contain any vertex of S, meaning that v is reachable also from W in G \ S, a contradiction. This shows that every vertex reachable from u in G \ S remains reachable in G \ S, contradicting the assumption that S is an important u − W separator. Therefore, S is indeed an important v − W separator.

(2) By Lemma 3.9, there are at most 4p important v − W separators of size at most p, thus by (1), vertex v can be contained in the exact shadows of at most that many members of Ip.

Combining Lemmas 3.10 and 3.13, we immediately have:

Proposition 3.14. Let R be a W -closest set and let S = N (R). Then every vertex v ∈ R ∪ N (R) is in the exact shadow of an some Sv ∈ Ip with Sv ⊆ S.

We use Prop. 3.14 to bound the probability that the constructed set Z satisﬁes the second condition of Theorem 3.6. We need the following simple observation to argue that the selection of these sets does not interfere with the ﬁrst condition of Theorem 3.6.

Lemma 3.15.

Let R be a W -closest set and let S = N (R) and S ⊆ S. Then the shadow of S is disjoint from S.

Proof. Suppose that v ∈ S is in the shadow of S ⊆ S, i.e., v ∈ S and S is a v − W separator. As v ∈ N (R), vertex v has a neighbor r ∈ R. We can assume that every component of G[R] contains a vertex of W : otherwise removing a component disjoint from W strictly decreases R without increasing |N (R)|, contradicting the assumption that R is a W -closest set. This means that there is a path from r to W fully contained in R. It follows that there is a path from v to W fully contained in R ∪ {v}, which is disjoint from S, contradicting the assumption that v is in the shadow of S.

In the simpliﬁed proof of Theorem 3.6, we select members of Ip uniformly at random and take the union of their exact shadows. In light of Lemmas 3.10 and 3.13, there is a set of at most 2p members of Ip that have to be selected and there is a set of at most N (R) · 4p members of Ip that have to avoided in order for the random selection to be successful.

Simpliﬁed proof of Theorem 3.6. The algorithm RandomSet(G, W, p) ﬁrst constructs the set Ip ; by Lemma 3.9, the size of Ip is O∗ (4p ) and can be constructed in time O∗ (4p ). Let Ip be the subset of Ip where each element from Ip occurs with probability 1 independently at random. Let Z be the union of the exact shadows of every set in Ip. We claim that the set Z satisﬁes the requirement of the theorem.

Let R be a W -closest set and let S = N (R). Let X1, X2,..., Xd ∈ Ip be the members of Ip that are fully contained in S. As |S| ≤ p, we have d ≤ 2p. By Lemma 3.15, we have that the exact

shadow of Xj is disjoint from S for every j ∈ [d]. Now consider the following events:

(E1) Z ∩ S = ∅ (E2) the exact shadow of Xj is a subset of Z for every j ∈ [d].

–  –  –

3.5 Random sampling of important separators—full proof In order to optimize the success probability, we perform the randomized selection of important separators in two phases: ﬁrst we select some members of Ip and add new edges to the graph and in the second phase we restrict our attention to members of Ip that induce cliques in the modiﬁed graph. We observe that important separators that induce cliques are nested, hence we can get a bound of p instead of 4p for the number of such separators.

Lemma 3.16.

For every vertex v ∈ V (G) \ W, there are at most p important v − W separators of size at most p inducing a clique.

Proof. Every minimal v − W separator arises as N (X) for some set X with v ∈ X and G[X] connected. The bound follows from observing that important separators inducing cliques are nested.

That is, we show that if X1 and X2 are connected sets containing v such that N (X1 ) and N (X2 ) are important v − W separators inducing cliques, then either X1 ⊂ X2 or X2 ⊂ X1.

Suppose that X1 \ X2 and X2 \ X1 are both nonempty. If X1 \ X2 = ∅ and X1 is connected, then there is a vertex x1 ∈ X1 ∩ N (X2 ). As N (X2 ) is a clique, every vertex of N (X2 ) is adjacent with x1, implying that N (X2 ) ⊆ X1 ∪ N (X1 ). If X2 \ X1 = ∅, then a symmetrical argument shows that N (X1 ) ⊆ X2 ∪ N (X2 ). We claim that N (X1 ∪ X2 ) ⊆ N (X1 ) ∩ N (X2 ) and hence |N (X1 ∪ X2 )| ≤ |N (X1 )|, |N (X2 )|; as X1 ∪ X2 ⊃ X1, X2, this would contradict the assumption that X1 and X2 are important components. Consider a vertex u ∈ N (X1 ∪ X2 ), which must have a neighbor w ∈ X1 ∪ X2. If w ∈ X1 ∩ X2, then u ∈ N (X1 ) ∩ N (X2 ) and we are done. Suppose without loss of generality that w ∈ X1 \ X2. Then u ∈ N (X1 ) ⊆ X2 ∪ N (X2 ), but u ∈ X2 by deﬁnition, hence u has to be in N (X2 ) as well.

Suppose now that X1, X2,..., Xt are connected sets containing v such that N (X1 ), N (X2 ),..., N (Xt ) are important v − W separators inducing cliques. We have shown that the Xi ’s form a chain, i.e., we can assume without loss of generality that X1 ⊂ X2 ⊂ · · · ⊂ Xt. This means that there are at most p of them, as the deﬁnition of important separator implies that |N (X1 )| |N (X2 )| · · · |N (Xt )| has to hold.

By Lemma 3.13(1), we have the following the bound:

Lemma 3.17.

Every vertex v ∈ V (G) \ W is contained in the exact shadow of at most p sets X ∈ Ip such that G[N (X)] is a clique.

Full proof of Theorem 3.6. The randomized algorithm consists of two phases. For consistency of notation, let G1 = G and Ip,1 = Ip. In the ﬁrst phase, we select a subset of Ip and obtain G2 for G1 by making the selected sets cliques. Let Ip,2 be deﬁned as Ip,1, but for graph G2 : S is in Ip,2 if it is an important v − W separator of size at most p for some vertex v ∈ V (G2 ) \ (W ∪ S) in G2. In the second phase, we select a subset of Ip inducing cliques in G2 and obtain Z as the union of the exact shadows of the selected sets.

Phase 1. In the ﬁrst phase, we select a subset Ip,1 ⊆ Ip,1 by putting every set of Ip,1 into Ip,1 with probability p1 = 4−p independently at random.

Then we make every set X ∈ Ip,1 a clique; let G2 be the graph obtained this way.

Let R be a W -closest set and let S = N (R). By Proposition 3.14, there exists a subcollection A2 of Ip,1, all being subsets of S, such that V (G) \ (R ∪ S) is covered by the exact shadows of the sets in A2. Let us estimate the probability that the events (E1) Every S ∈ A2 induces a clique in G2.

(E2) Every S ∈ A2 has the same exact shadow in G1 and in G2.

(E3) Every S ∈ A2 is in Ip,2.

occur.

Let us make a subset A1 of A2 such that for every S2 ∈ A2 and x, y ∈ S2, there is a set S1 ∈ A1 with x, y ∈ S1. In other words, the sets in A1 cover every pair {x, y} of vertices covered by the sets in A2. Since there are |S| ≤ p such pairs, it is clear that there exists a collection A1 of size at most p. Observe that, by Lemma 3.15, the shadow of every set in A1 is disjoint from S.

Let B1 contain those members of Ip,1 whose exact shadows intersect S; by Lemma 3.13, we have |B1 | ≤ |S| · 4p ≤ p · 4p. We claim that if every member of A1 is in Ip,1 and no member of B1 is in Ip,1, then (E1–E3) occur.

Consider an S ∈ A2. Assuming that every member of A1 is in Ip,1, the set G2 [S ] becomes a clique. This shows (E1).

To show (E2), that is, that S ∈ A2 has the same exact shadows in G1 and G2, we show that a subset S ⊆ S is a v − W separator for some vertex v in G1 if and only if it is in G2. This shows that S is a minimal v − W separator in G1 if and only if it is in G2, implying the equalities of the exact shadows. One direction is clear, as G1 is a subset of G2. For the other direction, suppose that S is not a v − W separator in G2. Let K be the connected component of v in G1 \ S ; by assumption K is disjoint from W. Then there have to be two vertices a ∈ K and b ∈ K ∪ S that are adjacent in G2 but not in G1. The reason why a and b are adjacent in G2 is that there is some X ∈ Ip,1 with a, b ∈ X. As we assumed that no member of B1 is in Ip,1, this means that the exact shadow of X is disjoint from S (and hence from S ). As X ∈ Ip,1, it is an important (hence minimal) q − W separator for some vertex q in its exact shadow. This means that there are paths from q to a and b in the exact shadow of X. Therefore, there is a path P from a to b in G1 whose internal vertices are in the exact shadow of X, hence disjoint from S. It follows that b is also in the component K of v in G1 \ S, a contradiction.

Finally, let us show (E3). As S ∈ Ip,1, it is an important v − W separator for some vertex v.

Again, let K be the connected component of v in G1 \ S. By the previous paragraph, S is a K − W separator in G2. This implies that S is an important v − W separator in G2 as well: if there is a separator S contradicting that S is an important v − W separator in G2, then S is a v − W separator in G1 as well (as G1 is a subgraph of G2 ) and at least one vertex of S is reachable from v in G1 \ S, which means that S contradicts that S is an important v − W separator in G1.

We can conclude that the probability that (E1–E3) occur can be bounded from below by the probability of the event that every set in A1 is selected and no set from B1 is selected. As the sets A1 and B1 are disjoint (recall that the exact shadow of every member of A1 is disjoint from S by Lemma 3.15 while the exact shadow of every member of B1 intersects S by deﬁnition), this probability is at least p 2 3 3 (1 − 4−p )p·4 · (4−p )p ≥ e−2p · 4−p = 2−O(p ) (in the inequality, we use that 1 + x ≥ exp(x/(1 + x)) for every x −1 and 1 − 4−p ≥ 1/2).

Phase 2. Ip,2 be a subset of Ip,2 where every X ∈ Ip,2 with G2 [X] being a clique appears with probability p2 = 1 − 2−p independently at random (and if a set X ∈ Ip,2 does not induce a clique in G2, then it is never selected).

Let Z be the union of the exact shadows of the sets in Ip,2.

If (E1–E3) occur, then every set in A2 is in Ip,2 and they induce cliques in G2. If additionally the events (E4) Z ∩ S = ∅, and (E5) A2 ⊆ Ip,2 occur, then every v ∈ R ∪ N (R) is in the exact shadow of some S ∈ Ip,2 and v ∈ Z follows.

Let us estimate the probability that both (E4) and (E5) hold on condition that (E1–E3) hold.

Let B2 contain those members of Ip,2 (inducing cliques) whose exact shadow in G2 intersects S; we have |B2 | ≤ p|S| ≤ p2 (by Lemma 3.17, every vertex of S is contained in the exact shadow of at most p members of Ip,2 inducing cliques in G2 ). If no member of B2 is selected, then no exact shadow of a set of Ip,2 contains a vertex of S, and hence Z ∩ S = ∅. Note that A2 and B2 are disjoint: by (E2), every S ∈ A2 has the same exact shadow in G1 and G2, therefore the exact shadow of S ∈ A2 is disjoint from S in G2 as well. Therefore, the probability that (E4) and (E5) hold can be bounded from below by the probability of the event that every member of A2 is selected and no member of B2 is selected, which is at least 2 p 3 3) (2−p )p · (1 − 2−p )2 ≥ 2−p · e−2 2−O(p (again, we use that 1 + x ≥ exp(x/(1 + x)) for every x −1 and 1 − 2−p ≥ 1/2).

Taking into account the probability of success in both phases, we get that for each W -closest set R, the set Z satisﬁes the requirements with probability 2−O(p ).

3.6 Derandomization By running 2O(p ) times the algorithm of Lemma 3.1, we get a collection of instances such that at least one of them satisﬁes the requirements of Lemma 2.4 with arbitrary large constant probability.

To obtain a deterministic version of Lemma 2.4, we derandomize the algorithm of Theorem 3.6 using the standard technique of splitters.

Lemma 3.18.

There is an algorithm DeterministicSets(G, W, p) that, given a graph G, a set W ⊆ V (G), and an integer p, produces t = 2O(p ) log2 |V (G)| subsets Z1,..., Zt of V (G) \ W such that the following holds. For every closest set R with |N (R)| ≤ p, there is at least one 1 ≤ i ≤ t with

–  –  –

Proof. An (n, r, r2 )-splitter is a family of functions from [n] to [r2 ] such that for any subset X ⊆ [n] with |X| = r, one of the functions in the family is injective on X. Naor, Schulman, and Srinivasan [38] gave an explicit construction of an (n, r, r2 )-splitter of size O(r6 log r log n).

Observe that in the ﬁrst phase of the algorithm of Theorem 3.6, a random subset of a universe Ip,1 of size n1 = |Ip,1 | ≤ 4p · n is selected, where n = |V (G)|. There is a collection A1 ⊆ Ip,1 of a1 ≤ p2 sets and a collection B1 ⊆ Ip,1 of b1 ≤ p · 4p sets such that if every set in A1 is selected and no set in B1 is selected, then (E1–E3) hold. Instead of selecting a random subset, we try every function f in an (n1, a1 + b1, (a1 + b1 )2 )-splitter family and every subset F ⊆ [(a1 + b1 )2 ] of size a1 (there are (a1 +b1 ) = 2O(p ) ) such sets F ). For a particular choice of f and F, we select those sets a1 X ∈ Ip,1 for which f (X) ∈ F. By the deﬁnition of the splitter, there will be a function f that is injective on A1 ∪ B1, and there is a subset F such that f (X) ∈ F for every A1 and f (X) ∈ F for every B1. For such an f and F, the selection will ensure that (E1–E3) hold.

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 7 |

Similar works:

«11/4/2016 St Anton info pack ST ANTON info pack Find out everything you need to know about St Anton. Your info pack is written for you by the Crystal team in St Anton and includes: 24/7 contact details for your rep get some advice on what to do and where to ski in St Anton. What to do should you need us if you have any problems we'll get it sorted straight away so you can enjoy your holiday. The details to get you settled in, kitted out and on the slopes, including lift passes, ski hire and...»

«A PRINCESS OF MARS Edgar Rice Burroughs The preparer of this public-domain (U.S.) text is unknown. The Project Gutenberg edition (designated “pmars11”) was converted to LTEX using GutenMark software and A re-edited by Ron Burkey. Some corrections from “pmars13.txt” (credited to Andrew Sly) were also applied. Report problems to info@sandroid.org. Revision B1 differs from B in that “—-” has everywhere been replaced by “—”. Revision: B1 Date: 01/27/2008 Contents CHAPTER I. ON...»

«Reform Ideas No 2 The case for private prisons Will Tanner February 2013 Summary The Government made two major announcements on prisons at the end of 2012: the effective abolition of whole prison contracting to private companies and the decision not to introduce local pay in the prison system. Instead the Government will pursue a “new approach” limiting competition to rehabilitation and ancillary services. It will introduce an “efficiency benchmark” for public sector prisons. It will...»

«RESEARCH Pupil Grouping Strategies and Practices at Key Stage 2 and 3: Case Studies of 24 Schools in England Peter Kutnick and Steve Hodgkinson, University of Brighton Judy Sebba and Sara Humphreys, University of Sussex Maurice Galton and Susan Steward, University of Cambridge Peter Blatchford and Ed Baines, Institute of Education, University of London Research Report RR796 Research Report No 796 Pupil Grouping Strategies and Practices at Key Stage 2 and 3: Case Studies of 24 Schools in England...»

«International Mathematical Forum, Vol. 7, 2012, no. 24, 1201 1207 Strongly g*s-Continuous Maps and Perfectly g*s-Continuous Maps in Topological Spaces A. Pushpalatha Department of Mathematics, Government Arts college Udumalpet-642 126, Tirupur District Tamilnadu state, India. velu_pushpa@yahoo.co.in K. Anitha Department of Mathematics Sri Subramanya college of Engineering and Technology Palani-624 601, Dindugal District Tamilnadu state, India. jegapraba@gmail.com Abstract A. Pushpalatha and K....»

«Digraph Measures: Kelly Decompositions, Games, and Orderings Paul Hunter and Stephan Kreutzer Logic and Discrete Systems, Institute for Computer Science, Humboldt-University Berlin, {hunter, kreutzer}@informatik.hu-berlin.de Abstract. We consider various well-known, equivalent complexity measures for graphs such as elimination orderings, k-trees and cops and robber games and study their natural translations to digraphs. We show that on digraphs all these measures are also equivalent and induce...»

«Bertie County Board of Commissioners May 2, 2016 4:00pm Ronald “Ron” Wesson District 1 Stewart White District II Tammy A. Lee District III Chairman John Trent District IV Vice Chairman Ernestine (Byrd) Bazemore District V BERTIE COUNTY BOARD OF COMMISSIONERS May 2, 2016 Meeting Agenda This agenda is only a tentative schedule of matters the Commissioners may address at their meeting and all items found on it may be deleted, amended or deferred. The Commissioners may also, in their absolute...»

«1 Mathematical Modelling With Young Learners Lyn English Queensland University of Technology, Australia l.english@qut.edu.au Current research is demonstrating that young children can make significant mathematical and social gains from working authentic modelling problems. This paper argues for the implementation of mathematical modelling activities within the elementary and middle school years. The key features of these activities that make them rich learning experiences for children are...»

«MAINE WORKFORCE 2025 MAINE 2025: An exploration of the future workforce requirements for the Maine State Government By Leading Futurists LLC and Green Consulting Group March 2015 LEADING FUTURISTS LLC i March 2015 MAINE WORKFORCE 2025 LEADING FUTURISTS LLC ii March 2015 MAINE WORKFORCE 2025 Preface Maine’s Bureau of Human Resources is seeking to answer critical questions about the future of the state workforce. The Bureau engaged foresight consultancy Leading Futurists LLC, working in...»

«1 COMPUTERISATION OF PADDY PROCUREMENT AND PUBLIC DISTRIBUTION SYSTEM IN CHATTISGARH DOCUMENTATION OF BEST PRACTICE FEBRUARY 2011 Researched and Documented By: OneWorld Foundation India TABLE OF CONTENTS Executive Summary Background Addressing food security Minimum Support Price (MSP) Public Distribution System (PDS) Paddy procurement at Minimum Support Price and the Public Distribution System in Chattisgarh Need for Computerisation of Paddy Procurement and Public Distribution System in...»

«Compliance & Regulation in 2012 Evelyn Hanrahan Managing Director Financial Services Compliance & Training Ltd 1 What I will cover today. The New Central Bank of Ireland The Structure of Enforcement in 2012 The New Structure of Regulation 2012 Consumer Protection Code Fitness & Probity Standard Minimum Competency Code Financial Services Compliance & Training Ltd 2 Central Bank Core Message. ‘The establishment of a framework of assertive risk-based regulation underpinned by the credible threat...»

«Diploma in Child Protection Studies Adolescent/Sibling Incest Perpetrators Introduction Although sexual offending is typically thought of as an adult crime, early studies determined that juvenile offending is also a problem (Doshay, 1943; Groth, Hobson, Lucey, & Pierre, 1981; Shoor, Speed, & Bartlet, 1966). Recent studies also support a need to study this population. In fact, Thomas and Rogers (1983) suggested that even though evidence strongly supports the view that intrafamilial sexual abuse...»

<<  HOME   |    CONTACTS
2017 www.abstract.dislib.info - Abstracts, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.