FREE ELECTRONIC LIBRARY - Abstracts, online materials

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

Fixed-parameter tractability of multicut parameterized by the size

of the cutset∗

D´niel Marx† Igor Razgon‡


August 27, 2013


Given an undirected graph G, a collection {(s1, t1 ),..., (sk, tk )} of pairs of vertices, and an

integer p, the Edge Multicut problem ask if there is a set S of at most p edges such that the

removal of S disconnects every si from the corresponding ti. Vertex Multicut is the analogous

problem where S is a set of at most p vertices. Our main result is that both problems can be solved in time 2O(p ) · nO(1), i.e., fixed-parameter tractable parameterized by the size p of the cutset in the solution. By contrast, it is unlikely that an algorithm with running time of the form f (p) · nO(1) exists for the directed version of the problem, as we show it to be W[1]-hard parameterized by the size of the cutset.

1 Introduction From the classical results of Ford and Fulkerson on minimum s − t cuts [20] to the more recent √ O( log n)-approximation algorithms for sparsest cut problems [44, 1, 18], the study of cut and separation problems have a deep and rich theory. One well-studied problem in this area is the Edge Multicut problem: given a graph G and pairs of vertices (s1, t1 ),..., (sk, tk ), remove a minimum set of edges such that every si is disconnected from its corresponding ti for every 1 ≤ i ≤ k. For k = 1, Edge Multicut is the classical s − t cut problem and can be solved in polynomial time. For k = 2, Edge Multicut remains polynomial-time solvable [46], but it becomes NP-hard for every fixed k ≥ 3 [15]. Edge Multicut can be approximated within a factor of O(log k) in polynomial time [22] (even in the weighted case where the goal is to minimize the total weight of the removed edges). However, under the Unique Games Conjecture of Khot [29], no constant factor approximation is possible [7]. One can analogously define the Vertex Multicut problem, where the task is to remove a minimum set of vertices. An easy reduction shows that the vertex version is more general than the edge version.

Using brute force, one can decide in time nO(p) if a solution of size at most p exists. Our main result is a more efficient exact algorithm for small values of p (the O∗ notation hides factors that are

polynomial in the input size):

Theorem 1.1.

Given an instance of Vertex Multicut or Edge Multicut and an integer p, one can find in time O∗ (2O(p ) ) a solution of size p, if such a solution exists.

∗ A preliminary version of the paper was presented at STOC 2011 [37]. Research of the second author was supported by the European Research Council (ERC) grant “PARAMTIGHT: Parameterized complexity and the search for tight complexity results,” reference 280152.

† Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), dmarx@cs.bme.hu ‡ Department of Computer Science and Information Systems, Birkbeck, University of London. igor@dcs.bbk.ac.uk That is, we prove that Vertex Multicut and Edge Multicut are fixed-parameter tractable parameterized by the size p of the solution, resolving a very challenging open question in the area of parameterized complexity. (Recall that a problem is fixed-parameter tractable (FPT) with a particular parameter p if it can be solved in time f (p) · nO(1), where f is an arbitrary computable function depending only on p; see [17, 19, 39] for more background). The question was first asked explicitly perhaps in [34]; it has been restated more recently as an open problem in e.g., [25, 8].

Our result shows in particular that multicut is polynomial-time solvable if the size of the optimum √ solution is O( 3 log n) (where n is the input size).

One reason why multicut is a fundamental problem is that it is able to express several other problems. It has been observed that a correlation clustering problem called Fuzzy Cluster Editing can be reduced to (and in fact, equivalent with) Edge Multicut [3, 16, 2]. Our results show that Fuzzy Cluster Editing is FPT parameterized by the editing cost, settling this open problem discussed e.g., in [3].

Previous work. The fixed-parameter tractability of multicut and related problems has been thoroughly investigated in the literature. Edge Multicut is NP-hard on trees, but it is known to be FPT, parameterized by the maximum number p of edges that can be deleted, and admits a polynomial kernel [5, 26]. Multicut problems were studied in [25] for certain restricted classes of graphs. For general graphs, Vertex Multicut is FPT if both p and and the number of terminal pairs k are chosen as parameters (i.e, the problem can be solved in time f (p, k) · nO(1) [35, 45, 24] for some function f ). The algorithm of Theorem 1.1 is superior to these result in the sense that the running time depends polynomially on the number k of terminals pairs, and the exponential dependence is restricted to the parameter p, the number of deletions. For the special case of Multiway Cut (where terminals in a set T have to be pairwise separated form each other), algorithms with running time of the form f (p) · nO(1) were already known [35, 8, 24], but apparently these algorithms do not generalize in an easy way to multicut. An FPT 2-approximation algorithm was given in [36] for Edge Multicut: in time O∗ (2O(p log p) ), one can find a solution of size 2p if a solution of size p exists. There is no obvious FPT algorithm for the problem even on bounded-treewidth graphs, although one can obtain linear-time algorithms if the treewidth remains bounded after adding an edge si ti for each terminal pair [23, 40]. A PTAS is known for bounded-degree graphs of bounded treewidth [6].

Our techniques. The first two steps of our algorithm follows [36]. We start by an opening step that is fairly standard in the design of FPT algorithms. Instead of solving the original Vertex Multicut problem, we solve the compression version of the problem, where the input contains a solution W of size p + 1, and the task is to find a solution of size p (if exists). A standard argument called iterative compression [43, 28] shows that if the compression problem is FPT, then the original problem is FPT. Alternatively, we can use the polynomial-time approximation algorithm of Gupta [27], which produces a solution W of size p2 if a solution of size p exists. In this case, O(p2 ) iterations of the compression algorithm gives a solution of size p.

Next, as in [36], we try to reduce the compression problem to Almost 2SAT (delete k clauses to make a 2-CNF formula satisfiable; also known as 2CNF Deletion), which is known to be FPT [42, 14, 41]. However, our 2SAT formulation is very different from the one in [36]: we introduce a single variable xv only for each vertex of G, while in [36] there is a variable xv,w for every vertex v ∈ V (G) and vertex w ∈ W of the initial solution. This simpler reduction to Almost 2SAT is

correct only if the instance satisfies two quite special properties:

(1) every component of G \ W is adjacent to at most two vertices of W (“has at most two legs”), and (2) there is a solution S such that every component of G \ S contains a vertex of W (“no vertex is isolated from W after removing the solution S” or “no vertex is in the shadow of S”).

The main part of the paper is devoted to showing how these properties can be achieved. In order to achieve property (1), we show by an analysis of cuts and performing appropriate branching steps that the set W can be extended in such a way that every component has at most two legs (Section 4).

To achieve property (2), we describe a nontrivial way of sampling random subset of vertices such that if we remove this subset by a certain contraction operation (taking the torso of the graph), then without changing the solution, we get rid of the parts not reachable from W with some positive probability (Section 3). This random sampling uses the concept of “important separators,” which was introduced in [35], and has been implicitly used in [9, 42, 8] in the design of parameterized algorithms. We consider the random sampling of important separators the main new technical idea of the paper. This technique and its generalizations have turned out to be useful for other problems as well [11, 31, 12, 11, 10, 33, 30] and we expect it to have further application in the future.

Directed graphs. Having resolved the fixed-parameter tractability of Vertex Multicut, the next obvious question is what happens on directed graphs. Note that for directed graphs, the edge and vertex versions are equivalent. In directed graphs, multicut becomes much harder to 1− approximate: there is no polynomial-time 2log n -approximation for any 0, unless NP ⊆ ZPP [13]. From the fixed-parameter tractability point of view, the directed version of the problem received particular attention because Directed Feedback Vertex Set or DFVS (delete p vertices to make the graph acyclic) can be reduced to Directed Multicut. The fixed-parameter tractability of DFVS had been a longstanding open question in the area of parameterized complexity until it was solved by Chen et al. [9] recently. The main idea that led to the solution is that DFVS can be reduced to a variant (in fact, special case) of Directed Multicut called Skew Multicut, where the task is to break every path from si to tj for every i j. By showing that Skew Multicut is FPT parameterized by the size of the solution, Chen et al. [9] proved the fixed-parameter tractability of DFVS. We show in Section 6 that, unlike Skew Multicut, the general Directed Multicut problem is unlikely to be FPT.

Theorem 1.2.

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

Independent and followup work. A preliminary version of this paper appeared in [37]; the current version contains essentially the same algorithm, but the terminology and organization of Section 5 were significantly changed. Independently from our work, Bousquet et al. [4] presented in the same volume a proof that Multicut is FPT parameterized by the size p of the solution. The two algorithms have certain parts in common: both reduce the problem to the compression version and both ensure that we have to deal with components having only two legs. However, the main part of the two algorithms are substantially different: the current paper introduces the technique of random sampling of important separators and uses it to reduce the problem to Almost 2SAT, while Bousquet et al. [4] uses an approach based on a series of problem-specific reductions to reduce the problem to 2SAT.

Subsequently to the first version of this paper, random sampling of important separators has been used in several other applications. For undirected graphs, the technique was used by Lokshtanov and Ramanujan [33] to solve a parity version of Multiway Cut and by Chitnis et al. [10] to solve a homomorphism problem generalizing certain deletion problems. For directed graphs, even though Directed Multicut is W[1]-hard parameterized by p (see Section 6), Chitnis et al. [11] proved that the special case Directed Multiway Cut (Given a set T of terminals, break every directed path between two different terminals by removing at most p edges/vertices) is FPT parameterized by p. A consequence of this result is that Directed Multicut with k = 2 is FPT parameterized by p is FPT. Kratsch et al. [30] proved that Directed Multicut on directed acyclic graphs (DAGs) is FPT with combined parameters k and p, and strenghed our hardness result by showing that Directed Multicut remains W[1]-hard parameterized by p even on DAGs. However, the complexity of Directed Multicut for k = 3 or with combined parameters k and p remains an interesting open question.

Chitnis et al. [12] use the random sampling technique to show the fixed-parmeter tractability of Directed Subset Feedback Vertex Set. They present an


framework that formalizes under which conditions this technique can be used, and they improve the randomized selection and its analysis to obtain better success probability and improved running time.

A very different application of the technique is given by Lokshtanov and Marx [31] in the context of clustering problems. They study a family of clustering problems such as partitioning the vertices of an undirected graph into clusters of size at most p such that at most q edges leave each cluster.

The problem boils down to being able to check whether a given vertex v is contained in such a cluster. It turns out that the random sampling of important separators technique can be used to show that this task (and therefore the original clustering problem) is FPT parameterized by q by reducing it to a knapsack-like problem.

2 Framework: compression, shadows, legs Let G be an undirected graph and let T = {(s1, t1 ),..., (sk, tk )} be a set of terminal pairs. We say that a set S ⊆ V (G) of vertices is a multicut of (G, T) if there is no component1 of G \ S that contains both si and ti for some 1 ≤ i ≤ k (note that it is allowed that S contains si or ti ). The

central problem of the paper is the following:

–  –  –

We prove the fixed-parameter tractability of Vertex Multicut by a series of reductions (see Figure 1). First we argue that it is sufficient to solve an easier solution compression problem. Then we present two reductions that modify the problem in such a way that it is sufficient to look for solutions that are shadowless and we can assume that the instance is bipedal. The last step of the proof is reducing this special variant of the problem to Almost 2SAT.

2.1 Compression The first step in the proof of Theorem 1.1 is a standard technique in the design of parameterized algorithms: we define and solve the compression problem, where it is assumed that the input contains a feasible solution of size larger than p. As this technique is standard (and in particular, we follow the approach of [36] for Edge Multicut), we keep this section short and informal.

–  –  –

Intuitively, it is clear that proving Lemma 2.1 could be easier than proving that Vertex Multicut is FPT: the extra input W can give us useful structural information about the graph (and as |W | appears in the running time, a large W is also helpful). What’s not obvious is how solving Multicut Compression gives us any help in the solution of the original Vertex Multicut problem. We sketch two methods.

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

Similar works:

«Marine Potable Water Test Kit Instruction Booklet Page | 1 9th Sept. 2013 Marine Potable Water Test Kit Instruction Booklet Page 3. Safety and Hygiene 5. Notes page 6. Chlorine (free, combined and total) 7. pH 8. Chlorine (high range) 9. Coliforms and E.Coli bacteria 11. Total Bacteria Count 13. Iron 14. Copper 15. Colour 15. Turbidity 16. Enterococci bacteria 17 24. Portable Incubator User Instructions 25. Spares and consumables Page | 2 9th Sept. 2013 Safety and Hygiene Workplace and...»

«MANAGEMENT’S DISCUSSION AND ANALYSIS of WEST KIRKLAND MINING INC. (formerly Anthem Ventures Capital Corp.) For the Three and Six Months Ended June 30, 2012 and 2011 Office: TSXV: WKM Suite 328 Phone: (604) 685-8311 550 Burrard Street Fax: (604) 484-4710 Vancouver, BC V6C 2B5 info@wkmining.com Canada www.wkmining.com West Kirkland Mining Inc. Management’s Discussion and Analysis For the Three and Six Months Ended June 30, 2012 and 2011 This management’s discussion and analysis (“MD&A”)...»


«A review on Architecture in Muslim Spain and North Africa (756-1500AD) Author: Rabah Saoud BA, MPhil, PhD IMPORTANT NOTICE: Chief Editor: Professor Salim Al-Hassani All rights, including copyright, in the content of this document are owned or controlled for these purposes by FSTC Limited. In Production: Ahmed Salem BSc accessing these web pages, you agree that you may only download the content for your own personal non-commercial use. You are not permitted to copy, broadcast, download, store...»

«”NATO Charity Bazaar” ASBL Avenue du Maréchal 20B, 1180 Uccle, Belgium. No: 874.358.592 General Meeting 25 September 2012 The General Meeting started at 10h10 In Attendance: 33 Full Members were present or represented Absent: Georgia, Iceland, Luxembourg and Sweden 1. Agenda – Susanne Christtreu (President) / president@natocharitybazaar.org 1.1. Welcome to new members Susanne welcomed the following new members: Yves Lecoq (ANR Belgium), Ivaylo Toshirov (ANR Bulgaria), Bisserka Bondinova...»

«University Mailing Addresses Sir George Williams Campus Loyola Campus 1455 De Maisonneuve Blvd. W. 7141 Sherbrooke St. W. Montreal, Quebec Montreal, Quebec H3G 1M8 H4B 1R6 Web Address concordia.ca Communication of Information to Provincial Ministère de l’Éducation, de l’Enseignement supérieur et de la Recherche Under the terms of an agreement between Concordia University and the provincial Ministère de l’Éducation, de l’Enseignement supérieur et de la Recherche, approved by the...»

«VOLUME 3, NUMBER 1 | AUTUMN, 2016 DatelineDistrict On Not Walking Alone INSIDE THIS ISSUE As a frequent traveler, I spend a lot of time sitting in airports. My routine is to pay way too much for a cup of coffee, then pull out my laptop and knock a few tasks off of the daily checklist. But I also make sure to sit where I can take a break now and then and just people watch. The parade of assorted humanity always reminds and reassures me PAGE 2 of God’s endlessly creative presence. Recently, I...»

«THE DOWNSTATE DELAWARE GENEALOGICAL SOCIETY TOMBSTONES OF SUSSEX COUNTY DELAWARE VOLUME THREE REVISED BRIDGEVILLE CEMETERY AS OF SEPTEMBER, 2015 BRIDGEVILLE CEMETERY ABBOTT, Denise Renaé, ssw-Timothy Paul Abbott, b. 07/26/1958, d. N/D ABBOTT, Timothy Paul, ssw-Denise Renaé Abbott, b. 07/14/1956, d. 03/08/1983 ABSHER, David, bsp-O. Kenneth Absher, Age 13 hours 25 min., b. N/D, d. 02/21/1962 ABSHER, O. Kenneth, bsp-David Absher, b. 11/12/1963, d. 05/23/1965 ADAMS, Alice B., w/o Elkton G. Adams,...»

«The Cameroonian-Nigerian Border Conflict in the Lake Chad Region: Assessment of the Resource and Conflict Management Capacities of the Lake Chad Basin Commission Florence Alessa Metz, PhD Student, ETH Zürich, Switzerland1 Key Words: Lake Chad Basin Commission, environmental conflict, resource conflict management ABSTRACT With the increasing impact of global climate change, a great deal of recent writings has analyzed the link between environment and conflict. Whereas some researchers warn that...»

«Celtic and Afro-Asiatic Graham R. Isaac (National University of Ireland, Galway) It is not remarkable that structural similarities between the Insular Celtic and some Afro-Asiatic1 languages continue to exert a fascination on many people. Research into any language may be enlightening with regard to the understanding of all languages, and languages that show similar features are particularly likely to provide useful information. It is remarkable that the structural similarities between Insular...»

«cv 2010 1 !{ SANJAY WAUHWA Attorney for Plaintiff SECURITIES AND EXCHANGE COMMISSION _1. '. 5 New York Regional Office 3 World Financial Center Room 400 New York, New York 10281 (212) 336-0181 UNITED STATES DISTRICT COURT SOUTHERN DISTRICT OF NEW YORK -X SECURITIES AND EXCHANGE COMMISSION, Plaintiff, COMPLAINT -againstECFCASE MATTHEW G. TEEPLE, DAVID T. RILEY, and JOHN V. JOHNSON, Defendants. -x. Plaintiff Securities and Exchange Commission (Commission), for its Complaint against defendants...»

«EARSeL eProceedings 10, 2/2011 73 ESA DUE PERMAFROST: AN EARTH OBSERVATION (EO) PERMAFROST MONITORING SYSTEM Birgit Heim1, Annett Bartsch2, Kirsten Elger1, Hugues Lantuit1, Julia Boike1, Sina Muster1, Moritz Langer1, Claude Duguay3, Sonia Hachem3, Aiman Soliman3, Christoph Paulik2, Tazzio Strozzi4, and Frank-Martin Seifert5 1. Alfred Wegener Institute for Polar and Marine Research, Potsdam, Germany; {birgit.heim / kirsten.elger / julia.boike / hugues.lantuit / sina.muster / moritz.langer}...»

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