FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 |   ...   | 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 6 ] --

We prove that B is a shattering set. Otherwise, let f : B → W be a function witnessing that B it is not a shattering set. It is not hard to see that M is a connected component in Gf \ W whose set of legs is a subset of W. We consider three subcases and arrive to a contradiction in each of them (see Figure 8).

Case 1a. M is a trivial component of Gf \ W. Let w be the only leg of M. Let w1 and w2 be other two distinct legs of K in G that are different from w. It follows that f maps every vertex of I(w1 ) ∪ I(w2 ) to w implying that there is a w − w1 and a w − w2 path in Gf whose internal vertices w∗ w∗ w∗

–  –  –

Figure 8: The 3 subcases of Case 1 in Lemma 4.6 for a component with legs {w∗, 1, 2, 3}. Case 1a:

w is the only leg of M in Gf \ W. The figure shows two paths in two distinct components connecting w to another leg (assuming w ∈ {1, 3}). Case 1b: f (v) = w for every v ∈ I(w). Case 1c: M is a nontrivial component in Gf \ W and f (v) = 3 for some v ∈ I(2); the figure shows a 2 − 3 path.

belong to two different components adjacent to w1 and w2 in G[K ∪ W ] \ M. Thus Gf has at least two non-trivial components that are subsets of K, in contradiction to the choice of f.

Case 1b. M is a nontrivial component of Gf \ W and f (v) = w for every v ∈ I(w) and w ∈ W (i.e., each vertex on the boundary is mapped to its preimage). As the smallest I(w∗ ) − I(W \ {w∗ }) separator in G[N (M ) ∪ M ] is larger than p, G[M ∪ W ] does not have a w∗ − W \ {w∗ } separator of size at most p, in contradiction to f being a witnessing function.

Case 1c. M is a nontrivial component of Gf \ W and there are distinct w1, w2 ∈ W such that f (v) = w2 for some v ∈ I(w1 ). By definition of I(w1 ), there is a w1 − v path in G whose internal vertices are fully contained in K \ M. Therefore, there is a w1 − w2 path in Gf whose internal vertices are disjoint from M, implying that Gf has a nontrivial component that is a subset of K, but distinct from the nontrivial component M. Thus the number of nontrivial components increases, a contradiction.

Case 2. We show that M ⊂ M and M is a good multiway cut in this case.

Let us show M ⊂ M first. Clearly, M = M, as M is disjoint from the (nonempty) set S ⊆ M. Thus M ⊂ M is only possible if M is disjoint from M, but Lemma 4.4 implies that the two disjoint connected sets M and M cannot be both multiway cuts.

For clarity, from now on we use IM (w) and IM (w) for the image of w on the boundary of M and M, respectively. Observe that IM (w) ∩ N (M ) ⊆ IM (w) for every w ∈ W : for every v ∈ IM (w) ∩ N (M ), there is a w − v path disjoint from M, which is obviously disjoint from M ⊂ M as well, and then v ∈ N (M ) implies v ∈ IM (w). We claim that either IM (w∗ ) or IM (W \ {w∗ }) is disjoint from N (M ). Suppose that there are two vertices v1 ∈ IM (w∗ ) ∩ N (M ) and v2 ∈ IM (W \ {w∗ }) ∩ N (M ). Vertices v1 and v2 can be connected by a path P whose internal vertices are in M (hence disjoint from S), contradicting the fact that S is an IM (w∗ )−IM (W \{w∗ })

–  –  –

Figure 9: The two possibilities in Case 2 of Lemma 4.6 (the set of legs is W = {w∗, 1, 2, 3}): either (a) N (M ) ⊆ IM (w∗ ) ∪ S or (b) N (M ) ⊆ IM (W \ {w∗ }) ∪ S holds.

separator. Therefore, either N (M ) ⊆ IM (w∗ ) ∪ S or N (M ) ⊆ IM (W \ {w∗ }) ∪ S holds. The two possibilities are demonstrated in Figure 9.

To show that |IM (w∗ ) \ W | and |IM (W \ {w∗ }) \ W | are both at most p, we argue as follows.

Suppose first that N (M ) ⊆ IM (w∗ ) ∪ S. We show that IM (w∗ ) ⊆ IM (w∗ ) and IM (W \ {w∗ }) ⊆ S hold, proving the bounds |IM (w∗ ) \ W | ≤ |IM (w∗ ) \ W | ≤ p and |IM (W \ {w∗ }) \ W | ≤ |S| ≤ p.

Let C1 (resp., C2 ) be the union of all those components of G[W ∪ (K \ M )] that contain a vertex of w∗ (resp., a vertex of W \ {w∗ }). As M is a multiway cut, C1 and C2 are disjoint. Now IM (w∗ ) and IM (W \ {w∗ }) are precisely the neighbors of M in C1 and C2, respectively. We observe that IM (w∗ ) ⊆ C1 : if v ∈ IM (w∗ ) is not in C1, then every w∗ − v path has to go through M ⊂ M, contradicting the definition of IM (w∗ ). Thus N (M ) ⊆ IM (w∗ ) ∪ S implies that every neighbor of M in C2 is from S (as it cannot be from IM (w∗ ) ⊆ C1 ), further implying IM (W \ {w∗ }) ⊆ S. Next, we show that S ⊆ C2. Suppose that there is a v ∈ S \ C2 and a w∗ − W \ {w∗ } path P intersecting S only in v (recall that S is a minimal w∗ − W \ {w∗ } separator). However, when the path P enters C2 from M, then, as we have seen, it enters a vertex of S ∩ C2 that is different from v, a contradiction.

Thus N (M ) ⊆ IM (w∗ ) ∪ S implies that every neighbor of M in C1 is from IM (w∗ ) (as it cannot be from S ⊆ C2 ), further implying IM (w∗ ) ⊆ IM (w∗ ). Finally, we can deduce that N (M ) = IM (W ), as required by the definition of good multiway cut: indeed, every vertex of N (M ) ⊆ IM (w∗ ) ∪ S is in C1 ∪ C2, that is, either in IM (w∗ ) or in IM (W \ {w∗ }). Therefore, we have shown that M ⊂ M is a good multiway cut.

A symmetrical argument (exchanging the role of w∗ and W \ {w∗ }) shows that if N (M ) ⊆ IM (W \ {w∗ }) ∪ S, then IM (w∗ ) ⊆ S and IM (W \ {w∗ }) ⊆ IM (W \ {w∗ }), implying the bounds |IM (w∗ ) \ W | ≤ p and |IM (W \ {w∗ }) \ W | ≤ p. Thus in both cases, we proved that M ⊂ M is a good multiway cut.

Case 3. Assume now that the algorithm returns B := (S ∪ N (M )) \ W as a shattering set.

This happens because the number of components of G[K \ (N (M ) ∪ S)] which are multiway cuts of (G[K ∪ W ], W ) is not exactly one. According to Lemma 4.5, N (M ) ∪ S is indeed a shattering set in this case. Clearly, its size is at most 3p.

Lemma 4.3 follows by iterative application of Lemma 4.6.

Proof (of Lemma 4.3). It is not hard to see that K is a good multiway cut of (G[K ∪ W ], W ); in particular, I(w) = {w} for every w ∈ W, and hence I(w∗ ) \ W = I(W \ {w∗ }) = ∅. Let M0 = K.

Apply the algorithm of Lemma 4.6 to M0. The algorithm either returns a shattering set of size at most 3p or a good multiway cut M1 ⊂ M0. In the former case, we return the shattering set, in the latter case, apply the algorithm of Lemma 4.6 to M1. Continuing this way, we obtain a sequence M0 ⊃ M1 ⊃... of good multiway cuts of decreasing size. It follows that after at most |V (G)| iterative applications of the algorithm of Lemma 4.6, a shattering set of size at most 3p will be returned.

5 Finding a shadowless solution by reduction to Almost 2SAT The goal of this section is to show that we can solve Bipedal Multicut Compression∗ if we know that there is at least one shadowless solution.

Let x1,..., xn be a set of variables; a literal is either a variable xi or its negation xi. Recall that a 2CNF formula is a conjunction of clauses with at most two literals in each clause, e.g., (x1 ∨ x2 ) ∧ (x3 ) ∧ (x1 ∨ x4 ). The classical 2SAT problem asks if a given 2CNF formula has a satisfying assignment. It is well-known that a satisfying assignment for a 2CNF formula can be found in linear time (if exists). However, it is NP-hard to find an assignment that maximizes the number of satisfied clauses, or equivalently, to find a minimum set of clauses whose removal makes the formula satisfiable. Lokshtanov et al. [32] (improving earlier work [42, 14, 41]) gave an O∗ (2.3146k ) time algorithm for the problem of deciding if a 2CNF formula can be made satisfiable by the deletion of at most k clauses; they call this problem Almost 2SAT. We need a variant of the result here, where instead of deleting at most k clauses, we are allowed to delete at most k variables. An easy reduction (see Appendix B) gives an algorithm for this variant. If φ is a 2CNF formula and X is a set of variables, then we denote by φ \ X the formula obtained by removing every clause containing a literal of a variable in X.

Theorem 5.1.

Given a 2CNF formula φ and an integer k, in time O∗ (2.3146k ) we can either find a set X of at most k variables such that φ \ X is satisfiable, or correctly state that no such set X exists.

It is not difficult to reduce finding a shadowless solution to the problem solved by Theorem 5.1.

For each vertex v of G\W, we introduce a variable whose value expresses which leg of the component containing v is reachable from v. This formulation cannot express that a vertex is separated from both legs. However, as we assume that there is a shadowless solution, we do not have to worry about such vertices.

Proof (of Lemma 2.7). We encode the Bipedal Multicut Compression∗ instance I = (G, T, W, p) as a 2CNF formula φ the following way. For each component C of G \ W having two legs, let 0 (C) and 1 (C) be the two legs. If component C has only one leg, then let 0 (C) be this leg, and let 1 (C) be undefined. For every vertex v ∈ C, let 0 (v) = 0 (C) and 1 (v) = 1 (C). We construct a formula φ whose variables correspond to V (G) \ W. The intended meaning of the variables is that v has value b ∈ {0, 1} if v is in the same component as b (v) after removing the solution. To enforce this

interpretation, φ contains the following clauses:

–  –  –

This completes the description of φ. Note that no clause is introduced for pairs (u, v) ∈ T with u, v ∈ W, but these pairs are automatically separated by a solution that is a multiway cut of W.

Furthermore, we can assume that W induces an independent set, otherwise there is no solution.

We show first that if I has a shadowless solution S, then removing the corresponding variables of φ makes it satisfiable. As S is shadowless and it is a multiway cut of W, every vertex of G \ S is in the same component as exactly one of 0 (v) and 1 (v); let the value of variable v be b if vertex v is in the same component as b (v). It is clear that this assignment satisfies the clauses in the first two groups. Consider a clause (u = bu ∨ v = bv ) from the third group. This means that (u, v) ∈ T and bu (u) = bv (v) = w ∈ W. If this clause is not satisfied, then u = bu and v = bv. By the way the assignment was defined, this is only possible if u is in the same component of G \ S as bu (u) = w and v is in the same component of G \ S as bv (v) = w. Therefore, u and v are in the same component of G \ S, contradicting the assumption that S is a solution of I. Clauses in Group 4 can be checked similarly.

We have shown that φ can be made satisfiable by the deletion of p variables. By Theorem 5.1, we can find such a set S of variables in time O∗ (4p ). To complete the proof, we show that such a set S corresponds to a (not necessarily shadowless) solution of I. Let us show first that S is a multiway cut of W. Suppose that there is a path P connecting w0, w1 ∈ W in G \ S. We can assume that the internal vertices of P are disjoint from W, i.e., they are in one component C of G \ W with two legs.

Thus there is a path P from a neighbor v0 of w0 to a neighbor v1 of w1 in C \ S. Suppose without loss of generality that 0 (C) = w0 and 1 (C) = w1. As the clauses in Group 1 are satisfied, every variable of P has the same value. However, because of the clauses in Group 2, we have xv0 = 0 and xv1 = 1, a contradiction. Therefore, we can assume that S is a multiway cut of W.

Suppose now that there is some (u, v) ∈ T such that u, v ∈ W are in the same component of G \ S ; let P be a u − v path in G \ S. As W is a multicut of T, it is clear that P goes through at least one vertex of W. We have seen that S is a multiway cut of W, thus P goes through exactly one vertex of W. Let P = P1 wP2 for some path P1 that is fully contained in the component of G \ W containing u and path P2 fully contained in the component containing v. Let bu, bv ∈ {0, 1} be such that bu (u) = bv (v) = w. Group 1 ensures that every variable of P1 has the same value and Group 2 ensures that the last variable of P1 has value bu, thus u = bu. A similar argument shows that v = bv. However, this means that clause (u = bu ∨ v = vu ) of Group 3 is not satisfied, a contradiction. Finally, a similar argument shows that the clauses in Group 4 ensure that pairs (u, v) ∈ T with u ∈ W, v ∈ W are separated.

6 Hardness of Directed Multicut We prove that Directed Edge Multicut is W[1]-hard parameterized by the solution size, thus it is not fixed-parameter tractable (assuming the widely-held complexity hypothesis FPT = W[1]).

Recall that the edge and vertex versions are equivalent, thus the hardness result holds for both versions. The proof below proves the hardness result for the weighted version of the problem, where each edge has a positive integer weight, and the task is to find a multicut with total weight at most p. If the weights are polynomial in the size of the input (which is true in the proof), then the weighted version can be reduced to the unweighted version by introducing parallel edges. Thus the proof proves the hardness of the unweighted version as well. For notational convenience, we allow edges with weight ∞; such edges can be easily replaced by edges with sufficiently large finite weight.

Theorem 6.1.

Directed Edge Multicut is W[1]-hard parameterized by the size p of the cutset.

Proof. We prove hardness for the weighted version of the problem by parameterized reduction from Clique. Let G be a graph with m edges and n vertices where a clique of size t has to be found. We construct an instance of Directed Edge Multicut containing t(t − 1) gadgets: for each ordered pair (i, j) (1 ≤ i, j ≤ t, i = j), there is a gadget Gi,j. Intuitively, each gadget Gi,j has 2m possible states and a state represents an ordered pair (vi, vj ) of adjacent vertices. We would like to ensure that the gadgets describe a t-clique {v1,..., vt } in the sense that Gi,j represents the pair (vi, vj ).

In order to enforce this interpretation, we need to connect the gadgets in a way that enforces two


(1) if Gi,j represents (vi, vj ), then Gj,i represents (vj, vi ), and (2) if Gi,j represents (vi, vj ) and Gi,j represents (ui, uj ), then vi = ui.

–  –  –

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

Similar works:

«Thank you for your interest in our College: this is a great time to come and join our team! Special things are happening at The Latimer Arts College: we are really going places. Visitors to the school can sense it and we hope that you will as well. Our students are fantastic and thrive in a happy, safe and purposeful learning environment. Our staff share a passionate and steely determination to make the College the best that it can be for the good of our students. It was therefore with great...»

«The Pilgrimage 5/13/05 3:40 PM Page i THE PILGRIMAGE The Pilgrimage 5/13/05 3:40 PM Page ii ALSO BY PAULO COELHO The Alchemist The Valkyries By the River Piedra I Sat Down and Wept The Fifth Mountain Veronika Decides to Die The Devil and Miss Prym Manual of the Warrior of Light Eleven Minutes The Zahir The Pilgrimage 5/13/05 3:40 PM Page iii PAULO COELHO THE PILGRIMAGE TRANSLATED BY ALAN R. CLARKE HarperCollinsPublishers The Pilgrimage 5/13/05 3:40 PM Page iv HarperCollinsPublishers 77–85...»

«Available online at www.sciencedirect.com ScienceDirect Energy Procedia 54 (2014) 680 – 689 4th International Conference on Advances in Energy Research 2013, ICAER 2013 Comparative Analysis of Solar Photovoltaic Lighting Systems in India Rishi Raj Borah a, *, Debajit Palit b, Sadhan Mahapatra a a Department of Energy, Tezpur University, Tezpur, Napam 784028, Assam, India b The Energy and Resources Institute, Darbari Seth Block, IHC Complex, Lodhi Road, New Delhi 110 003,India Abstract This...»

«Brandeis University Classical Studies Department Nuntius Nullum est iam dictum quod non dictum est prius. News from The Classical Studies Department at Brandeis University Summer/Fall 2006 Volume III, Number 1 Notabilia ! Congratulations to the Brandeis Class of 2006, which graduated on May 20, 2006, and to our graduating majors and minors! Majors: Catherine K. Baker ! Deborah R. Berman ! Melanie R. Brault ! Kathryn E. Harris ! Gayle M. McElvain ! Benjamin M. Woodring. Minors: Mandi J. Altman !...»

«International Journal of Advancements in Research & Technology, Volume 4, Issue 1, January -2015 59 ISSN 2278-7763 LIBRARY ENTREPRENEURSHIP A PANACEA TO LIBRARY UNDER FUNDING IN NIGERIA: A STUDY OF MUHAMMADU LIBRARY FEDERAL POLYTECHNIC BAUCHI BY MADALLA AJEMASU, HAJARATU C. PISAGIH AND RHODA Y. J. DEGRI ABSTRACT Funds for Nigerian academic libraries and information services are traditionally derived from their parent institution. These funds vary from a fixed percentage of an institutions...»

«GCAT genes TACG GCAT Review DNA Polymerases λ and β: The Double-Edged Swords of DNA Repair Elisa Mentegari, Miroslava Kissova, Laura Bavagnoli, Giovanni Maga * and Emmanuele Crespan * Institute of Molecular Genetics, IGM-CNR, via Abbiategrasso 207, 27100 Pavia, Italy; elisa.mentegari01@universitadipavia.it (E.M.); miroslava.kissova01@universitadipavia.it (M.K.); bavagnoli@igm.cnr.it (L.B.) * Correspondence: maga@igm.cnr.it (G.M.); emmanuelecrespan@gmail.com (E.C.); Tel.: +39-0382-546354...»

«Munich Personal RePEc Archive Research and Science Today ˘ Alex andra DRAGHICI and Irina DAMIAN and Andreea Maria DAN and Diana-Gabriela POPA and Elena Mihaela ˘ EZARU and Ana Maria Roxana PAICA and Adriana Rodica MURESAN and Raluca LUTAI and Ileana Daniela,, SERBAN and Mihaela Andreea CIOREI and ¸ ˘ ˘ Flavius-Cristian MARCAU Constantin Brancusi University of Targu-Jiu, Romania 1. September 2011 Online at http://mpra.ub.uni-muenchen.de/41929/ MPRA Paper No. 41929, posted 14. October 2012...»

«Synesthesia: Phenomenology And Neuropsychology A Review of Current Knowledge Richard E. Cytowic 4720 Blagden Terrace, NW Washington DC 20011-3720 USA neuroman@glib.org Copyright (c) Richard E. Cytowic 1995 PSYCHE, 2(10), July 1995 http://psyche.cs.monash.edu.au/v2/psyche-2-10-cytowic.html KEYWORDS: consciousness, emotion, perception, subjectivity, synesthesia, neurology. ABSTRACT: Synesthesia (Greek, syn = together + aisthesis = perception) is the involuntary physical experience of a...»

«Notes Meeting: St Blazey, Fowey & Lostwithiel Community Network Panel Date: Monday 17 October 2016 Time: 7pm Location: Church Rooms, Church Lane, Lostwithiel, PL22 0DD Present Title/Representing Benedicte Jenkinson CC (Chair) Cornwall Councillor Lostwithiel David Hughes CC Cornwall Councillor – Fowey & Tywardreath Roy Taylor CC Cornwall Councillor – St Blazey Councillor Roger Smith Luxulyan Parish Council Councillor Robin Anderson St Sampson Parish Council Councillor Richard Read St Winnow...»

«BGC Notes, LLC v Gordon 2015 NY Slip Op 31221(U) July 13, 2015 Supreme Court, New York County Docket Number: 651808/14 Judge: Saliann Scarpulla Cases posted with a 30000 identifier, i.e., 2013 NY Slip Op 30001(U), are republished from various state and local government websites. These include the New York State Unified Court System's E-Courts Service, and the Bronx County Clerk's office. This opinion is uncorrected and not selected for official publication. [* 1] SUPREME COURT OF THE STATE OF...»

«A RT I C L E 369 The Geneva Model of discourse analysis: an interactionist and modular approach to discourse organization Discourse Studies Copyright © 2002 SAGE Publications. (London, Thousand Oaks, CA and New Delhi) Vol 4(3): 369–393. [1461-4456 L A U R E N T F I L L I E T TA Z A N D E D D Y R O U L E T (200208) 4:3; 369–393; 023677] U N I V E R S I T Y O F G E N E VA This article presents recent developments in the Geneva modular A B S T R AC T and interactionist approach to discourse...»

«mu Written Testimony Manuel Manny Fernandez, National Managing Partner Campus Recruiting KPMG LLP House Financial Services Committee Subcommittee on Oversight and Investigation July 12,2006 Introduction Good afternoon Chairwoman Kelly and Ranking Member Gutierrez. Thank you very much for the opportunity to testify today on this critical topic. I would also like to thank Ranking Member Barney Frank for his leadership on this issue. My name is Manny Fernandez, and I am KPMG's National Managing...»

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