FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 | 2 || 4 | 5 |   ...   | 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 3 ] --

Proof. Let G and G = torso(G, V (G) \ Z) be the graphs in instances I and I/Z, respectively. To prove the first statement, we show that if S ⊆ V (G ) is a solution of I/Z, then S is a solution of I as well. Suppose that some pair (x, y) of I is not separated by S. Let P be a path in G \ S going from x to y. Let x and y be the first and last vertex of P not in Z, respectively, and let P be the subpath of P from x to y. (Note that P cannot be fully contained in Z, as it contains at least one vertex of the multicut W.) By the way I/Z is defined, (x, y ) is a pair in I/Z, hence S separates x and y in G = torso(G, C). Using Prop. 3.3 with C = V (G) \ Z, we get that S separates x and y in G, which is in contradiction with the existence of the path P. A similar argument shows that there is no path in G \ S that connects two vertices of W.

For the second statement, suppose that S is a solution of I with S ∩ Z = ∅. Let us show that S is a solution of I/Z as well. Suppose that S does not separate x and y in G for some pair (x, y ) of I/Z. Using Prop. 3.3 with C = V (G) \ Z, we get that S does not separate x and y in G, i.e., there is an x − y path P in G \ S. By the way the pairs in I/Z were defined, there is a pair (x, y) of I and there is an x − x path P1 such that x is the only vertex of P1 not in Z, and there is a y − y path P2 such that y is the only vertex of P2 not in Z. Clearly, these paths are disjoint form S. Therefore, the concatenation of P1, P, P2 is an x − y path in G \ S, contradicting that S is a solution of I.

To see that S is shadowless in G, consider a vertex v of G \ S. As v ∈ Z is not in the shadow of the solution S of I, there is a path P in G \ S going from v to a vertex w ∈ W. Again by Prop. 3.3, this means that there is a v − w path in G \ S as well, which means that v is not in the shadow of the solution S of I.

3.2 Closest sets Lemma 3.4 shows that in order to reduce the Multicut Compression∗ problem to finding a shadowless solution, all we need is a set Z that covers the shadow of a hypothetical solution S, but disjoint from S itself. It is not obvious how this observation is of any help: it seems that there is no way of constructing such a set without actually knowing a solution S. Nevertheless, we present a randomized procedure that constructs such a set with non-negligible probability.

The main idea of the randomized procedure is that a solution of a Multicut Compression∗ instance can be characterized by the set of vertices reachable from W, and we can assume that this set has the property that it cannot be made smaller without increasing the size of the boundary.

The following definition formalizes this property:

Definition 3.5. Let G be an undirected graph and let W ⊆ V (G) be a subset of vertices. We say that a set R ⊇ W is a W -closest set if there is no R ⊂ R with R ⊇ W and |N (R )| ≤ |N (R)|.

The main technical idea of the paper is the following randomized procedure, which, in some sense, finds the boundary of a closest set. Note that this statement could be of independent interest, as it is about closest sets in general and contains nothing specific to multicut problems.

Theorem 3.6 (random sampling).

There is a randomized algorithm RandomSet(G, W, p) that, given a graph G, a set W ⊆ V (G), and an integer p, produces a set Z ⊆ V (G) \ W such that the following holds. For every W -closest set R with |N (R)| ≤ p, the probability that the following two events both

occur is at least 2−O(p ) :

1. N (R) ∩ Z = ∅, and

2. V (G) \ (R ∪ N (R)) ⊆ Z.

That is, the two events say that Z covers every vertex outside R ∪ N (R) and may cover some vertices inside R, but disjoint from N (R). To prove Theorem 3.6, we introduce the main new technique of the paper: random sampling of important separators. In Section 3.3, we review the notion of important separators. Section 3.4 contains a simplified proof of Theorem 3.6 (with probability O(p) 3 bound 2−2 instead of 2−O(p ) ). The full proof appears in Section 3.5. We show below that Theorem 3.6 can be used to prove Lemma 3.1. Section 3.6 shows how to derandomize Theorem 3.6, which immediately proves Lemma 2.4.

Proof (of Lemma 3.1). Let I = (G, W, T, p) be an instance of Multicut Compression∗. Let us use the algorithm RandomSet(G, W, p) of Theorem 3.6 to obtain a set Z and let I = I/Z. By Lemma 3.4, every solution of I is a solution of I as well.

Assume now that I has a solution S; let S be a solution such that |S| is minimum possible, and among such solutions the set R of vertices reachable from W in G \ S is as small as possible. Clearly, N (R) ⊆ S. We claim that R is a W -closest set. Suppose that there is a set R ⊂ R containing W such that |N (R )| ≤ |N (R)|. Let S = N (R ), we have that |S | ≤ |S|. We claim that S is a solution, contradicting the minimality of S. Suppose that there is a path P in G \ S connecting the two terminals in a pair (x, y) ∈ T or two vertices of W. In both cases, P has to go through a vertex of W (here we use that the definition of Multicut Compression∗ requires that W is a multicut).

Therefore, P is fully contained in R ⊂ R, which implies that it is disjoint from N (R) ⊆ S, i.e., S is not a solution. Thus S is indeed a solution with |S | ≤ |S| and |R | |R|, contradicting the choice of the solution S. This contradiction proves our claim that R is a W -closest set. The same argument shows that N (R) is a solution, hence S = N (R) has to hold.

As R is a W -closest set, the probability that both S ∩ Z = ∅ and V (G) \ (R ∪ S) ⊆ Z hold is −O(p3 ). The later inclusion is equivalent to saying that the shadow of the solution S is contained in Z. Therefore, by Lemma 3.4, set S is a shadowless solution of instance I.

–  –  –

Figure 5: Set S1 is the unique minimum X − Y separator and therefore it is an important X − Y separator. Set S2 is not an important X − Y separator, as |S2 | = |S3 | and a superset of vertices is reachable from X in G\S3 compared to G\S2. Sets S3 and S4 are both important X −Y separators.

Definition 3.8. Let X, Y ⊂ V (G) be disjoint sets of vertices, S ⊆ V (G) be an X − Y separator, and let K be the union of every component of G \ S intersecting X. We say that S is an important X − Y separator if it is inclusionwise minimal and there is no X − Y separator S with |S | ≤ |S| such that K ⊃ K, where K is the union of every component of G \ S intersecting X.

See Figure 5 for illustration. Note that the order of X and Y matters: an important X − Y separator is not necessarily an important Y − X separator. It is easy to see that if S is an important X − Y separator, then S = N (R) for some set R with X ⊂ R and (R ∪ N (R)) ∩ Y = ∅: we can define R to be the set of vertices reachable from X in G \ S. Observe that if R is defined this way, then every component of G[R] contains at least one vertex of X. In particular, if X contains only a single vertex, then we can assume that G[R] is connected.

A bound on the number of important separators was given in [35] (although the notation there is slightly different). A better bound is implicit in [8]. For the convenience of the reader, we give a self-contained proof of the following fact in the appendix.

Lemma 3.9.

Let X, Y ⊆ V (G) be disjoint sets of vertices in a graph G. For every p ≥ 0, there are at most 4p important X − Y separators of size at most p. Furthermore, we can enumerate all these separators in time 4p · p · (|E(G)| + |V (G)|).

Note that one can give an exponential lower bound on the number of important separators as a function of p and in fact the bound 4p in Lemma 3.9 is asymptotically tight up to factors polynomial in p.

The following lemma connects closest sets and important separators by showing that the boundary of a closest set is formed by important separators. Intuitively, every vertex v outside the closest set R “sees” a part of the boundary N (R) that is an important v − W separator: otherwise, we could “push” this part of the boundary away from v and towards W, contradicting the assumption that R is a closest set.

Lemma 3.10 (pushing).

Let G be an undirected graph, W a set of vertices, and R a W -closest set.

For every vertex v ∈ R ∪ N (R), there is an important v − W separator Sv ⊆ N (R).

Proof. Let v be an arbitrary vertex of G not in R ∪ N (R) and let K be the component of G \ N (R) containing v. As v ∈ R ∪ N (R) and W ⊆ R, we have that K is disjoint from W. We show that K R

–  –  –

Figure 6: Proof of Lemma 3.10. Note that, in general, K can intersect other components of G \ (R ∪ N (R)).

N (K) is an important v − W separator. First, we observe that N (K) is a minimal v − W separator:

we have N (K) ⊆ N (R), thus every vertex of N (K) is adjacent to both K and R. Thus, if N (K) is not an important v − W separator, then there is a K ⊃ K such that K ∪ N (K ) is disjoint from W and |N (K )| ≤ |N (K)|. We may assume that G[K ] is connected. Let R := R \ (K ∪ N (K )). Now N (R ) ⊆ (N (R) \ N (K)) ∪ N (K ): it is clear that every neighbor of R is in N (R) ∪ N (K ) (as it cannot be in K ) and every vertex of N (K) \ N (K ) is fully contained in K. Thus |N (R )| ≤ |N (R)| follows from |N (K )| ≤ |N (K)|. Furthermore, the connectivity of G[K ] and K ⊂ K implies that K contains a vertex of N (K) ⊆ N (R) and therefore K ∪ N (K ) contains a vertex of R. This means that R is a proper subset of R with |N (R )| ≤ |N (R)|, contradicting the assumption that R is a W -closest set.

3.4 Random sampling of important separators—simplified proof In this section, we present a simpler version of the proof of Theorem 3.6, where the probability of success is double exponentially small in p. This simpler proof highlights the main idea of the randomized reduction. The full proof, which improves the probability to 2−O(p ) with additional ideas, appears in Section 3.5.

By Lemma 3.9 we can enumerate every separator of size at most p that is an important v − W separator for some v.

Definition 3.11. The set Ip contains a set S ⊆ V (G) \ W if S is an important v − W separator of size at most p for some vertex v ∈ V (G) \ (W ∪ S).

By Lemma 3.9, the size of Ip is at most 4p · |V (G)| and we can construct Ip in time O∗ (4p ).

Recall that the shadow of a set S is the set of vertices not reachable from W in G \ S. By Lemma 3.10, every vertex of the shadow of N (R) is covered by the shadow of a member of Ip that is a subset of N (R). This means that the shadow of 2p members of Ip fully cover the shadow of N (R).

This suggests that we may construct a set Z satisfying the conditions of Theorem 3.6 by guessing these members of Ip and obtaining Z as the union of the shadows of the selected sets. However, in general the size of Ip cannot be bounded as a function of p only. Thus complete enumeration of all possible ways of selecting 2p members of Ip is not feasible. Instead, we randomly select a subset of Ip and hope that it contains these at most 2p members and it does not contain any member of Ip whose shadow intersects N (R).

The probability of randomly selecting a member of Ip should not be too high, because we want to avoid selecting any member whose shadow contains a vertex of N (R). We need a bound on the number such members of Ip. Intuitively, the bound of Lemma 3.9 on the number of important separators should imply that each vertex of N (R) is contained in the shadow of a bounded number of members of Ip, but in order to make this claim precise, we need to consider a slightly different

notion of a shadow:

Definition 3.12. The exact shadow of a set S ⊆ V (G)\W contains those vertices v ∈ V (G)\(W ∪S) for which S is a minimal v − W separator.

For example, in Figure 2, set C2 is in the exact shadow of S, but C1 is not, as a 2-vertex subset of S separates every vertex of C1 from W.

The following lemma is true only for exact shadows: the bound in (2) is not true with the original definition of shadow.

Lemma 3.13.

(1) For every S ∈ Ip, we have that v ∈ V (G) \ (W ∪ S) is in the exact shadow of S if and only if S is an important v − W separator.

(2) Each vertex v ∈ V (G) \ W is contained in the exact shadow of at most 4p members of Ip.

Proof. (1) By definition, if S is an important v − W separator, then S is a minimal v − W separator, hence v is in the exact shadow of S. For the other direction, suppose that v is in the exact shadow of some S ∈ Ip. By definition of Ip, there is a vertex u ∈ V (G) \ (W ∪ S) such that S is an important u − W separator. If S is not an important v − W separator, then (as the definition of exact shadow implies that S is a minimal v − W separator) there is a v − W separator S with |S | ≤ |S| and such that a superset of vertices is reachable from v in G \ S compared to G \ S.

We claim that S is a u − W separator as well. Suppose that there is a u − W path P in G \ S.

This path has to go through S \ S ; let s be the first vertex of S \ S on P when going from u to W. Since S is a minimal v − W separator, s has a neighbor reachable from v in G \ S and hence in G \ S. Therefore, s ∈ S is also reachable from v in G \ S. It follows that s is reachable from both u and v in G \ S, i.e., u and v are in the same component of G \ S, contradicting the assumption that S is a v − W separator.

Pages:     | 1 | 2 || 4 | 5 |   ...   | 7 |

Similar works:

«Fiber Optics for Remote Delivery of High Power Pulsed Laser Beams Jason M. Kriesel1 and Nahum Gat2 Opto-Knowledge Systems, Inc. (OKSI), Torrance, CA, 90502 and David Plemmons3 Aerospace Testing Alliance (ATA), Arnold AFB, TN, 37389 The work described here is focused on the technology to enable remote fiber optic delivery of high-power, pulsed laser beams for diagnostics used in combustion and flow-field characterization. Fiber delivery is desirable since it is not always practical to locate...»

«I Who Cares about the Evolution of Stories? Author(s): Paul Bloom Reviewed work(s): Source: Critical Inquiry, Vol. 38, No. 2 (Winter 2012), pp. 388-393 Published by: The University of Chicago Press Stable URL: http://www.jstor.org/stable/10.1086/662749. Accessed: 16/02/2012 22:18 Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at. http://www.jstor.org/page/info/about/policies/terms.jsp JSTOR is a not-for-profit service that helps scholars,...»

«MILID Yearbook 2013 A Collaboration between UNITWIN Cooperation Programme on Media and Information Literacy and Intercultural Dialogue and NORDICOM Media and Information Literacy and Intercultural Dialogue Edited by Ulla Carlsson & Sherri Hope Culver Autonomous University of Barcelona, University of São Paulo, Tsinghua University, Cairo University, Temple University, University of the West Indies, Queensland University of Technology, Sidi Mohamed Ben Abdellah University The International...»

«OFFICE OF LICENSING & GUIDANCE INSPECTOR’S REPORT ON AN IPPC LICENCE REVIEW Directors To: Emer Cooney From: LICENSING UNIT 17 APRIL 2007 Date: Application for review of an IPPC Licence from Microprint, Licence Reg. No. P0659-02.RE: Application Details Class of activity: 12.2.2 The use of coating materials with a capacity to use at least 10 tonnes per year of organic solvents, not included in paragraph 12.2.1. Section 90(1)(b) notice sent: 14 December 2006 Licence application received: 23...»

«Diplomatic, Consular & Other Representatives in Canada March 2010 Inside A Word From the Publishing Team p. 2 Office of Protocol Senior Level Staff p. 3 Order of Precedence p. 4 Diplomatic Corps & Consular Representatives p. 7 International Organizations and Other Offices p. 141 National Days p. 155 Canadian National Holidays p. 159 Provincial Protocol Offices p. 160 A word from the publishing team Each The public’s continued feedback is highly month, an estimated 200 foreign representatives...»


«Julio 2011 MIGRACIONES Y SAGUA LA GRANDE Yoel Rivero Marín yoel@emaildiario.zzn.com Para citar este artículo puede utilizar el siguiente formato: Rivero Marín, Y.: Migraciones y Sagua La Grande, en Contribuciones a las Ciencias Sociales, julio 2011. www.eumed.net/rev/cccss/13/ Las migraciones o desplazamientos de la población constituyen uno de los procesos sociales donde tienen lugar la reunión de un gran número de aspectos, ya que prácticamente están relacionadas directas o...»

«The initial growth of complex oxides: Study and Manipulation Guus Rijnders Contents 1 Introduction 9 References chapter 1 12 2. Experimental 13 2.1 Introduction 13 2.2 Pulsed laser deposition 14 2.2.1 Basic principles 14 2.2.2 PLD set-up 16 2.2.3 Experimental conditions 17 2.3 High-pressure reflection high-energy electron diffraction (RHEED) 18 2.3.1 Geometry and basic principles of RHEED 18 2.3.2 Utility of RHEED: surface properties 22 2.3.3 Utility of RHEED: monitoring thin film growth 26...»

«Knowl Inf Syst (2013) 36:789–826 DOI 10.1007/s10115-012-0563-0 REGULAR PAPER Using Case-Based Reasoning and Principled Negotiation to provide decision support for dispute resolution Davide Carneiro · Paulo Novais · Francisco Andrade · John Zeleznikow · José Neves Received: 24 August 2010 / Revised: 7 July 2011 / Accepted: 4 August 2012 / Published online: 18 October 2012 © Springer-Verlag London 2012 Abstract The growing use of Information Technology in the commercial arena leads to an...»

«Navigating Hierarchically Clustered Networks through Fisheye and Full-Zoom Methods DOUG SCHAFFER The University of Calgary ZHENGPING ZUO Simon Fraser University SAUL GREENBERG The University of Calgary LYN BARTRAM and JOHN DILL Simon Fraser University SHELLI DUBS Alberta Research Council and MARK ROSEMAN The University of Calgary Many information structures are represented as two-dimensional networks (connected graphs) of links and nodes. Because these networks tend to be large and quite...»

«Federal Maritime Commission Initial Draft Strategic Plan Fiscal Years 2014-2018 July 29, 2013 Table of Contents Overview...3 Summary of Strategic Goals, Objectives, and Performance Measures.6 FMC Strategic Plan Fiscal Years 2014-2018..8 Strategic Goal 1: Maintain an efficient and competitive international ocean transportation system..8 Objective 1: Enhance efficiency in the trades through the use of asset sharing authority under the Shipping Act of 1984...8 Strategic Goal 2: Protect the...»

«New York State Board of Elections Page 1 of 16 Board of Commissioners Meeting 2014-09-26 Jim Walsh: Good morning. My name is Jim Walsh; I will be directing our meeting this afternoon. I would like my fellow Commissioners to introduce themselves. Pardon me? Douglas Kellner: I’m Doug Kellner Andrew Spano: Andy Spano Gregory Peterson: Greg Peterson Jim Walsh: Around the table, we’ll wait for the other two to get back to introduce themselves but in the meantime. John Conklin: John Conklin Risa...»

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