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

<< HOME
CONTACTS

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

In the second phase, we select a random subset of universe Ip,2 of size n2 ≤ pn, and there is a collection A2 ⊆ Ip,2 of size a2 ≤ 2p and a collection B2 ⊆ Ip,2 of size b2 ≤ p2 such that if every set in A2 is selected and no set in B2 is selected, then (E4) and (E5) hold. As in the ﬁrst phase, we can replace this random choice by enumerating the functions of an (n2, a2 + b2, (a2 + b2 )2 )-splitter and every subset F ⊆ [(a2 + b2 )2 ] of size b2 (there are (a2 +b2 ) = 2O(p ) such sets F ). This time, we b2 select a set X ∈ Ip,2 if f (X) is not in F and it is clear that there is an f and F for which (E4) and (E5) hold.

Let us bound the number of branches of the algorithm. In both phases, the size of the splitter family is 2O(p) · log n and the there are 2O(p ) possible F. (Note that the splitter family can be constructed in time polynomial in the size of the family.) Thus the algorithm produces 2O(p ) · log2 n sets.

4 Reduction to the bipedal case Let (G, T, W, p) be an instance of the Multicut Compression∗ problem. Let us call a component of G \ W having at least two legs a non-trivial component of G w.r.t. W (when the context is clear, we will just refer to a non-trivial component). As the solution of Multicut Compression∗ has to be a set S that is disjoint from W and a multiway cut of W, the number of non-trivial components is a lower bound on the size of the solution.

We present an algorithm that either solves the given instance of the Multicut Compression∗ problem or produces a set of instances of the Bipedal Multicut Compression∗ problem whose number is bounded by a function of p and such that if the considered instance of the Multicut Compression∗ problem has a shadowless solution then one of the output instances of the Bipedal Multicut Compression∗ problem has a solution. In addition, any (not necessarily shadowless) solution of any of these output instances is a solution of the input instance of the Multicut Compression∗ problem. The key ingredient of this algorithm is a procedure that, given an instance of the Multicut Compression∗ problem where at least one component has more than 2 legs, reduces this instance to a set of instances whose number is bounded by a function of p and such that in each instance either the parameter is decreased or the number of non-trivial components is increased.

The main idea for the branching is the following. Let B be a set of vertices in G \ W and let S be a hypothetical shadowless solution for Multicut Compression∗. We try to guess what happens to each vertex of B in the solution S. It is possible that a vertex v ∈ B is in S; in this case, we delete v from the instance and reduce the parameter. Otherwise, as the solution is shadowless, v has to be in the same component as precisely one w ∈ W (since S is a multiway cut of W ). In this case, identifying v and w does not change the solution.

The following lemma formalizes these observations. Given a set B of vertices in G \ W and a function f : B → W, we denote by Gf the graph obtained by replacing each set {w} ∪ f −1 (w) with a single vertex (with removal of loops and multiple occurrences of edges). To simplify the presentation, we will assume that this new vertex is also named w. We denote by Tf the set of terminal pairs where each vertex v ∈ B is replaced by f (v), and we denote by T \ v the set where every pair involving the vertex v is removed.

Lemma 4.1.

Let K be a non-trivial component of G \ W with set of legs W and let B ⊆ K. If (G, T, W, p) has a shadowless solution, then one of the following statements is true.

• There is a v ∈ B such that the instance (G \ v, T \ v, W, p − 1) has a shadowless solution.

• There is a function f : B → W such that instance (Gf, Tf, W, p) has a shadowless solution.

Moreover, if any of the above instances has a solution, then (G, T, W, p) has a solution as well.

Proof. Assume that (G, T, W, p) has a shadowless solution S. Then it either intersects or does not intersect with B. In the former case, we can specify a v ∈ S ∩ B such that S \ {v} is a shadowless solution of (G \ v, T \ v, W, p − 1). In the latter case, we can assign each v ∈ B precisely one vertex f (v) of W such that vertex v belongs to the same component of G \ S as f (v). It is not hard to see that S is a shadowless solution of (Gf, Tf, W, p).

For the second statement, we observe that the existence of a solution for any of the above instances implies the existence of a solution for (G, T, W, p). This is certainly true in the ﬁrst case, where we delete a vertex and decrease the parameter by 1. In the second case, the statement follows from the fact that replacing G with Gf by identifying vertices cannot make the problem any easier.

Lemma 4.1 determines a set of recursive calls to be applied in order to ﬁnd a solution for the given instance (G, T, W, p) of the Multicut Compression∗ problem, if a shadowless solution is guaranteed to exist.

It is clear that in each step, the number of directions we branch into is bounded by a function of p, |B|, and |W | (observe that the number of functions f : B → W can be bounded by |W ||B| ≤ |W ||B| ). However, in order to ensure that the size of the search tree is bounded, we need to ensure that the height of the search tree is bounded as well. This is obvious for the ﬁrst type of branches, as p decreases. The following property ensures that in every branch of the second type, either the number of nontrivial components increases or we get an instance that trivially has no solution.

Deﬁnition 4.2. Let K be a non-trivial component and let W ⊆ W be its set of legs. Let B be a subset of K. We say that B is a shattering set if for any function f : B → W one of the following statements is true regarding the instance (Gf, Tf, W, p) of the Multicut Compression∗.

• There is a w ∈ W such that there is no w −(W \{w}) separator of size at most p in Gf [K ∪ W ].

• The number of non-trivial components of Gf \ W is greater than the number of non-trivial components of G \ W.

Note that the ﬁrst possibility includes the case when Gf [W ] is not an independent set (recall that an X −Y separator is disjoint from X ∪Y by deﬁnition). In Section 4.1, we present a polynomial-time algorithm for ﬁnding a shattering set.

Lemma 4.3.

Given an instance (G, T, W, p) of the Multicut Compression∗ problem and a component K of G \ W with more than two legs, we can ﬁnd a shattering set B ⊆ K of size at most 3p in polynomial time.

With Lemma 4.3 in mind, we are ready to prove Lemma 2.6, the main statement of this section.

Proof (of Lemma 2.6). The desired algorithm looks as follows. If the given instance (G, T, W, p) of Multicut Compression∗ satisﬁes one of the following cases, then we can determine the answer

without any further branching:

• All the terminal pairs of T are separated: solve the multiway cut problem (G, W, p).

• The parameter is zero while there are unseparated terminals: this is a “NO” instance.

• There is a w ∈ W such that there is no w − (W \ {w}) separator of size at most p in G: this is a “NO” instance. The situation where W is not an independent set is a special subcase of this case.

• The number of non-trivial components is greater than p: this is a “NO” instance since each non-trivial component contributes at least one vertex to any solution.

• Every component has at most two legs: this is an instance of Bipedal Multicut Compression∗ problem and hence it is returned as the output.

Otherwise, we choose a component K of G \ W having more than two legs, and use Lemma 4.3 to compute a shattering subset B of K of size at most 3p. We apply recursively the branches speciﬁed in the statement of Lemma 4.1. If the “YES” answer is obtained on at least one of these branches, then we return “YES”. If all the branches return “NO”, we return “NO”. According to Lemma 4.1, the resulting answer is correct. Furthermore, assume that no one of branches produces a “YES” or “NO” answer. Then, according to Lemma 4.1, if the parent instance has a shadowless solution, then the instance on one of the branches has a shadowless solution. It is also not hard to notice that any solution for a branch instance can be easily transformed into a solution of the parent instance. Applying this argument inductively, we conclude that the same relationship exists between the original instance (G, T, W, p) and the Bipedal Multicut Compression∗ problem instances at the leaves of the recursion tree.

To bound the number of leaves of the recursion tree, let us deﬁne κ to be the number of nontrivial components. Observe that removing a vertex of V (G) \ W from G can decrease the number of nontrivial components only by at most one. Thus inspection of Lemma 4.1 shows that the measure 2p − κ strictly decreases in each branch. This means that the height of the search tree is at most 2p. The number of branches in each step can be bounded by 3p + |W |3p. Thus the number of leaves of the recursion tree can be generously bounded by 2O((p+log |W |). Taking into account that the runtime per node of the recursion tree is polynomial, it follows that the runtime of this algorithm is O∗ (2O((p+log |W |) ) ).

4.1 Finding a shattering set We try to ﬁnd a shattering set by selecting a set that separates one leg from all the other. If it is not a shattering set, then we can characterize quite well how it can look like, and where should we continue our search for a shattering set. Let us start with two simple lemmas.

Lemma 4.4.

Let K be a non-trivial component with a set W of at least 3 legs. If G[M1 ] and G[M2 ] are both connected for two disjoint sets M1, M2 ⊆ K, then at most one of M1 and M2 can be a multiway cut of (G[K ∪ W ], W ).

Proof. Assume the opposite. Since no two vertices of W belong to the same component of G[K ∪ W ] \ M1 and |W | ≥ 3, we can specify two vertices w and w of W whose respective components C and C in G[K ∪ W ] \ M1 are disjoint from the connected set M2. As G[K] is connected, there is a w − w path in G[K ∪ W ] that ﬁrst uses vertices from C, then vertices from (the connected set) M1, then vertices from C. This path is disjoint from M2, contradicting the assumption that M2 is a multiway cut.

Lemma 4.5.

Let K be a non-trivial component with a set W of at least 3 legs. Let B ⊆ K be a non-shattering set. Then there is exactly one connected component of G[K \ B] that is a multiway cut of (G[K ∪ W ], W ).

Proof. Let f : B → W be the mapping witnessing that B is not a shattering set. Let K ⊆ K \ B be the unique non-trivial component of Gf \ W that is a subset of K (witnessing B being a nonshattering set). As every neighbor of K is in B ∪ W, it is easy to see that K is a component of G[K \ B] as well. Furthermore, we claim that K is a multiway cut of (G[K ∪ W ], W ). Otherwise, a path between vertices of W in G[K ∪ W ] \ K would correspond to a walk of Gf between the same vertices which belong to a non-trivial component that is a subset of K but diﬀerent from K, in contradiction to the deﬁnition of f. Finally, Lemma 4.4 implies that K is the unique connected component of G[K \ B] being a multiway cut of G[K ∪ W ].

Let K be a non-trivial component with a set of legs W. Let M ⊆ K be a multiway cut of (G[K ∪ W ], W ). We call N (M ) (i.e., the open neighborhood of M ) the boundary of M (which possibly includes vertices of W ). For each w ∈ W, the image I(w) of w is the set of vertices of N (M ) reachable from w in G[K ∪ W ] \ M (the image may include vertex w itself, but it cannot include any other member of W ), see Figure 7. Note that I(w) is nonempty for any w ∈ W : consider the ﬁrst vertex of N (M ) on a path from w to some other leg in W. Furthermore, as M is a multiway cut, the sets I(w ) and I(w ) are disjoint for w = w : otherwise, there would be a w − w path disjoint from M. For X ⊆ W, we let I(X) = w∈X I(w). Let us select a distinguished leg w∗ ∈ W.

We say that M is good if all of the following conditions are true.

–  –  –

Our goal is to obtain a shattering set from the boundary of a good multiway cut. The following lemma gives a polynomial-time algorithm that either produces a shattering set, or ﬁnds a smaller good multiway cut. Interestingly, the algorithm does not check that the returned set B is a shattering using Deﬁnition 4.2 directly: this would require trying every function f : B → W. Instead, the way the set B is produced guarantees that B is indeed a shattering set.

–  –  –

Figure 7: M is a multiway cut of the 4 legs {1, 2, 3, 4}. The dark region represents the boundary of M. Observe that I({1, 2, 3, 4}) is a proper subset of the boundary: vertices of the boundary that are adjacent only to C and C are not in I(w) for any w ∈ {1, 2, 3, 4}.

Lemma 4.6.

Let K be a non-trivial component with a set W of at least 3 legs and a distinguished leg w∗. Let M be a good multiway cut of (G[K ∪ W ], W ). Then there is a polynomial-time algorithm that either returns a shattering set of size at most 3p or a good multiway cut M ⊂ M.

Proof. The desired algorithm ﬁrst computes a smallest I(w∗ )−I(W \{w∗ }) separator S of G[N (M )∪ M ] (recall that the images are nonempty). Observe that S is an inclusionwise minimal w∗ − W \{w∗ }

separator in G[K ∪ W ] (and hence nonempty). We consider three cases:

1. If |S| p, then the algorithm returns B := N (M ) \ W reporting it as a shattering set.

2. If |S| ≤ p and there is a unique connected component M of G[K \ (N (M ) ∪ S)] that is a multiway cut of (G[K ∪ W ], W ), then the algorithm returns M reporting it as a good multiway cut.

3. If |S| ≤ p and there is no such unique M, then the algorithm returns B := (N (M ) ∪ S) \ W reporting it as a shattering set.

This algorithm clearly takes polynomial time. The remaining proof establishes correctness of the algorithm in each of these three cases.

Case 1. The deﬁnition of good multiway cut implies that that B := N (M ) \ W has size at most 2p.

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

Similar works:

«Form ADV Part 2A: Firm Disclosure Brochure Amendment – December 7, 2016 O’Brien Wealth Partners LLC Jill A. Fopiano, CEO, CIO 177 Huntington Ave., Suite 2010 Boston, MA 02115 (617) 547-6717 Fax: (617) 547-9516 www.obrienwp.com Summary of Material Changes This amendment of Form ADV Part 2A: Firm Disclosure Brochure for O’Brien Wealth Partners LLC contains the following material changes since our last update on October 3, 2016. Jill A. Fopiano has assumed the role of CEO and Chief...»

«eBay eCommerce Platform A case study in Scalability by Mohammad Usman Ahmed mohammad.ahmed@mail.mcgill.ca Table of Contents: 1. The Application and its overall architecture 2. Component Model and its interactions 3. Technological aspects of the eBay Architecture 4. Strengths and relative weaknesses of the Architecture 5. Component Model and variations 6. Key Quality Attributes favoured by the eBay Architecture 7. Evolution of the Application and its Architecture 8. Conclusion The Application...»

«i CONFIRMED FUTURE TITLES! IN THE PIPELINE. YOUR BOOK HERE? AVAILABLE NOW! i (follow us @ twi er.com/hiivebooks) hiive The ZX Spectrum Book 1982 to 199X Recollections of the ZX Spectrum ● For many, the Sinclair ZX Spectrum was the first glimpse of the exciting “.for former ‘Spec-Chums’, this unique tribute to the world of possibilities opened up by affordable colour clash of yore will prove hard to resist.” home computing. EDGE Magazine ● Kick-starting the “.We’re looking...»

«A Trait Approach to Measuring Materialism: Structure and Scale Properties Martin Grimmer, Dallas Hanson, University of Tasmania Abstract Materialism is a topic of intense scholarly and popular attention, yet the measurement of materialism continues to be problematic. The present study evaluated Belk’s (1984) measure of materialism which assesses three materialistic personality traits: possessiveness, nongenerosity and envy. An adapted version of Belk’s measure was administered to 274...»

«Population Dynamics: Analysis, Modelling, Forecast 2(4): 154–181 Larch bud moth dynamics: can we explain periodicity of population fluctuations by the time lag dependence in birth rate? D.L. Sadykova1, L.V. Nedorezov2 University of St. Andrews, UK e-mail dinasadykova@gmail.com University of Nova Gorica, Slovenia e-mail l.v.nedorezov@gmail.com Abstract Current publication is devoted to traditional and non-traditional approaches to statistical analysis of well-known time series on the dynamics...»

«SECURITIES AND EXCHANGE BOARD OF INDIA ORDER UNDER SECTION 11(4), 11B OF SEBI ACT, 1992 READ WITH REGULATION 11 OF SEBI (PROHIBITION OF FRAUDULENT AND UNFAIR TRADE PRACTICES RELATING TO SECURITIES MARKET) REGULATIONS, 2003 AGAINST KETAN V. PAREKH, KARTIK K. PAREKH, CLASSIC CREDIT LTD, PANTHER FINCAP & MANAGEMENT SERVICES LTD, LUMINANT INVESTMENT LTD, SAIMANGAL INVESTRADE LTD, CHITRAKUT COMPUTERS PRIVATE LTD, CLASSIC INFIN LTD AND PANTHER INVESTRADE LTD 1.0 Significant price rise and volumes...»

«CNA Activities Related to Resolutions Proposed by Members and Agreed to by CNA Board of Directors in 2012 Resolutions are a method of providing advice to CNA’s board of directors and engaging in direct input from the membership. Seventeen resolutions were received in 2012. Sixteen resolutions and three motions from the floor were accepted by the membership at the annual meeting on June 18, 2012. One motion from the floor was deferred to the board for its November meeting. This report presents...»

«Parliamentary Oversight for Government Accountability Edited by Riccardo Pelizzo, Rick Stapenhurst and David Olson World Bank Institute Copyright © 2006 The International Bank for Reconstruction and Development /The World Bank 1818 H Street, N.W. Washington, D.C. 20433, U.S.A. The World Bank enjoys copyright under protocol 2 of the Universal Copyright Convention. This material may nonetheless be copied for research, educational or scholarly purposes only in the member countries of The World...»

«Int. J. Mol. Sci. 2011, 12, 4661-4677; doi: 10.3390/ijms12074661 OPEN ACCESS International Journal of Molecular Sciences ISSN 1422-0067 www.mdpi.com/journal/ijms Article Sida rhomboidea. Roxb Leaf Extract Down-Regulates Expression of PPARγ2 and Leptin Genes in High Fat Diet Fed C57BL/6J Mice and Retards in Vitro 3T3L1 Pre-Adipocyte Differentiation Menaka C. Thounaojam 1, Ravirajsinh N. Jadeja 1, Umed V. Ramani 2, Ranjitsinh V. Devkar 1,* and A. V. Ramachandran 1 Division of Phytothrapeutics...»

«Autobiography of Madame Guyon by Madame Guyon About Autobiography of Madame Guyon by Madame Guyon Title: Autobiography of Madame Guyon URL: http://www.ccel.org/ccel/guyon/auto.html Author(s): Guyon, Madame (1647-1717) Publisher: Grand Rapids, MI: Christian Classics Ethereal Library Print Basis: Moody Press Source: Digitized by Harry Plantinga Rights: Public Domain Date Created: 2000-07-09 Status: Audio files narrated by Ruth Lomas CCEL Subjects: All; Classic; Biotarget=guyon; Biography; Proofed...»

«APPENDIX D PERTINENT CORRESPONDENCE FINAL FEASIBILITY REPORT AND ENVIRONMENTAL IMPACT STATEMENT PORT EVERGLADES HARBOR NAVIGATION STUDY BROWARD COUNTY, FLORIDA THIS PAGE LEFT INTENTIONALLY BLANK B~'QWARD COUNTY JI FLORIDA POR1 E\'t :R GL.i\ OES DEPART:\ II:::'\, Chief b~futiu/ ro rt Director's Offict' 11'50 Flkr Dri,c. Fon LIUkrdak. Fl(rida1331• '1~4-4fll!-U I-III I t\ \ J5 4-511-X711 August 14. 20 14 Colonel Alnn M. Dodd US Anny District Commander U.S. Army Corps of Engineers. Jackson illc...»

«Proceedings of ASBBS Volume 16 Number 1 CONSUMER REVENGE BEHAVIOR: A CROSSCULTURAL PERSPECTIVE Zourrig, Haithem Université du Québec à Montréal, Canada zourrig.haithem@.uqam.ca Chebat, Jean-Charles* HEC Montreal, Canada Jean-charles.chebat@hec.ca Toffoli, Roy Université du Québec à Montréal, Canada toffoli.roy@.uqam.ca * Corresponding author : Jean-Charles Chebat, CGECSC Chair Professor, HEC Montréal, 3000 Chemin de la Côte-Sainte-Catherine, Montréal (Qc) H3T 2A7 Canada. Tel.: +1 514...»

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