FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 |   ...   | 5 | 6 ||

«Fixed-parameter tractability of multicut parameterized by the size of the cutset∗ D´niel Marx† Igor Razgon‡ a August 27, 2013 Abstract Given ...»

-- [ Page 7 ] --

Acknowledgement We would like to thank the reviewers for the insightful comments that have helped us to fix a number of errors and improve readability.

References [1] S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):1–37, 2009.

[2] N. Bansal, A. Blum, and S. Chawla. Correlation clustering. Machine Learning, 56(1-3):89–113, 2004.

[3] H. L. Bodlaender, M. R. Fellows, P. Heggernes, F. Mancini, C. Papadopoulos, and F. A. Rosamond. Clustering with partial information. Theor. Comput. Sci., 411(7-9):1202–1211, 2010.

–  –  –

[5] N. Bousquet, J. Daligault, S. Thomasse, and A. Yeo. A polynomial kernel for multicut in trees.

In STACS, pages 183–194, 2009.

[6] G. Calinescu, C. G. Fernandes, and B. Reed. Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width. Journal of Algorithms, 48(2):333 – 359, 2003.

[7] S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. Comput. Complexity, 15(2):94–114, 2006.

[8] J. Chen, Y. Liu, and S. Lu. An improved parameterized algorithm for the minimum node multiway cut problem. Algorithmica, 55(1):1–13, 2009.

[9] J. Chen, Y. Liu, S. Lu, B. O’Sullivan, and I. Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM, 55(5), 2008.

[10] R. Chitnis, L. Egri, and D. Marx. List H-coloring a graph by removing few vertices. To appear in proceedings of ESA 2013.

[11] R. Chitnis, M. Hajiaghayi, and D. Marx. Fixed-parameter tractability of Directed Multiway Cut parameterized by the size of the cutset. To appear in SIAM Journal on Computing.

[12] R. H. Chitnis, M. Cygan, M. T. Hajiaghayi, and D. Marx. Directed Subset Feedback Vertex Set is fixed-parameter tractable. In ICALP (1), pages 230–241, 2012.

[13] J. Chuzhoy and S. Khanna. Polynomial flow-cut gaps and hardness of directed cut problems.

J. ACM, 56(2):1–28, 2009.

[14] M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk. On multiway cut parameterized above lower bounds. TOCT, 5(1):3, 2013.

[15] E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity of multiterminal cuts. SIAM J. Comput., 23(4):864–894, 1994.

[16] E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica. Correlation clustering in general weighted graphs. Theor. Comput. Sci., 361(2-3):172–187, 2006.

[17] R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer, New York, 1999.

[18] U. Feige, M. Hajiaghayi, and J. R. Lee. Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput., 38(2):629–657, 2008.

[19] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, Berlin, 2006.

[20] L. R. Ford, Jr. and D. R. Fulkerson. Maximal flow through a network. Canad. J. Math., 8:399–404, 1956.

[21] L. R. Ford, Jr. and D. R. Fulkerson. Flows in networks. Princeton University Press, Princeton, N.J., 1962.

[22] N. Garg, V. V. Vazirani, and M. Yannakakis. Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput., 25(2):235–251, 1996.

[23] G. Gottlob and S. T. Lee. A logical approach to multicut problems. Inf. Process. Lett., 103(4):136–141, 2007.

[24] S. Guillemot. FPT algorithms for path-transversal and cycle-transversal problems. Discrete Optimization, 8(1):61 – 71, 2011.

[25] J. Guo, F. H¨ffner, E. Kenar, R. Niedermeier, and J. Uhlmann. Complexity and exact algou rithms for vertex multicut in interval and bounded treewidth graphs. European J. Oper. Res., 186(2):542–553, 2008.

[26] J. Guo and R. Niedermeier. Fixed-parameter tractability and data reduction for multicut in trees. Networks, 46(3):124–135, 2005.

[27] A. Gupta. Improved results for directed multicut. In SODA, pages 454–455, 2003.

[28] F. H¨ffner, R. Niedermeier, and S. Wernicke. Techniques for practical fixed-parameter algou rithms. The Computer Journal, 51(1):7–25, 2008.

[29] S. Khot. On the power of unique 2-prover 1-round games. In STOC, pages 767–775, 2002.

–  –  –

[31] D. Lokshtanov and D. Marx. Clustering with local restrictions. Inf. Comput., 222:278–292, 2013.

[32] D. Lokshtanov, N. S. Narayanaswamy, V. Raman, M. S. Ramanujan, and S. Saurabh. Faster parameterized algorithms using linear programming. CoRR, abs/1203.0833, 2012.

[33] D. Lokshtanov and M. S. Ramanujan. Parameterized tractability of multiway cut with parity constraints. In ICALP (1), pages 750–761, 2012.

[34] D. Marx. Parameterized graph separation problems. In IWPEC, pages 71–82, 2004.

[35] D. Marx. Parameterized graph separation problems. Theoretical Computer Science, 351(3):394– 406, 2006.

[36] D. Marx and I. Razgon. Constant ratio fixed-parameter approximation of the edge multicut problem. Inf. Process. Lett., 109(20):1161–1166, 2009.

[37] D. Marx and I. Razgon. Fixed-parameter tractability of multicut parameterized by the size of the cutset. In Proceedings of the 43nd ACM Symposium on Theory of Computing, pages 469–478, 2011.

[38] M. Naor, L. J. Schulman, and A. Srinivasan. Splitters and near-optimal derandomization. In FOCS, pages 182–191, 1995.

[39] R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.

[40] R. Pichler, S. R¨mmele, and S. Woltran. Multicut algorithms via tree decompositions. In CIAC, u pages 167–179, 2010.

[41] V. Raman, M. S. Ramanujan, and S. Saurabh. Paths, flowers and vertex cover. In ESA, pages 382–393, 2011.

[42] I. Razgon and B. O’Sullivan. Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci., 75(8):435–450, 2009.

–  –  –

[45] M. Xiao. Algorithms for multiterminal cuts. In CSR, pages 314–325, 2008.

[46] M. Yannakakis, P. C. Kanellakis, S. S. Cosmadakis, and C. H. Papadimitriou. Cutting and partitioning a graph after a fixed pattern. In ICALP, pages 712–722, 1983.

A Important separators

First we state without proof some properties of Definition 3.8 that are easy to see:

Proposition A.1. Let G be a graph, X, Y ⊆ V (G) be two disjoint sets of vertices, and S be an important X − Y separator.

1. For every v ∈ S, the set S \ {v} is an important X − Y separator in G \ v.

2. If S is an X − Y separator for some X ⊃ X, then S is an important X − Y separator.

Proof (of Lemma 3.9). We prove by induction on 2p − λ that there are at most 22p−λ important X − Y separators of size at most p, where λ is the size of the smallest X − Y separator. If λ p, then there is no X − Y separator of size p, and therefore the statement holds if 2p − λ 0. Also, if λ = 0 and p ≥ 0, then there is a unique important X − Y separator of size at most p: the empty set.

If S is an X − Y separator, then we denote by KS the union of every component of G \ S intersecting X. First we show the well-known fact that there is a unique X − Y separator S ∗ of size λ such that KS ∗ is inclusionwise maximal, i.e., we have KS ⊂ KS ∗ for every other X − Y separator S of size λ. Suppose that there are two separators S and S such that KS and KS are incomparable and inclusionwise maximal. Let us define the function γ(Z) = |N (Z)|. It is well-known that γ is submodular, that is, γ(A) + γ(B) ≥ γ(A ∪ B) + γ(A ∩ B) for every A, B ⊆ V (G). In particular, the submodularity of gamma implies that γ(KS ) + γ(KS ) ≥ γ(KS ∪ KS ) + γ(KS ∩ KS ).

≥λ =λ =λ The left hand side is exactly 2λ, while the second term of the right hand side is at least λ (as N (KS ∩ KS ) is an X − Y separator). Therefore, γ(KS ∪ KS ) ≤ λ. This means that N (KS ∪ KS ) is also a minimum X − Y separator, contradicting the maximality of S and S.

Next we show that for every important X − Y separator S, we have KS ∗ ⊆ KS. Suppose this is

not true for some S. We use submodularity again:

γ(KS ∗ ) +γ(KS ) ≥ γ(KS ∗ ∪ KS ) + γ(KS ∗ ∩ KS ).

≥λ =λ By definition, γ(KS ∗ ) = λ, and N (KS ∗ ∩ KS ) is an X − Y separator, hence γ(KS ∗ ∩ KS ) ≥ λ. This means that γ(KS ∗ ∪ KS ) ≤ γ(KS ). However this contradicts the assumption that S is an important X − Y separator: N (KS ∗ ∪ KS ) is an X − Y separator not larger than S, but KS ∗ ∪ KS is a proper superset of KS (as KS ∗ is not a subset of KS by assumption).

We have shown that for every important separator S, the set KS contains KS ∗. Let v ∈ S ∗ be an arbitrary vertex of S ∗ (note that λ 0, hence S ∗ is not empty). An important X − Y separator S of size at most p either contains v or not. If S contains v, then S \ {v} is an important X − Y separator in G \ v of size at most p := p − 1 (Prop. A.1(1)). As v ∈ X, Y, the size λ of the minimum X − Y separator in G \ v is at least λ − 1. Therefore, 2p − λ 2p − λ and the induction hypothesis implies that there are at most 22p −λ ≤ 22p−λ−1 important X − Y separators of size p in G \ {v}, and hence at most that many important X − Y separators of size p in G that contain v.

Let us count now the important X − Y separators not containing v. Note that by the minimality of S ∗, vertex v of S ∗ has a neighbor in KS ∗. We have seen that KS ∗ ⊆ KS for every such X − Y separator S. As v ∈ S and v has a neighbor in KS, even KS ∗ ∪{v} ⊆ KS is true. Let X = KS ∗ ∪{v};

it follows that S is a X − Y separator and in fact an important X − Y separator by Prop. A.1(2).

There is no X − Y separator S of size λ: such a set S would be an X − Y separator of size λ as well, with KS ∗ ∪ {v} ⊆ KS, contradicting the maximality of S ∗. Thus the minimum size λ of an X − Y separator is greater than λ. It follows by the induction assumption that the number of important X − Y separators of size at most p is at most 22p−λ ≤ 22p−λ−1, which is a bound on the number of important X − Y separators of size p in G that does not contain v.

Adding the bounds in the two cases, we get the required bound 22p−λ. An algorithm for enumerating all the at most 4p important separators follows from the above proof. First, we can find a maximum X − Y flow in time O(p(|V (G)| + |E(G)|)) using at most p rounds of the Ford-Fulkerson algorithm. It is well-known that the separator S ∗ in the proof can be deduced from the maximum flow in linear time by finding those vertices from which Y cannot be reached in the residual graph [21]. Pick any arbitrary vertex v ∈ S ∗. Then we branch on whether vertex v ∈ S ∗ is in the important separator or not, and recursively find all possible important separators for both cases. Note that this algorithm enumerates a superset of all important separators: by our analysis above, every important separator is found, but there is no guarantee that all the constructed separators are important.

Therefore, the algorithm has to be followed by a filtering phase where we check for each returned separator whether it is important. Observe that S is an important X − Y separator if and only if S is the unique minimum KS − Y separator, where KS is the set of vertices reachable from X in G \ S. As the size of S is at most p, this can be checked in time O(p(|V (G)| + |E(G)|)) by finding a maximum flow and constructing the residual graph. The search tree has at most 4p leaves and the work to be done in each node is O(p(|V (G)| + |E(G)|)). Therefore, the total running time of the branching algorithms is O(4p · p(|V (G)| + |E(G)|)) and returns at most 4p separators. This is followed by the filtering phase, which takes time O(4p · p(|V (G)| + |E(G)|)).

Pages:     | 1 |   ...   | 5 | 6 ||

Similar works:

«www.ecofem.org/journal Ecofeminism within Gender and Development H. K. Manion Social Work Research Assistant, University of East London It is for the union of you and me that there is light in the sky. it is for the union of you and me that the earth is decked in dusky green. It is for the union of you and me that night sits motionless with the world in her arms; dawn appears opening the eastern door with sweet murmurs in her voice. The boat of hope sails along on the currents of Eternity...»

«PING PONG Help and Manuals Version release/16.12.1 Table of contents Time limited groups 3 Project groups: Trainer 6 Create project groups (as trainer) 9 Log book trainer 16 Toolbox 27 Preferences 29 Activating participants 36 Preferences Logotype 37 Preferences Navigation 38 Preferences Archiving 39 Answer questions 40 Send message 41 Progress 43 Main menu 45 Content 48 Mark free writing 49 Test results 50 Survey results 52 Assignments 57 Ask / Answer questions 61 Discuss 62 Message board 63...»

«A narrative for youth work today: final draft for consultation An education for the 21st century: A narrative for youth work today Why now? There are two reasons why the timing is ideal for a new understanding of the role youth work, alongside formal education, parents, families and wider communities, plays in the personal and social development of young people and equips them with the resources they need to ‘succeed’. Such success we might define as finding a place within the community...»

«BOARD OF GOVERNORS REGULAR MEETING MINUTES MEETING: Monday, February 1, 2016 TIME: 5:00 pm LOCATION: Paul Building, Room 216, Lansdowne Campus BOARD MEMBERS: ADMINISTRATION: Ron Rice, Acting Chair John Boraas, VP Education Sherri Bell, President Deborah Huelscher, Chief Financial Officer Steve Chang Barbara Severyn, Executive Director, Human Resources Cindy Choi Geoff Wilmshurst, VP Partnerships Jennifer Erwin Joan Yates, VP Communications, Advancement & Planning Stefan Fletcher Nigel Giuliany...»

«Release 4 HQ-FOI-01268-12 All emails sent by Richard Windsor were sent by EPA Administrator Lisa Jackson 01268-EPA-6128 Gina McCarthy/DC/USEPA/US To Laura Vaught cc Alcantara.Betsaida@epamail.epa.gov, 12/13/2011 09:09 PM Barron.Alex@epamail.epa.gov, Joel Beauvais, Bob Perciasepe, Brendan Gilfillan, Dru Ealons, Ganesan.Arvin@epamail.epa.gov, Joseph Goffman, Goo.Michael@epamail.epa.gov, Kanninen.Daniel@epamail.epa.gov, Oster.Seth@epamail.epa.gov, Stephanie Owens, Thompson.Diane@epamail.epa.gov,...»

«Vidya Prasarak Mandal's B.N.Bandodkar College of Science.Thane NAAC re-accredited 'A' grade Best College Award (University of Mumbai ) Department of Chemistry and Research Committee National Conference on Phytochemistry: Recent Trends and Challenges December 14th -15th 2012 Venue: Thorle Bajirao Sabhagrah, VPM‟s B.N.Bandodkar College of Science, Thane(W)400 601. Maharashtra Organized By: Department of Chemistry and Research Committee VPM‟s B.N.Bandodkar College of Science, „Jnanadweepa‟...»

«Gestural Structures and Phonological Patterns* Catherine P. Browman and Louis Goldsteint INTRODUCTION In thiS paper, we present a particular view of phonology, one in which lexical items are construed as characterizing the activity of the vocal tract (and its articulators) as a sound-producing system. Central to this characterization is the concept of dynamically defined articulatOl:y gestures. Such gestures are, we argue, useful primitives for characterizing phonological patterns as well as...»

«Lincoln and The Key to Uncle Tom's Cabin By Katherine Kane, Executive Director, Harriet Beecher Stowe Center As featured in Connecticut Explored, Winter 2012/2013 issue President Abraham Lincoln, in office for less than two years and leader of a fractured and war-torn nation, picked up his pen and signed his Emancipation Proclamation New Year’s Day 1863. From Boston to Beaufort, South Carolina, crowds that had been waiting all day erupted excitedly as the news finally came from Washington,...»

«3 GM-group After all the fireworks of round two, round three true enough became a small anti-climax. Both the top boards this morning were drawn without too many exciting moments. Still the four next boards all got a winner, and the remaining three draws all were hard fought and exciting. No player is left with a perfect score after this round, as the Vovk brothers and veteran Rausis are now sharing the lead at 2.5/3. The first board meeting between GM Igors RAUSIS (2600) and GM Andrey VOVK...»

«Spectrum Brands, Inc. ( SPEB ) 601 RAYOVAC DRIVE MADISON, WI, 53711 608−275−3340 www.spectrumbrands.com 10−K Annual report pursuant to section 13 and 15(d) Filed on 12/29/2009 Filed Period 9/30/2009 Table of Contents Index to Financial Statements UNITED STATES SECURITIES AND EXCHANGE COMMISSION Washington, D.C. 20549 FORM 10−K ANNUAL REPORT PURSUANT TO SECTION 13 OR 15(d) OF THE SECURITIES EXCHANGE ACT OF 1934 For the Fiscal Year Ended September 30, 2009. OR TRANSITION REPORT PURSUANT...»

«The Early Years Foundation Stage (EYFS) Review Report on the Evidence � March 2011 � Contents � Introduction 2 Chapter1:Theearlyyears 4 Chapter2:Afairandflexibleframework 12 Chapter3:Enjoying,learninganddeveloping 19 Chapter4:Assessingchildren’sprogress 30 Chapter5:Safe,happy,healthychildren 40 Chapter6:Theearlyyearssystem 51 Introduction This review of the Early Years Foundation Stage (EYFS) has gathered evidence from a wide range of people working...»

«Wilson Bull., 105(3), 1993, pp. 497-503 TROPHIC NICHE OF NEARCTIC SHORT-EARED OWLS DENVER W. HOLT’ AssTticr.-The trophic niche of Short-eared Owls (Asiojlammeus) was analyzed using nine Nearctic studies reporting 500 prey items each. Of 20,416 prey items, 4136 were from the breeding and 16,280 from the non-breeding seasons. The owls preyed upon at least 62 species from four classes of animals. Mammals constituted 95% of prey from all but two sites. Food-niche breadth ranged from 1.23 to 5.20...»

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