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



Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |

«Abstract. In this paper, we study a parity based generalization of the classical MULTIWAY CUT problem. Formally, we study the PARITY MULTIWAY CUT ...»

-- [ Page 1 ] --

Parameterized Tractability of Multiway Cut with Parity

Constraints

Daniel Lokshtanov1 and M. S. Ramanujan2

University of California, San Diego, USA.

daniello@ii.uib.no

The Institute of Mathematical Sciences, Chennai, India.

msramanujan@imsc.res.in

Abstract. In this paper, we study a parity based generalization of the classical MULTIWAY CUT problem. Formally, we study the PARITY MULTIWAY CUT

problem, where the input is a graph G, vertex subsets Te and To (T = Te ∪ To )

called terminals, a positive integer k and the objective is to test whether there exists a k-sized vertex subset S such that S intersects all odd paths from v ∈ To to T \ {v} and all even paths from v ∈ Te to T \ {v}. When Te = To, this is precisely the classical MULTIWAY CUT problem. If To = ∅ then this is the EVEN MULTIWAY CUT problem and if Te = ∅ then this is the ODD MULTIWAY CUT problem. We remark that even the problem of deciding whether there is a set of at most k vertices that intersects all odd paths between a pair of vertices s and t is NP-complete. Our primary motivation for studying this problem is the recently initiated parameterized study of parity versions of graphs minors (Kawarabayashi, Reed and Wollan, FOCS 2011) and separation problems similar to MULTIWAY CUT. The area of design of parameterized algorithms for graph separation problems has seen a lot of recent activity, which includes algorithms for MULTI-CUT on undirected graphs (Marx and Razgon, STOC 2011, Bousquet, Daligault and Thomass´, STOC 2011), k-WAY CUT (Kawarabayashi and Thorup, e FOCS 2011), and MULTIWAY CUT on directed graphs (Chitnis, Hajiaghayi and Marx, SODA 2012). A second motivation is that this problem serves as a good example to illustrate the application of a generalization of important separators which we introduce, and can be applied even when most of the recently develped tools fail to apply. We believe that this could be a useful tool for several other separation problems as well. We obtain this generalization by dividing the graph into slices with small boundaries and applying a divide and conquer paradigm over these slices. We show that PARITY MULTIWAY CUT is fixed parameter tractable (FPT) by giving an algorithm that runs in time f (k)nO(1). More precisely, we show that instances of this problem with solutions of size O(log log n) can be solved in polynomial time. Along with this new notion of generalized important separators, our algorithm also combines several ideas used in previous parameterized algorithms for graph separation problems including thenotion of important separators and randomized selection of important sets to simplify the input instance.

1 Introduction A fundamental min-max theorem about connectivity in graphs is Menger’s Theorem, which states that the maximum number of vertex disjoint paths between two vertices s and t, is equal to the minimum number of vertices whose removal separates these two vertices. Indeed, a maximum set of vertex disjoint paths between s, t and a minimum size set of vertices separating these two vertices can be computed in polynomial time.

A known generalization of this theorem, commonly known as Mader’s T -path Theorem [21] states that, given a graph G and a subset T of vertices, there are either k vertex disjoint paths with only the end points in T (such paths are called T -paths and if their length is odd (even), then odd (even) T -paths), or there is a vertex set of size at most 2k which intersects every T -path. Although computing a maximum set of vertex disjoint T -paths can be done in polynomial time by using matching techniques, the decision version of the dual problem of finding a minimum set of vertices that intersects every T -path is NP-complete for |T | 2. Formally, this problem is the classical MULTIWAY CUT problem, where the input is a graph G, a subset of vertices T called terminals, a positive integer k and the objective is to test whether there exists a k-sized vertex subset that intersects every T -path. This is a very well studied problem in terms of approximation, as well as parameterized algorithms [2, 9, 22]. In this paper we study a generalization of this classical MULTIWAY CUT problem to a parity version. Formally, we study the PARITY MULTIWAY CUT problem which is defined as follows.

PARITY MULTIWAY CUT (PMWC)

Instance: A graph G = (V, E), vertex subsets Te and To (T = Te ∪ To ), integer k.

Parameter: k Question: Is there a vertex set S of size at most k which intersects

1. all odd paths from a vertex v ∈ To to some other vertex u ∈ T \ {v},

2. all even paths from a vertex v ∈ Te to some other vertex u ∈ T \ {v}?

When Te = To, this is precisely the classical MULTIWAY CUT problem. If To = ∅ then this is the EVEN MULTIWAY CUT (EMWC) problem and if Te = ∅ then this is the ODD MULTIWAY CUT (OMWC) problem.

Our main motivation for studying this particular generalization is the recently initiated parameterized study of parity versions of graphs minors by Kawarabayashi, Reed and Wollan [15] and separation problems similar to MULTIWAY CUT [1, 4, 23]. The area of design of parameterized algorithms for graph separation problems has seen a lot of recent activity, which includes algorithms for MULTI-CUT on undirected graphs [23, 1], k-WAY CUT [16] and MULTIWAY CUT on directed graphs [4]. Furthermore, recently, Geelen, Gerards, Reed, Seymour and Vetta [10] proved an odd variant of Mader’s T path Theorem. They showed that, given a graph G and a subset T of vertices, there are either k vertex disjoint odd T -paths, or there is a vertex set of size at most 2k which intersects every odd T -path. This result has already turned out to be useful in graph theory [10, 18], as well as in the design of parameterized algorithms [11, 13, 14]. This result was crucial in settling the parameterized complexity of finding k vertex disjoint odd length cycles in a graph [14]. Observe that, this odd variant of Mader’s T -path Theorem naturally gives rise to the OMWC problem, a special case of PMWC.





The goal of parameterized complexity is to find ways of solving NP-hard problems more efficiently than by brute force. Here, the aim is to restrict the combinatorial explosion of computational difficulty to a parameter that is hopefully much smaller than the input size. Formally, a parameterization of a problem is the assignment of an integer k to each input instance and we say that a parameterized problem is fixed-parameter tractable (FPT) if there is an algorithm that solves the problem in time f (k) · |I|O(1), where |I| is the size of the input instance and f is an arbitrary computable function depending only on the parameter k. For more background, the reader is referred to the monographs [7, 8, 25].

Unlike MULTIWAY CUT, the PMWC is already NP-complete for the case when |T | = 2. Indeed, consider the following reduction from VERTEX COVER to PMWC.

Given an instance (G = (V, E), k) of VERTEX COVER, add two new vertices t1 and t2, make them both adjacent to every vertex in V, and set To = {t1, t2 } and Te = ∅. Call this new graph G. It is easy to see that G has a vertex cover of size at most k if and only if G has k-sized vertex subset that intersects every odd To −path. In fact, our argument shows that OMWC is NP-complete for the case when |T | = 2. One can similarly show that EMWC is NP-complete for the case when |T | = 2.

Marx [22] was the first to consider cut problems in the context of parameterized complexity. He gave an algorithm for MULTIWAY CUT with running time O(4k nO(1) ) k O(1) with the current fastest algorithm running in time O(2 n ) [5]. Even the recent developments in techniques to solve graph separation problems [23] and parity based graph problems [17], do not seem to apply to PMWC, a natural companion of these problems. In this paper, we introduce a new notion of generalized important separators, which along with the tools used to solve parameterized cut problems like MULTIWAY CUT and MULTI-CUT, allows us to design an FPT algorithm for PMWC. In general, this notion seems to allow us to bring a number of problems under a single umbrella, and in particular we demonstrate its application to PMWC. The main result of this paper is the following.

O(k) nO(1) time.

Theorem 1. PMWC can be solved in time 22 Our algorithm combines several ideas used in previous parameterized algorithms for graph separation problems including the notion of important separators and randomized selection of important sets to simplify the input instance.

Furthermore, we introduce a generalization of important separators, which we believe could be a useful tool for several other separation problems. The algorithm for PMWC has three phases, in the first phase using a well-known technique of iterative compression, we bound the number of even terminals by a linear function of k. In the second phase we remove even terminals using the notion of generalized important separators that we define in this paper and obtain f (k) instances of OMWC. We obtain the generalized important separators by dividing the graph into slices with small boundaries and applying a divide and conquer paradigm over these slices. In the final phase we solve these instances of OMWC by designing an FPT algorithm for OMWC. More precisely we obtain the following result.

O(k) nO(1) time.

Lemma 1. OMWC can be solved in time 22 We note that OMWC can be shown to be FPT be a simple reduction to the SUBSET OCT problem which was shown to be FPT in [17].

However, such an algorithm for OMWC would have a much worse dependence on the parameter k when compared to the algorithm we present in this paper. We also point out that in the case of the EMWC problem with two terminals, we may subdivide the edges incident on one of them, thus converting all even paths between these terminals into odd paths and vice versa. This reduction shows that OMWC is equivalent to EMWC in the case of two terminals and hence Lemma 1 immediately gives an FPT algorithm for EMWC in the case of two terminals. We also consider the edge version of PMWC, the EDGE PARITY MULTIWAY CUT (EPMWC) problem, where the input is a graph G, a subset of vertices T = Te ∪ To, a positive integer k and the objective is to determine whether there exists a k-sized edge subset that intersects every even path from a vertex v ∈ Te to T \ {v} and every odd path from a vertex v ∈ To to T \ {v}. We show that this problem is also FPT by establishing a parameter preserving reduction from EPMWC to PMWC.

Related Work. Parity problems hold a lot of promise and remain hitherto unexplored from the perspective of parameterized complexity, with exceptions that are few and far between. The first parameterized algorithm for ODD CYCLE TRANSVERSAL, finding a k sized vertex subset that intersect all odd cycles only appeared in 2004 [28]. Recently, Kawarabayashi and Reed [13] obtained an almost linear time parameterized algorithm for ODD CYCLE TRANSVERSAL, albeit with a much worse dependence on solution size than in [28]. Kawarabayashi and Reed [14] settled the parameterized complexity of ODD CYCLE PACKING, finding k vertex disjoint odd cycles in a graph, by showing it to be FPT. The Parameterized Complexity of ODD CYCLE PACKING was a long standing open problem and is much more general problem than the famous DISJOINT PATHS problem, finding vertex disjoint paths between given pairs of vertices. Recently, Kawarabayashi, Reed and Wollan [15] initiated the parameterized study of parity versions of graphs minors and gave an algorithm to find odd minors. Other studies include finding odd subdivision, parity paths passing through specific vertices [12, 11]. On the cut side, as we mentioned before, the area was initiated by the paper of Marx [22].

The notions used in this paper has been useful in settling parameterized complexity of variety of problems including DIRECTED FEEDBACK VERTEX SET [3], ALMOST 2 SAT [27] and ABOVE GUARANTEE VERTEX COVER [27, 26]. Recently, Marx and Razgon [23] and Bousquet, Daligault and Thomass´ [1] independently showed that e MULTI-CUT, finding k vertices to disconnect given pairs of terminals is FPT. Continuing this line of study, Chitnis, Hajiaghayi and Marx studied MULTIWAY CUT on directed graphs and showed it to be FPT [4].

2 Preliminaries

Given a path P, we refer to the number of edges in P as the length of P and denote it by |P |. We call a path an odd (even) path if the length of the path is odd (respectively even). We refer to the parity of |P | as the parity of the path P. If P is a path from some vertex in a set X to some vertex in a set Y, we say that P is an X-Y path. If A contains a single vertex x, we say that P is an x-Y path. Given a graph G = (V, E) and T ⊆ V, paths with only the end points in T are called T -paths and if their length is odd (even), then odd (even) T -paths. Given a vertex set S, we denote by P ∩ S, the set of vertices in S which intersect P. Given two paths P1 = v1,..., vl and P2 = u1,..., ur, such that one end point of P1 (say vl ) is the same vertex as some endpoint of P2 (say u1 ) and no other vertices of the two paths coincide, we define the concatenated path P1 + P2 as v1,..., vl, u2,..., ur. Given a walk W = v1,..., vl from t1 = v1 to t2 = vl, we define a closed loop (or loop) of W, as a closed walk W = vi, vi+1,..., vj, vp, vp+1,..., vr where vi = vr and vj = vp, vi+1,..., vj−1 and vp+1,..., vr−1 are either vertex disjoint simple paths which are subpaths of W, or are the same exact path which is a subpath of W. By deleting a closed loop W = vi,..., vr from W, we obtain the walk W = v1,..., vi, vr+1,..., vl. Note that deleting an even closed loop does not affect the parity of the walk, while deleting an odd closed loop flips the parity of the walk.

Hence, loops of the second type (for eg. v1, v2, v1 ), where the two internal subpaths coincide exactly can be removed without changing the parity of the walk since such loops are by definition, even. Hence, in our discussions, we will assume that such loops do not occur, that is, if W = vi, vi+1,..., vj, vp, vp+1,..., vr is a loop, then it is a cycle.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 6 |


Similar works:

«Clever Search: A WordNet Based Wrapper for Internet Search Engines Peter M. Kruse, André Naujoks, Dietmar Rösner, Manuela Kunze Otto-von-Guericke-Universität Magdeburg, Institut für Wissensund Sprachverarbeitung, P.O. Box 4120, D-39016 Magdeburg, Germany roesner|makunze@iws.cs.uni-magdeburg.de Typ des Beitrags/Type of the paper Workshop Clever Search: A WordNet Based Wrapper for Internet Search Engines Peter M. Kruse, André Naujoks, Dietmar Rösner, Manuela Kunze This paper presents an...»

«Minutes of the Municipal District of Ennis Committee Meeting held at 3.30pm on Tuesday February 2nd, 2016, in the Council Chamber, Áras Contae an Chláir, Clare County Council, New Road, Ennis, Co. Clare.Present: Councillors: P. Daly, J. Flynn, M. Howard, C. Colleran Molloy, A. Norton, J. Breen, P. Murphy and T. McNamara. Officials: Ger Dollard, Director of Services, Eamon O’Dea, Senior Executive Engineer, Catherine O’ Hara, Meetings Administrator & Fiona Whelan, Staff Officer. Item No. 1....»

«Tail Wags Dog? Time-Varying Information Shares in the Bund Market Christian Upper Thomas Werner Discussion paper 24/02 Economic Research Centre of the Deutsche Bundesbank October 2002 The discussion papers published in this series represent the authors’ personal opinions and do not necessarily reflect the views of the Deutsche Bundesbank. Deutsche Bundesbank, Wilhelm-Epstein-Strasse 14, 60431 Frankfurt am Main, Postfach 10 06 02, 60006 Frankfurt am Main Tel +49 69 95 66-1 Telex within Germany...»

«PAINLESS TENS ™ Wireless Rechargeable Instruction Manual Contents Introduction 2 Indications for Use 2 Parts 3 Safety Warnings 4 Specifications/Battery Information 7 Operating Instructions 8 Recommended Use 10 Recommended Electrode Placements 10 Cleaning and Storage 11 Troubleshooting 11 Introduction The wireless PAINLESS TENS is a single-channel transcutaneous electrical nerve stimulator (TENS) for over-the-counter (No prescription is required) use of pain relief. The device generates small...»

«Motherland by Vineeta Vijayaraghavan C o m i n g To g e t h e r i n S k o k i e Book Selection for J a n u a r y M a rc h 2 0 1 0 WELCOME LETTERS Dear Skokie Community: I am pleased at the collaboration that has resulted in the Coming Together in Skokie project that I believe presents a great opportunity for everyone to participate in a valuable community reading initiative and learning experience. The committee’s selection of Motherland is an outstanding choice for the project. The book is...»

«The Chariot to Nibbana Sila – Samadhi – Panna Pa Auk Sayadaw Compiled and Translated by U.Dhamminda) A Gift of Dhamma Page 1 of 86 A GIFT of Dhamma Maung Paw, California The Chariot to Nibbana (Sila – Samadhi – Panna) Namo tassa bhagavato arahato sammAsambuddhassa 1.0 INTRODUCTION 1.0 Introduction The method of practicing meditation, based on Visuddhimagga commentary, taught at Pa Auk Tawya Monastery. The method involves several stages of complex and involved practice. Each stage...»

«Getting started with Hydra Modeller Download Installation Hydra Modeller Basics Logging in Installing a template Building a network manually Importing a pre-defined network Setting GIS Layers Managing Data Scenarios Adding a new scenario by CSV Viewing Data Editing Data Installing an App Example 1: The Water Allocation Demo model Example 2: California sequential modelling Download Hydra Modeller is available at http://www.hydramodeller.com. Installation Double-click on ‘hydra.exe’ to open...»

«109 ISSN 1364-0380 (on line) 1465-3060 (printed) Geometry & Topology G T G G TT T T T G G Volume 5 (2001) 109{125 GT T G T G GTG Published: 24 February 2001 T G TG GG G T TT Cobordisms and Reidemeister torsions of homotopy lens spaces Siddhartha Gadgil Department of Mathematics SUNY at Stony Brook Stony Brook, NY 11794, USA Email: gadgil@math.sunysb.edu Abstract We show that any 3{dimensional homotopy lens space M 3 that is simplehomotopy equivalent to a lens space L(p; q) is topologically...»

«21 Magnesium supplementation and test anxiety Journal of Articles in Support of the Null Hypothesis Vol. 11, No. 2 Copyright 2015 by Reysen Group. 1539-8714 www.jasnh.com Oral Magnesium Supplementation and Test Anxiety in University Undergraduates Mathew H. Gendle Krysten P. O’Hara Elon University Magnesium (Mg++) has significant potential in the treatment of test anxiety. This study assessed the possibility that oral Mg++ could reduce test anxiety, through the reversal of stress-induced...»

«KOŠICKÝ SAMOSPRÁVNY KRAJ CENTRUM VÝSKUMU RASTLINNEJ VÝROBY – VÝSKUMNÝ ÚSTAV AGROEKOLÓGIE MICHALOVCE Polychlórované bifenyly a ich obsah v životnom prostredí regiónu Zemplín Informačná publikácia Košice 2009 Polychlórované bifenyly a ich obsah v životnom prostredí regiónu Zemplín Autori: RNDr. Igor Danielovič, PhD. RNDr. Ján Hecl, PhD. Ing. Rastislav Mati, CSc. Vydavateľ: Košický samosprávny kraj v spolupráci s CVRV Výskumným ústavom agroekológie Michalovce...»

«Supreme Court of Florida No. SC11-1446 ANA MARIA CARDONA, Appellant/Cross-Appellee, vs. STATE OF FLORIDA, Appellee/Cross-Appellant. [February 18, 2016] PER CURIAM. Ana Maria Cardona, who was twenty-nine years old at the time of the crimes, was found guilty of the 1990 first-degree murder and aggravated child abuse of her three-year-old son, Lazaro Figueroa. Cardona appeals her convictions and the death sentence imposed for the murder. We have jurisdiction. See art. V, § 3(b)(1), Fla. Const....»

«RELATIONES INTERNATIONALES Miscellaneous A Friend of the Danubians Honorary Consul Associate-Professor Jana Maftei, PhD Danubius University of Galati, Romania janamaftei@univ-danubius.ro Associate-Professor Anişoara Popa, PhD Danubius University of Galati, Romania apopa@univ-danubius.ro Abstract: In this paper we intend to make some considerations on being appointed the Honorary Consul of the Republic of Moldova at Saint-Etienne, France, the Professor Christian Daudel, collaborator of Danubius...»





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