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

<< HOME
CONTACTS

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

Method 1. Let us use the polynomial-time approximation algorithm of Gupta [27] to ﬁnd a multicut W of size at most c · OPT2, where c is a universal constant and OPT is the minimum size of a multicut.

If |W | ≥ c · p2, then we can safely answer “NO”, as there is no multicut of size at most p. Otherwise, we run the algorithm of Lemma 2.1 for this set W to obtain a solution in time O∗ (2O((p+log |W |) ) = O∗ (2O(p ) ).

Method 2. The standard technique of iterative compression [43, 28] allows us to reduce Vertex Multicut to at most |V (G)| instances of Multicut Compression with |W | = p + 1.

This technique was used for the 2-approximation of Edge Multicut in [36] and its application is analogous in our case. Let (G, T, p) be an instance of Vertex Multicut. Suppose that V (G) = {v1,..., vn }, let Gi = G[{v1,..., vi }], and let Ti be the subset of T containing the pairs with both endpoints in Gi. One by one, we consider the instances (Gi, Ti, p) in ascending order of i, and for each instance we ﬁnd a solution Si of size at most p. We start with S0 = ∅. For some i 0, we compute Si provided that Si−1 is already known. Observe that Si−1 ∪ {vi } is a multicut of size at most p + 1 for (Gi, Ti ). Thus we can use the algorithm for Multicut Compression, which either returns a multicut Si of (Gi, Ti ) having size at most p or returns “NO”. In the ﬁrst case, we can continue the iteration with i + 1. In the second case, we know that there is no multicut of size p for (G, T) (as there is no such multicut even for (Gi, Ti )), and hence we can return “NO”.

Both methods result in O∗ (2O(p ) ) time algorithms. However, we feel it important to mention both approaches, as improvements in Lemma 2.1 might have diﬀerent eﬀects on the two methods.

It will be convenient to work with a slightly modiﬁed version of the compression problem. We say that a set S ⊆ V (G) is a multiway cut of W ⊆ V (G) if every component of G \ S contains at most one vertex of W.

Multicut Compression∗ Input: A graph G, an integer p, a set T of pairs of vertices of G, and a multicut W of (G, T).

Output: A set S of size at most p such that

–  –  –

That is, Multicut Compression∗ has two additional constraints on the solution S. In Sections 4–5,

we prove that this problem is FPT:

Lemma 2.2.

Multicut Compression∗ can be solved in time O∗ (2O((p+log |W |) ) ).

–  –  –

It is not diﬃcult to reduce Multicut Compression to Multicut Compression∗ (an analogous reduction was done in [36] for the the edge case). We brieﬂy sketch such a reduction. In order to solve an instance (G, T, W, p) of Multicut Compression, we ﬁrst guess the intersection X of the multicut W given in the input and the solution S we are looking for. This guess results in at most p |W | branches; in each branch, we remove the vertices of X from G and decrease i=1 i p by |X|. Thus in the following, we can restrict our attention to solutions disjoint from W. Next, we branch on all possible partitions (W1,..., Wt ) of W, contract each Wi into a single vertex, and solve Multicut Compression∗ on the resulting instance (G, T, W, p ). One of the partitions (W1,..., Wt ) corresponds to the way the solution S partitions W into connected components, and in this case S is a multiway cut of W in G. Thus if the original Multicut Compression instance has a solution S, then it is a solution of one of the constructed Multicut Compression∗ instances.

Conversely, any solution of the constructed instances is a solution of the original instance. As the number of partitions of W can be bounded by |W |O(|W |), the running time claimed in Lemma 2.1 follows from Lemma 2.2. Thus in the rest of the paper, it is suﬃcient to prove Lemma 2.2 to obtain the main result, i.e., Theorem 1.1. Thus proving Lemma 2.2 implies the main result Theorem 1.1.

2.2 Shadows An important step in our algorithm for Multicut (and in further applications of the randomized sampling of important separators method) is to argue about solutions that are “shadowless” in the sense deﬁned below. Intuitively, we imagine the vertices in W as light sources, light spreads on the edges, and S blocks the light (see Figure 2).

Deﬁnition 2.3. Let I = (G, T, W, p) be an instance of the Multicut Compression∗ problem, and let S be a solution for I. The shadow of the set S is the set of vertices not reachable from any vertex of W in G \ S. We say that the solution S is shadowless if the shadow is empty, i.e., G \ S has exactly |W | components.

In Section 3, we present a randomized algorithm that modiﬁes the instance such that if a solution exists, then it makes the solution shadowless with positive probability. The algorithm is based on a randomized contraction of sets deﬁned by “important separators”; we review this concept in

Section 3.3. The algorithm can be derandomized to obtain the following lemma:

Given an instance I of the Multicut Compression∗ problem, we can construct in time O∗ (2O(p ) ) a set of t = 2O(p ) log n instances I1,..., It, each with the same parameter p as I, such that

1. Any solution of Ii for any 1 ≤ i ≤ t is a solution of I.

Figure 3: An instance with 7 components. The strong circles are the vertices of W, the numbers show the number of legs for each component.

2. If I has a solution, then Ii has a shadowless solution for at least one 1 ≤ i ≤ t.

Thus Lemma 2.4 allows us to reduce the Multicut Compression∗ problem into a variant where the task is to ﬁnd a shadowless solution.

2.3 Components and legs In order to ﬁnd a shadowless solution for a Multicut Compression∗ instance, the problem is further transformed in Section 4 using the concept of legs.

Deﬁnition 2.5. Given an instance (G, T, W, p) of Multicut Compression∗, we say that a component C of G \ W has -legs if C is adjacent with vertices of W (see Figure 3). We say that a Multicut Compression∗ instance is bipedal if every component of G \ W has at most two legs;

Bipedal Multicut Compression∗ is the problem restricted to such instances.

The transformation presented in Section 4 reduces Multicut Compression∗ to a bounded number of bipedal instances.

Lemma 2.6 (bipedal reduction).

Given an instance I of the Multicut Compression∗ problem with parameter p, in time O∗ (2O((p+log |W |) ) ) we can either solve this instance or construct a set of t = 2O(p+log |W |) instances I1,..., It, of Bipedal Multicut Compression∗ each with parameter at most p, such that

1. Any solution of Ii for any 1 ≤ i ≤ t is a solution of I.

2. If I has a shadowless solution, then Ii has a shadowless solution for at least one 1 ≤ i ≤ t.

Finally, in Section 5, we show how this solution can be found by a quite intuitive reduction to an FPT problem Almost 2SAT.

Lemma 2.7.

Let I = (G, T, W, p) be an instance of Bipedal Multicut Compression∗ that has a shadowless solution S of size at most p. In time O∗ (4p ), we can ﬁnd a (not necessarily shadowless) solution S.

Combining Lemmas 2.4–2.7 allows us to prove Lemma 2.2 and therefore to solve Vertex Multicut.

Proof (of Lemma 2.2). Let us apply the Algorithm of Lemma 2.4 to an instance I = (G, T, W, p) of Multicut Compression∗. This algorithm takes time O∗ (2O(p ) ) and produces t = 2O(p ) log n instances Ii of the Multicut Compression∗ problem, each with parameter at most p, so that the original instance I has a solution if and only if one of these t instances has a shadowless solution.

Moreover a (not necessarily shadowless) solution of any of these instances is also a solution of the orginal instance.

Apply to each instance Ii the algorithm of Lemma 2.6, which in time O∗ (2O((p+log |W |) ) ) either returns an answer or produces 2O((p+log |W |) ) instances Ii,j, each with parameter at most p, of the Bipedal Multicut Compression∗ problem such that Ii has a shadowless solution if and only if at least one Ii,j has a shadowless solution. Moreover a (not necessarily shadowless) solution of any new instance Ii,j is also a solution of Ii.

Combining the above two steps, we conclude that in time O∗ (2O((p+log |W |) ) ) the algorithm produces 2O((p+log |W |) ) log n instances of the Bipedal Multicut Compression∗ problem such that the original instance I has a solution if and only if at least one of the these 2O((p+log |W |) ) log n instances has a shadowless solution. Moreover a (not necessarily shadowless) solution of any instance Ii,j is also a solution of I.

Finally, we apply to each resulting instance Ii,j of the Bipedal Multicut Compression∗ problem the algorithm of Lemma 2.7. By the discussion above, if the algorithm returns a solution for at least one of the instances, then this is a solution of the original instance I. If the algorithm returns “NO” for all the instances, this means that no one of them has a shadowless solution. It follows that the original instance does not have a solution either. Taking into account that the algorithm of Lemma 2.7 takes time O∗ (4p ), processing of 2O((p+log |W |) ) log n instances takes time O∗ (2O((p+log |W |) ) ). Consequently, the instance I of the Multicut Compression∗ problem can be solved in time O∗ (2O((p+log |W |) ) ).

3 Making the solution shadowless The purpose of this section is to reduce solving Multicut Compression∗ to ﬁnding a shadowless solution. We present a randomized transformation that, given an instance having a solution, modiﬁes the instance in such a way that the new instance has a shadowless solution with probability 2−O(p ).

More precisely:

Lemma 3.1.

Given an instance I of the Multicut Compression∗ problem, we can construct in time O∗ (2O(p) ) an instance I with the same parameter p as I such that

1. Any solution of I is a solution of I.

2. If I has a solution, then I has a shadowless solution with probability 2−O(p ).

This means that if I has a solution, then by invoking Lemma 3.1 2O(p ) times, with constant probability at least one of the instances has a shadowless solution. Thus if we are able to solve the problem with the assumption that a shadowless solution exists, then this way we can get a solution for I with constant probability. The main result of this section is a derandomized version of this transformation (Lemma 2.4).

The main idea in the proof of Lemma 3.1 is to try to randomly guess a set Z whose removal does not change the instance substantially, but makes the instance shadowless. Section 3.1 introduces the torso operation, which is used to remove the set Z, and states what properties the set Z needs to satisfy. The construction of Z is based on the observation that the solution can be characterized by a “closest set” and we need to locate the boundary of such a set (Section 3.2). We develop a randomized algorithm for this purpose in Sections 3.3–3.6. The algorithm uses the notion of C

–  –  –

important separators; Section 3.3 reviews this concept and shows why it is relevant for our problem.

Sections 3.4–3.5 describe and analyze the randomized selection process. Section 3.6 shows how the random selection can be derandomized to obtain the deterministic version, Lemma 2.4.

3.1 Torsos and shadowless solutions The randomized transformation can be conveniently described using the operation of taking the torso of a graph.

Deﬁnition 3.2. Let G be a graph and C ⊆ V (G). The graph torso(G, C) has vertex set C and two vertices a, b ∈ C are adjacent if {a, b} ∈ E(G) or there is a path P in G connecting a and b whose internal vertices are not in C.

In particular, every edge of G[C] is in torso(G, C). It is easy to show that this operation

preserves separation inside C:

Proposition 3.3. Let C ⊆ V (G) be a set of vertices in G and let a, b ∈ C two vertices. A set S ⊆ C separates vertices a and b in torso(G, C) if and only if S separates these vertices in G.

Proof. Let P be a path connecting a and b in G and suppose that P is disjoint from the set S. The path P contains vertices from C and from V (G) \ C. If u, v ∈ C are two vertices such that every vertex of P between u and v is from V (G) \ C, then by deﬁnition there is an edge uv in torso(G, C).

Using these edges, we can modify P to obtain a path P that connects a and b in torso(G, C) and avoids S.

Conversely, suppose that P is a path connecting a and b in the graph torso(G, C) and it avoids S ⊆ C. If P uses an edge uv that is not present in G, then this means that there is a path connecting u and v whose internal vertices are not in C. Using these paths, we can modify P to obtain a path P that uses only the edges of G. Since S ⊆ C, the new vertices on the path are not in S, i.e., P avoids S as well.

Let I = (G, W, T, p) be an arbitrary instance of Multicut Compression∗. Given a set Z ⊆

V (G) \ W of vertices, the reduced instance I/Z = (G, W, T, p) is deﬁned the following way:

1. The graph G is torso(G, V (G) \ Z).

2. For every v ∈ V (G), let φ(v) = N (C) if v belongs to component C of G[Z], and let φ(v) = {v} if v ∈ Z. The set T is obtained by by replacing every pair (x, y) ∈ T with the set of pairs {(x, y ) | x ∈ φ(x), y ∈ φ(y)}.

The main observation is that if we perform this torso operation for a Z that is suﬃciently large to cover the shadow of a hypothetical solution S and suﬃciently small to be disjoint from S, then S becomes a shadowless solution of I/Z. Furthermore, the torso operation is “safe” in the sense that it does not make the problem easier, i.e, does not create new solutions.

Lemma 3.4.

Let I = (G, T, W, p) be an instance of Multicut Compression∗ and let Z ⊆ V (G) \ W be a set of vertices.

(1) Every solution of I/Z is a solution of I.

(2) If I has a solution S such that Z covers the shadow and Z ∩ S = ∅, then S is a shadowless solution of I/Z.

Pages:     | 1 || 3 | 4 |   ...   | 7 |

Similar works:

«Building a better future 2015 20F REPORT UNITED STATES SECURITIES AND EXCHANGE COMMISSION WASHINGTON, D.C. 20549 FORM 20-F (Mark One)  REGISTRATION STATEMENT PURSUANT TO SECTION 12(b) OR (g) OF THE SECURITIES EXCHANGE ACT OF 1934 OR  ANNUAL REPORT PURSUANT TO SECTION 13 OR 15(d) OF THE SECURITIES EXCHANGE ACT OF 1934 For the fiscal year ended December 31, 2015 OR  TRANSITION REPORT PURSUANT TO SECTION 13 OR 15(d) OF THE SECURITIES EXCHANGE ACT OF 1934 OR  SHELL COMPANY REPORT...»

«We are pleased to be able to give the following comments on the proposed simplification of Cosmetics Directive 76/768 EEC. Item 4 considered by the Commission and submitted for public consultation: Which terms would need to be included in a set of definitions in order to make the Cosmetics Directive clearer?1. Definition of fragrance-free Enhancing the transparency vis-à-vis consumers and professionals by ingredient labelling of fragrance allergens in cosmetics is an important move to increase...»

«FINANCIAL SERVICES GUIDE VERSION 6.4 – 20151109 PATRON Financial Services Pty Ltd (ABN 13 122 381 908) atf the PATRON Financial Trust (ABN 32 307 788 137) trading as PATRON Financial Advice (PATRON) Australian Financial Services Licence Number 307379...»

«The Vision “And the Lord answered me and said, Write the vision and engrave it so plainly upon tablets that everyone who passes may [be able to] read [it easily and quickly] as he hastens by. For the vision is yet for an appointed time and it hastens to the end [fulfillment]; it will not deceive or disappoint. Though it tarry, wait [earnestly] for it, because it will surely come; it will not be behindhand on its appointed day.” (Habakkuk 2:2-3 Amp.) Rod Neal Cincinnati, Ohio October, 2012...»

«Gender Dimension of Arsenicosis: A Sociological Study in Selected Villages of Nilphamari District Submitted By: Examination Roll No: 4615; Registration No: Ha-5676 Masters of Social Sciences (M.S.S) Examination-2012 Second Semester, Session: 2011-12 Department of Sociology University of Dhaka January, 2014 Gender Dimension of Arsenicosis: A Sociological Study in Selected Villages of Nilphamari District This Advanced Research Thesis Is Submitted to the Department of Sociology in Partial...»

«OASIS: Onboard Autonomous Science Investigation System for Opportunistic Rover Science Rebecca Castano* Tara Estlin Machine Learning Systems Artificial Intelligence Jet Propulsion Laboratory Jet Propulsion Laboratory 4800 Oak Grove Drive – MS 126-347 4800 Oak Grove Drive – MS 126-347 Pasadena, CA 91109 Pasadena, CA 91109 Rebecca.Castano@jpl.nasa.gov Tara.Estlin@jpl.nasa.gov Robert C. Anderson Daniel M. Gaines Geophysics and Planetary Geosciences Artificial Intelligence Jet Propulsion...»

«1 REPUBLIQUE DU BENIN ASSEMBLEE NATIONALE LOI N° 91-009 DU 04 MARS 1991 PORTANT LOI ORGANIQUE SUR LA COUR CONSTITUTIONNELLE MODIFIEE PAR LA LOI DU 31 MAI 2001.Le Haut Conseil de la République a délibéré et adopté ;L’Assemblée Nationale a délibéré et adopté en ses séances du 17 juin 1997 et 11 juillet 2000 suite aux Décisions DCC 96 – 010 des 23 et 24 janvier 1996, DCC 98-015 du 06 février 1998 et DCC 98-058 du 02 juin 1998 de la Cour Constitutionnelle pour mise en conformité...»

«The 36th Annual Conference of the German Classiﬁcation Society (GfKl) on Data Analysis, Machine Learning and Knowledge Discovery University of Hildesheim, Germany August 1-3, 2012 Program & Abstracts Photo title page: Market place of Hildesheim ( c Hildesheim Marketing, Photographer: Obornik) The 36th Annual Conference of the German Classiﬁcation Society (GfKl) v The 36th Annual Conference of the German Classiﬁcation Society (GfKl) on Data Analysis, Machine Learning and Applications...»

«Communication Skills Prof. T. Ravichandran Department of Humanities and Social Sciences Indian Institute of Technology, Kanpur Module #12 Lecture 3 Common Errors (Refer Slide Time: 00:19) Hello, welcome to NPTEL’s course on Communication Skills. We are on the final module, this is module number 12 and again on the final lecture, this is lecture number 3 on Common Errors. I have been giving two lectures already and this is the third lecture on common errors. And in the past two lectures, we...»

«Parliamentary Affairs Advance Access published May 23, 2012 Parliamentary Affairs (2012) 1–11 doi:10.1093/pa/gss024 Strengthening Women’s Roles in Parliaments Susan Markham* National Democratic Institute for International Affairs (NDI), Washington, DC, USA Downloaded from http://pa.oxfordjournals.org/ at National Democratic Institute on June 18, 2012 * Correspondence: smarkham@ndi.org The National Democratic Institute for International Affairs (NDI) has supported democratic institutions and...»

«2012-2013 Youth Concerts Hold the Cannons Oct. 22, 2012 Tchaikovsky and the 1812 Overture Meet the Orchestra April 29, 2013 Additional support for Education Programs provided by: Sponsored by: Table of Contents Welcome 1 Fall Concert Program 2 Notes on the Fall Program 3 Fall Concert Meet the Artists 9 Spring Concert Program 10 Notes on the Spring Program 11 Spring Concert Meet the Artists 15 Spring Concert Meet the Artist Q&A 16 Learning Activities Orchestra Worksheet 17 Learning Activities...»

«Bio-based polymers Irina Voevodina, Andrej Kržan Recently great attention is given to the concept of sustainable development. The most widely accepted definition of sustainable development is “development that meets the needs of the present without compromising the ability of future generations to meet their own needs” (World Commission on Environment and Development’s report “Our Common Future”, 1987). For a transition to a higher level of sustainability development it is necessary...»

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