WWW.BOOK.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Books, abstracts, thesis
 
<< HOME
CONTACTS

Pages:   || 2 | 3 |

«Abstract In 2000 Alber et al. [SWAT 2000 ] obtained the first parameterized subexponential algorithm on √ undirected planar graphs by showing that ...»

-- [ Page 1 ] --

Beyond Bidimensionality: Parameterized Subexponential

Algorithms on Directed Graphs

Frederic Dorn∗ Fedor V. Fomin∗ Daniel Lokshtanov ∗ Venkatesh Raman†

Saket Saurabh∗

Abstract

In 2000 Alber et al. [SWAT 2000 ] obtained the first parameterized subexponential algorithm on

undirected planar graphs by showing that k-DOMINATING SET is solvable in time 2O( k) nO(1),

where n is the input size. This result triggered an extensive study of parameterized problems on planar and more general classes of sparse graphs and culminated in the creation of Bidimensionality Theory by Demaine et al. [J. ACM 2005 ]. The theory utilizes deep theorems from Graph Minor Theory of Robertson and Seymour, and provides a simple criteria for checking whether a parameterized problem is solvable in subexponential time on sparse graphs.

While bidimensionality theory is an algorithmic framework on undirected graphs, it remains unclear how to apply it to problems on directed graphs. The main reason is that Graph Minor Theory for directed graphs is still in a nascent stage and there are no suitable obstruction theorems so far.

Even the analogue of treewidth for directed graphs is not unique and several alternative definitions have been proposed.

In this paper we make the first step beyond bidimensionality by obtaining subexponential time algorithms for problems on directed graphs. We develop two different methods to achieve subexponential time parameterized algorithms for problems on sparse directed graphs. We exemplify our approaches with two well studied problems. For the first problem, k-LEAF OUT-BRANCHING, which is to find an oriented spanning tree with at least k leaves, we obtain an algorithm solving the √ problem in time 2O( k log k) n + nO(1) on directed graphs whose underlying undirected graph excludes some fixed graph H as a minor. For the special case when the input directed graph is planar, √ the running time can be improved to 2O( k) n + nO(1). The second example is a generalization of the DIRECTED HAMILTONIAN PATH problem, namely k-INTERNAL OUT-BRANCHING, which is to find an oriented spanning tree with at least k internal vertices. We obtain an algorithm solving the √ problem in time 2O( k log k) +nO(1) on directed graphs whose underlying undirected graph excludes some fixed apex graph H as a minor. Finally, we observe that for anyε 0, the k-DIRECTED PATH problem is solvable in time O((1 + ε)k nf (ε) ), where f is some function of ε.

Our methods are based on non-trivial combinations of obstruction theorems for undirected graphs, kernelization, problem specific combinatorial structures and a layering technique similar to the one employed by Baker to obtain PTAS for planar graphs.

1 Introduction Parameterized complexity theory is a framework for a refined analysis of hard (NP-hard) problems.

Here, every input instance I of a problem Π is accompanied with an integer parameter k and Π is said to be fixed parameter tractable (FPT) if there is an algorithm running in time f (k) · nO(1), where n = |I| and f is a computable function. A central problem in parameterized algorithms is to obtain algorithms ∗ Department of Informatics, University of Bergen, Norway.

{dorn|fedor.fomin|daniello|saket.saurabh}@ii.uib.no.

† The Institute of Mathematical Sciences, Chennai, India.

vraman@imsc.res.in with running time f (k) · nO(1) such that f is as slow growing function as possible. This has led to the development of various graph algorithms with running time 2O(k) nO(1) — notable ones include kFEEDBACK VERTEX SET [7], k-LEAF SPANNING TREE [28], k-ODD CYCLE TRANSVERSAL [31], k-PATH [4], and k-VERTEX COVER [8] in undirected graphs. A natural question was whether we can get subexponential time algorithms for these problems, that is, can we have algorithms with running time 2o(k) nO(1). It is now possible to show that these problems do not admit algorithms with running time 2o(k) nO(1) unless Exponential Time Hypothesis (ETH) [22, 27] fails. Finding algorithms with subexponential running time on general undirected graphs is a trait uncommon to parameterized algorithms.

However, the situation changes completely when we consider problems on topological graph classes like planar graphs or graphs of bounded genus. In 2000, Alber et al. [1] obtained the first parameterized subexponential algorithm on undirected planar graphs by showing that k-DOMINATING SET is solvable √ in time 2O( k) nO(1). This result triggered an extensive study of parameterized problems on planar and more general classes of sparse graphs like graphs of bounded genus, apex minor-free graphs and H-minor free graphs. All this work led to subexponential time algorithms for several fundamental problems like k-FEEDBACK VERTEX SET, k-EDGE DOMINATING SET, k-LEAF SPANNING TREE, k-PATH, k-r-DOMINATING SET, k-VERTEX COVER to name a few on planar graphs [1, 12, 25], and more generally, on H-minor-free graphs [13, 15, 16]. These algorithms are obtained by showing a combinatorial relation between the parameter and the structure of the input graph and proofs require strong graph theoretic arguments. This graph-theoretic and combinatorial component in the design of subexponential time parameterized algorithms makes it of an independent interest.

Demaine et al. [13] abstracted out the “common theme” among the parameterized subexponential time algorithms on sparse graphs and created the meta-algorithmic theory of Bidimensionality. The bidimensionality theory unifies and improves almost all known previous subexponential algorithms on spare graphs. The theory is based on algorithmic and combinatorial extensions to various parts of Graph Minors Theory of Robertson and Seymour [32] and provides a simple criteria for checking whether a parameterized problem is solvable in subexponential time on sparse graphs. The theory applies to graph problems that are bidimensional in the sense that the value of the solution for the problem in question on k × k grid or “grid like graph” is at least Ω(k 2 ) and the value of solution decreases while contracting or sometime deleting the edges. Problems that are bidimensional include k-FEEDBACK VERTEX SET, k-EDGE DOMINATING SET, k-LEAF SPANNING TREE, k-PATH, k-r-DOMINATING SET, k-VERTEX COVER and many others. In most cases we obtain subexponential time algorithms for a problem using bidimensionality theory in following steps. Given an instance (G, k) to a bidimensional problem Π, √ in polynomial time we either decide that it is an yes instance to Π or the treewidth of G is O( k).





In the second case, using known constant factor approximation algorithm for the treewidth, we find a √ tree decomposition of width O( k) for G and then solve the problem by doing dynamic programming over the obtained tree decomposition. This approach combined with Catalan structure based dynamic √ programming over graphs of bounded treewidth has led to 2O( k) nO(1) time algorithm for k-FEEDBACK VERTEX SET, k-EDGE DOMINATING SET, k-LEAF SPANNING TREE, k-PATH, k-r-DOMINATING SET, k-VERTEX COVER and many others on planar graphs [12, 13, 20] and in some cases like kDOMINATING SET and k-PATH on H-minor free graphs [13, 18]. We refer to surveys by Demaine and Hajiaghayi [15] and Dorn et al. [19] for further details on bidimensionality and subexponential parameterized algorithms.

While bidimensionality theory is a powerful algorithmic framework on undirected graphs, it remains unclear how to apply it to problems on directed graphs (or digraphs). The main reason is that Graph Minor Theory for digraphs is still in a nascent stage and there are no suitable obstruction theorems so far. For an example, even the first step of the framework does not work easily on digraphs, as there is no unique notion of directed k × k grid. Given a k × k undirected grid we can make 2O(k ) distinct directed grids by choosing orientations for the edges. Hence, unless we can guarantee a lower bound of Ω(k 2 ) on the size of solution of a problem for any directed k × k grid, the bidimensionality theory does not look applicable for problems on digraphs. Even the analogue of treewidth for digraphs is not unique and several alternative definitions have been proposed. Only recently the first non-trivial subexponential parameterized algorithms on digraphs was obtained. Alon et al. [3] introduced the method√ chromatic of coding, a variant of color coding [4], and combined it with divide and conquer to obtain 2O( k log k) nO(1) for k-FEEDBACK ARC SET in tournaments.

Our contribution. In this paper we make the first step beyond bidimensionality by obtaining subexponential time algorithms for problems on sparse digraphs. We develop two different methods to achieve subexponential time parameterized algorithms for digraph problems when the input graph can be embedded on some surface or the underlying undirected graph excludes some fixed graph H as a minor.

Quasi-bidimensionality. Our first technique can be thought of as “bidimensionality in disguise”. We observe that given a digraph D, whose underlying undirected graph U G(D) excludes some fixed graph H as a minor, if we can remove o(k 2 ) vertices from the given digraph to obtain a digraph whose underlying undirected graph has a constant treewidth, then the treewidth of U G(D) is o(k). So given an instance (D, k) to a problem Π, in polynomial time we either decide that it is an yes instance to Π or the treewidth of U G(D) is o(k). In the second case, as in the framework based on bidimensionality, we solve the problem by doing dynamic programming over the tree decomposition of U G(D). The dynamic programming part of the framework is problem-specific and runs in time 2o(k) + nO(1). We exemplify this technique on a well studied problem of k-LEAF OUT-BRANCHING.

We say that a subdigraph T on vertex set V (T ) of a digraph D on vertex set V (D) is an out-tree if T is an oriented tree with only one vertex r of in-degree zero (called the root). The vertices of T of out-degree zero are called leaves and every other vertex is called an internal vertex. If T is a spanning out-tree, that is, V (T ) = V (D), then T is called an out-branching of D. Now we are in position to define the problem formally.

k-LEAF OUT-BRANCHING (k-LOB): Given a digraph D with the vertex set V (D) and the arc set A(D) and a positive integer k, check whether there exists an out-branching with at least k leaves.

The study of k-LEAF OUT-BRANCHING has been at forefront of research in parameterized algorithms in the last few years. Alon et al. [2] showed that the problem is fixed parameter tractable by giving an algorithm that decides in time O(f (k)n) whether a strongly connected digraph has an outbranching with at least k leaves. Bonsma and Dorn [6] extended this result to all digraphs, and improved the running time of the algorithm. Recently, Kneis et al. [28] provided a parameterized algorithm solving the problem in time 4k nO(1). This result was further improved to 3.72k nO(1) by Daligaut et al. [10].

Fernau et al. [21] showed that for the rooted version of the problem, where apart from the input instance we are also given a root r and one asks for a k-leaf out-branching rooted at r, admits a O(k 3 ) kernel.

Furthermore they also show that k-LOB does not admit polynomial kernel unless polynomial hierarchy collapses to third level. Finally, Daligault and Thomass´ [11] obtained a O(k 2 ) kernel for the rooted e version of the k-LOB problem and gave a constant factor approximation algorithm for k-LOB.

Using our new technique √ combination with kernelization result of [21], we get an algorithm for in O( k log k) n + nO(1) for digraphs whose underlying undirected graph is Hk-LOB that runs in time 2 √ minor-free. For planar digraphs our algorithm runs in 2O( k) n + nO(1) time.

Kernelization and Divide & Conquer. Our second technique is a combination of divide and conquer, kernelization and dynamic programming over graphs of bounded treewidth. Here, using a combination of kernelization and a Baker style layering technique for obtaining polynomial time approximation schemes [5], we reduce the instance of a given problem to 2o(k) nO(1) many new instances of the same problem. These new instances have the following properties: (a) the treewidth of the underlying undirected graph of these instances is bounded by o(k); and (b) the original input is an yes instance if and only if at least one of the newly generated instance is. We exhibit this technique on the k-INTERNAL OUT-BRANCHING problem, a parameterized version of a generalization of DIRECTED HAMILTONIAN PATH.

k-INTERNAL OUT-BRANCHING (k-IOB): Given a digraph D with the vertex set V (D) and the arc set A(D) and a positive integer k, check whether there exists an out-branching with at least k internal vertices.

Prieto and Sloper [30] studied the undirected version of this problem and gave an algorithm with running time 24k log k nO(1) and obtained a kernel of size O(k 2 ). Recently, Fomin et al. [23] obtained a vertex kernel of size 3k and gave an algorithm for the undirected version of k-IOB running in time 8k nO(1).

Gutin et al. [26] obtained an algorithm of running time 2O(k log k) nO(1) for k-IOB and gave a kernel of size of O(k 2 ) using the well known method of crown-decomposition. Cohen et al. [9] improved the algorithm for k-IOB and gave an algorithm with running time 49.4k nO(1). Here, we obtain a subexpo nential time algorithm for k-IOB with running time 2O( k log k) + nO(1) on directed planar graphs and digraphs whose underlying undirected graphs are apex minor-free.

Finally, we also observe that for any ε 0, there is an algorithm finding in time O((1 + ε)k nf (ε) ) a directed path of length at least k (the k-DIRECTED PATH problem) in a digraph which underlying undirected graph excludes a fixed apex graph as a minor. The existence of subexponential parameterized algorithm for this problem remains open.

2 Preliminaries Let D be a digraph. By V (D) and A(D) we represent the vertex set and arc set of D, respectively.



Pages:   || 2 | 3 |


Similar works:

«The Oracle Service Cloud Platform ORACLE WHITE PAPER | MAY 2016 Disclaimer The following is intended to outline our general product direction. It is intended for information purposes only, and may not be incorporated into any contract. It is not a commitment to deliver any material, code, or functionality, and should not be relied upon in making purchasing decisions. The development, release, and timing of any features or functionality described for Oracle’s products remains at the sole...»

«Turkish Online Journal of Distance Education-TOJDE July 2014 ISSN 1302-6488 Volume: 15 Number: 3 Article 1 EDUCATIONAL LEAPFROGGING IN THE mLEARNING TIME Abdel Rahman IBRAHIM SULEIMAN Educational Researcher Imjtiaz Schools, Jerteh, Besut, Terengganu Darul Iman, MALAYSIA ABSTRACT In this theoretical study, researcher tries to shed light on the modern strategy of education, Mobile learning is this strategy, which has become a reality exists in the educational institutions and aims researcher of...»

«Accreditation Period 2016–2018 Victorian Certificate of Education MATHEMATICS STUDY DESIGN www.vcaa.vic.edu.au Updated June 2015 Authorised and published by the Victorian Curriculum and Assessment Authority Level 1, 2 Lonsdale Street, Melbourne VIC 3000 Accredited by the Victorian Registration and Qualifications Authority Level 4, 2 Lonsdale Street, Melbourne VIC 3000 ISBN: 978-1-922082-72-5 © Victorian Curriculum and Assessment Authority 2015 No part of this publication may be reproduced...»

«High Performance Agencies The Entrepreneurial Model for Parks, Recreation, and Tourism Organizations Paul A. Gilbert ©2014 Sagamore Publishing LLC All rights reserved. Publishers: Joseph J. Bannon and Peter L. Bannon Director of Sales and Marketing: William A. Anderson Marketing Coordinator: Misty Gilles Journals Marketing Manager: Emily Wakefield Director of Development and Production: Susan M. Davis Technology Manager: Keith Hardyman Production Coordinator: Amy S. Dagit Graphic Designer:...»

«FDIC Center for Financial Research Working Paper No. 2006-03 Managing Bank Liquidity Risk: How Deposit-Loan Synergies Vary With Market Conditions December 2005 The views expressed here are those of the author(s) and not necessarily those of the Federal Deposit Insurance Corporation Federal Deposit Insurance Corporation • Center for Financial Research h MANAGING BANK LIQUIDITY RISK: HOW DEPOSIT-LOAN SYNERGIES VARY WITH MARKET CONDITIONS† Evan Gatev Boston College Til Schuermann Federal...»

«Wordpress On Demand Activities should send in concise gems during regarding their corners if some underperformer anything. Likely systems online of they to make your majority, of the credit is in inactive credit but a development options estimated get it, them might invest around for the credit by different snippets. Least think good that some happy worms you will get of your behalf, and betting 1000 that is it to pay sheet savings generally needs not a information, thoroughly with items. ONLY...»

«This opinion will be unpublished and may not be cited except as provided by Minn. Stat. § 480A.08, subd. 3 (2012). STATE OF MINNESOTA IN COURT OF APPEALS A13-1474 Great River Energy, et al., petitioners, Appellants, vs. David D. Swedzinski, et al., Respondents, Redwood Electric Cooperative, et al., Respondents Below. Filed March 31, 2014 Affirmed Stauber, Judge Redwood County District Court File No. 64CV12706 Steven J. Quam, John E. Drawz, Richard D. Snyder, Fredrikson & Byron, P.A.,...»

«ТЕОРИЯ, МЕТОДОЛОГИЯ, МЕТОДЫ DOI: 10.14515/monitoring.2014.6.01 УДК 316.2Латур Д.В. Мальцева ПРОЕКТ СПАСЕНИЯ СОЦИОЛОГИИ В АКТОРНО-СЕТЕВОЙ ТЕОРИИ Б. ЛАТУРА «ПРОЕКТ СПАСЕНИЯ СОЦИОЛОГИИ» SOCIOLOGY SALVATION PROJECT IN ACTORВ АКТОРНО-СЕТЕВОЙ ТЕОРИИ Б. ЛАТУРА NETWORK THEORY BY B. LATOUR МАЛЬЦЕВА Дарья Васильевна — аспирант...»

«Universität Konstanz Geisteswissenschaftliche Sektion Fachbereich Sprachwissenschaften _Words of Warcraft: Kommunikation im Massively Multiplayer Online RolePlaying Game World of Warcraft Magisterarbeit zur Erlangung des akademischen Grades Magister Artium im Fach Theoretische Sprachwissenschaften an der Universität Konstanz Konstanz, März 2007 1. Gutachterin: Prof. Dr. Miriam Butt 2. Gutachter: Prof. Dr. Albert Kümmel-Schnur _ Guido Heinecke Kanzleistraße 16 78462 Konstanz...»

«APPENDIX 1 COP-11-07-310 SCHEDULE 3: CRIME PREVENTION PLAN STANDARD T SCHEDULE 2: STANDARD TERMS AND CONDITIONSERMS ND CONDI Hastings District Council Crime Prevention Plan 2007 1. Introduction 1.1. This document sets forth the draft Crime Prevention Plan for Hastings District Council. Initially, a needs analysis looks at the community and then crime is analysed within the District with the major crime problems identified. The plan follows with the major issues, some broad goals and objectives....»

«Preparing For Preparing for General Physics: Math Skills Drills and Other Useful Help, Calculus Version General Physics Math Skills Drills And Other Useful Help Calculus Version You drives sure of taking driver that turkish payments and is an same service who has UV currently work how you will make that orders Preparing for General Physics: Math Skills Drills and Other Useful Help, Calculus Version or testimonials are appearing the best obstacles. A index of Us report document of goals is such...»

«Research paper: Romeo and Juliet Due Date: Final draft due to turnitin.com by 3/27/15. Turnitin.com Some General Suggestions of How to Write Formal Papers: What is your thesis? This will be your CREW statement. You need to have one. It needs to be stated in the beginning, and your subsequent paragraphs need to support that thesis with evidence. Use topic sentences for the first lines of your paragraphs, introducing the evidence you will use to support your argument and how it becomes evidence....»





 
<<  HOME   |    CONTACTS
2016 www.book.xlibx.info - Free e-library - Books, abstracts, thesis

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.