检索结果-内蒙古大学图书馆

parameterized COMPLEXITY OF DIRECTED STEINER TREE ON SPARSE GRAPHS

SIAM JOURNAL ON DISCRETE MATHEMATICS 2017年第2期31卷 1294-1327页

作者： Jones, Mark Lokshtanov, Daniel Ramanujan, M. S. Saurabh, Saket Suchy, Ondrej Royal Holloway Univ London Dept Comp Sci Egham TW20 0EX Surrey England Univ Bergen N-5020 Bergen Norway Inst Math Sci Madras 600113 Tamil Nadu India Czech Tech Univ Fac Informat Technol Prague 16636 Czech Republic

We study the parameterized complexity of the directed variant of the classical STEINER TREE problem on various classes of directed sparse graphs. While the parameterized complexity of STEINER TREE parameterized by the number of terminals is well understood, not much is known about the parameterization by the number of nonterminals in the solution tree. All that is known for this parameterization is that both the directed and the undirected versions are W[2]-hard on general graphs and hence unlikely to be fixed parameter tractable (FPT). The undirected STEINER TREE problem becomes FPT when restricted to sparse classes of graphs such as planar graphs, but the techniques used to show this result break down on directed planar graphs. In this article we precisely chart the tractability border for DIRECTED STEINER TREE (DST) on sparse graphs parameterized by the number of nonterminals in the solution tree. Specifically, we show that the problem is FPT on graphs excluding a topological minor but becomes W[2]-hard on graphs of degeneracy 2. On the other hand we show that if the subgraph induced by the terminals is acyclic, then the problem becomes FPT on graphs of bounded degeneracy. We further show that our algorithm achieves the best possible asymptotic running time dependence on the solution size and degeneracy of the input graph, under standard complexity theoretic assumptions. Using the ideas developed for DST, we also obtain improved algorithms for DOMINATING SET on sparse undirected graphs. These algorithms are asymptotically optimal.

关键词： algorithms and data structures graph algorithms parameterized algorithms Steiner tree problem sparse graph classes

来源：评论

学校读者我要写书评

暂无评论

parameterized Complexity of Small Weight Automorphisms 34

Parameterized Complexity of Small Weight Automorphisms

引用

34th Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Arvind, Vikraman Kobler, Johannes Kuhnert, Sebastian Toran, Jacobo Inst Math Sci HBNI Chennai Tamil Nadu India Humboldt Univ Inst Informat Berlin Germany Univ Ulm Inst Theoret Informat Ulm Germany

ISBN: (纸本)9783959770286

We show that checking if a given hypergraph has an automorphism that moves exactly k vertices is fixed parameter tractable, using k and additionally either the maximum hyperedge size or the maximum color class size as parameters. In particular, it suffices to use k as parameter if the hyperedge size is at most polylogarithmic in the size of the given hypergraph. As a building block for our algorithms, we generalize Schweitzer's FPT algorithm [ESA 2011] that, given two graphs on the same vertex set and a parameter k, decides whether there is an isomorphism between the two graphs that moves at most k vertices. We extend this result to hypergraphs, using the maximum hyperedge size as a second parameter. Another key component of our algorithm is an orbit-shrinking technique that preserves permutations that move few points and that may be of independent interest. Applying it to a suitable subgroup of the automorphism group allows us to switch from bounded hyperedge size to bounded color classes in the exactly-k case.

关键词： parameterized algorithms hypergraph isomorphism

来源：评论

学校读者我要写书评

暂无评论

METRIC DIMENSION OF BOUNDED TREE-LENGTH GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2017年第2期31卷 1217-1243页

作者： Belmonte, Remy Fomin, Fedor V. Golovach, Petr A. Ramanujan, M. S. Kyoto Univ Dept Architecture & Architectural Engn Kyoto Japan Univ Bergen Dept Informat Bergen Norway TU Wien A-1040 Vienna Austria

The notion of resolving sets in a graph was introduced by Slater [Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Util. Math., Winnipeg, 1975, pp. 549-559] and Harary and Melter [Ars Combin., 2 (1976), pp. 191-195] as a way of uniquely identifying every vertex in a graph. A set of vertices in a graph is a resolving set if for any pair of vertices x and y there is a vertex in the set which has distinct distances to x and y. A smallest resolving set in a graph is called a metric basis and its size, the metric dimension of the graph. The problem of computing the metric dimension of a graph is a well-known NP-hard problem and while it was known to be polynomial time solvable on trees, it is only recently that efforts have been made to understand its computational complexity on various restricted graph classes. In recent work, Foucaud [Algorithmica, 2016, pp. 1-31] showed that this problem is NP-complete even on interval graphs. They complemented this result by also showing that it is fixed-parameter tractable (FPT) parameterized by the metric dimension of the graph. In this work, we show that this FPT result can in fact be extended to all graphs of bounded tree-length. This includes well-known classes like chordal graphs, AT-free graphs, and permutation graphs. We also show that this problem is FPT parameterized by the modular-width of the input graph.

关键词： algorithms and data structures graph algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

HITTING SELECTED (ODD) CYCLES

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2017年第3期31卷 1581-1615页

作者： Lokshtanov, Daniel Misra, Pranabendu Ramanujan, M. S. Saurabh, Saket Univ Bergen Bergen Norway HBNI Inst Math Sci Madras Tamil Nadu India TU Wien Algorithms & Complex Grp Vienna Austria

In the Subset Odd Cycle Transversal (Subset OCT) problem, the input is a graph G, a subset of vertices T and a positive integer k and the objective is to determine whether there exists a k-sized vertex subset that intersects every odd cycle containing a vertex from T. Clearly, Subset OCT is a generalization of the classic Odd Cycle Transversal problem where the objective is to determine whether there exists a k-sized vertex subset that intersects every odd cycle in the given graph. We remark that Subset OCT also generalizes the well known Multiway Cut problem, as well as a parity constrained variant, the Odd Multiway Cut problem. Recently, Kakimura, Kawarabayashi, and Kobayashi [Proceedings of SODA, 2012, pp. 1726-1736] proposed a fixed parameter tractable (FPT) algorithm for this problem that runs in time f(k)mn(3) using the theory of graph minors, where f is some function, and n and m denote the number of vertices and edges in the graph. However, the dependence of this function on k is at least triple exponential. In this paper, we give the first FPT algorithm for this problem where the exponential dependence of the running time of the algorithm on k is polynomial. Our algorithm avoids the use of the theory of graph minors, is self contained, and runs in time 2(O(k3) (log k))mn(2)log(2) n, thus improving upon the algorithm of Kakimura and co-authors with respect to both the parameter as well as the input size. Our algorithm utilizes a recursive application of generalized important separators to reduce the subset version of this problem to the standard version of the problem.

关键词： important separators sequence odd cycle transversal graph separation problems parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithms for Minimum Fill-in

引用

ALGORITHMICA 2011年第4期61卷 817-838页

作者： Bodlaender, Hans L. Heggernes, Pinar Villanger, Yngve Univ Bergen Dept Informat N-5020 Bergen Norway Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands

We present two parameterized algorithms for the MINIMUM FILL-IN problem, also known as CHORDAL COMPLETION: given an arbitrary graph G and integer k, can we add at most k edges to G to obtain a chordal graph? Our first algorithm has running time O(k(2)nm + 3.0793(k)), and requires polynomial space. This improves the base of the exponential part of the best known parameterized algorithm time for this problem so far. We are able to improve this running time even further, at the cost of more space. Our second algorithm has running time O(k(2)nm + 2.35965(k)) and requires O*(1.7549(k)) space. To achieve these results, we present a new lemma describing the edges that can safely be added to achieve a chordal completion with the minimum number of edges, regardless of k.

关键词： Minimum Fill-in parameterized algorithms Chordal graphs Fixed parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Answer Set Solving with Bounded Treewidth Revisited 14th

Answer Set Solving with Bounded Treewidth Revisited

引用

14th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR)

作者： Fichte, Johannes K. Hecher, Markus Morak, Michael Woltran, Stefan TU Wien Inst Informat Syst Vienna Austria

ISBN: (纸本)9783319616605;9783319616599

parameterized algorithms are a way to solve hard problems more efficiently, given that a specific parameter of the input is small. In this paper, we apply this idea to the field of answer set programming (ASP). To this end, we propose two kinds of graph representations of programs to exploit their treewidth as a parameter. Treewidth roughly measures to which extent the internal structure of a program resembles a tree. Our main contribution is the design of parameterized dynamic programming algorithms, which run in linear time if the treewidth and weights of the given program are bounded. Compared to previous work, our algorithms handle the full syntax of ASP. Finally, we report on an empirical evaluation that shows good runtime behaviour for benchmark instances of low treewidth, especially for counting answer sets.

关键词： parameterized algorithms Tree decompositions

来源：评论

学校读者我要写书评

暂无评论

Finding Even Cycles Faster via Capped k-Walks 2017

Finding Even Cycles Faster via Capped <i>k</i>-Walks

引用

49th Annual ACM-SIGACT Symposium on Theory of Computing (STOC)

作者： Dahlgaard, Soren Knudsen, Mathias Baek Tejs Stoeckel, Morten Univ Copenhagen Copenhagen Denmark

ISBN: (纸本)9781450345286

Finding cycles in graphs is a fundamental problem in algorithmic graph theory. In this paper, we consider the problem of finding and reporting a cycle of length 2k in an undirected graph G with n nodes and m edges for constant k >= 2. A classic result by Bondy and Simonovits [J. Combinatorial Theory, 1974] implies that if m >= 100kn(1+1/k), then G contains a 2k-cycle, further implying that one needs to consider only graphs with m = O(n(1+1/k)). Previously the best known algorithms were an O(n(2)) algorithm due to Yuster and Zwick [J. Discrete Math 1997] as well as a O(m(2)-((1+[k/2]-1)/(k+1))) algorithm by Alon et. al. [Algorithmica 1997]. We present an algorithm that uses O(m(2k/(k+1))) time and finds a 2k-cycle if one exists. This bound is O(n(2)) exactly when m = Theta(n(1+1/k)). When finding 4-cycles our new bound coincides with Alon et. al., while for every k > 2 our new bound yields a polynomial improvement in m. Yuster and Zwick noted that it is "plausible to conjecture that O(n(2)) is the best possible bound in terms of n". We show "conditional optimality": if this hypothesis holds then our O(m(2k/(k+1))) algorithm is tight as well. Furthermore, a folklore reduction implies that no combinatorial algorithm can determine if a graph contains a 6-cycle in time O(m(3/2-epsilon)) for any epsilon > 0 unless boolean matrix multiplication can be solved combinatorially in time O(n(3-epsilon')) for some epsilon' > 0, which is widely believed to be false. Coupled with our main result, this gives tight bounds for finding 6-cycles combinatorially and also separates the complexity of finding 4- and 6-cycles giving evidence that the exponent of m in the running time should indeed increase with k. The key ingredient in our algorithm is a new notion of capped k-walks, which are walks of length k that visit only nodes according to a fixed ordering. Our main technical contribution is an involved analysis proving several properties of such walks which may be of independent inter

关键词： Graph algorithms Cycles parameterized algorithms graph walks capped walks conditional lower bounds

来源：评论

学校读者我要写书评

暂无评论

Constructing a Consensus Phylogeny from a Leaf-Removal Distance (Extended Abstract) 1

引用

24th International Symposium on String Processing and Information Retrieval (SPIRE)

作者： Chauve, Cedric Jones, Mark Lafond, Manuel Scornavacca, Celine Weller, Mathias Simon Fraser Univ Dept Math Burnaby BC Canada Delft Univ Technol Delft Inst Appl Math POB 5 NL-2600 AA Delft Netherlands Univ Ottawa Dept Math & Stat Ottawa ON Canada Univ Montpellier CNRS EPHE Inst Sci EvolutIRD Montpellier France Univ Montpellier Lab Informat Robot & Microelect Montpellier IBC Montpellier France

ISBN: (数字)9783319674285

ISBN: (纸本)9783319674285;9783319674278

Understanding the evolution of a set of genes or species is a fundamental problem in evolutionary biology. The problem we study here takes as input a set of trees describing possibly discordant evolutionary scenarios for a given set of genes or species, and aims at finding a single tree that minimizes the leaf-removal distance to the input trees. This problem is a specific instance of the general consensus/super-tree problem, widely used to combine or summarize discordant evolutionary trees. The problem we introduce is specifically tailored to address the case of discrepancies between the input trees due to the misplacement of individual taxa. Most supertree or consensus tree problems are computationally intractable, and we show that the problem we introduce is also NP-hard. We provide tractability results in form of a 2-approximation algorithm and a parameterized algorithm with respect to the number of removed leaves. We also introduce a variant that minimizes the maximum number d of leaves that are removed from any input tree, and provide a parameterized algorithm for this problem with parameter d.

关键词： Computational biology Phylogenetics parameterized algorithms Approximation Consensus trees Leaf deletion

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithms for Minimum Fill-in

引用

19th Annual International Symposium on algorithms and Computation (ISAAC)

作者： Bodlaender, Hans L. Heggernes, Pinar Villanger, Yngve Univ Bergen Dept Informat N-5020 Bergen Norway Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands

ISBN: (纸本)3540921818

关键词： Minimum Fill-in parameterized algorithms Chordal graphs Fixed parameter tractability

来源：评论

学校读者我要写书评

暂无评论

parameterized tractability of the maximum-duo preservation string mapping problem

引用

THEORETICAL COMPUTER SCIENCE 2016年第0期646卷 16-25页

作者： Beretta, Stefano Castelli, Mauro Dondi, Riccardo CNR Ist Tecnol Biomed Segrate Italy Univ Milano Bicocca Dipartimento Informat Sistemist & Comunicaz Milan Italy Univ Nova Lisboa NOVA IMS Lisbon Portugal Univ Bergamo Dipartimento Lettere Filosofia & Comunicaz Bergamo Italy

In this paper we investigate the parameterized complexity of the Maximum-Duo Preservation String Mapping Problem, the complementary of the Minimum Common String Partition Problem. We show that this problem is fixed-parameter tractable when parameterized by the number k of conserved duos, by first giving a parameterized algorithm based on the color-coding technique and then presenting a reduction to a kernel of size O (k(6)). (C) 2016 Elsevier B.V. All rights reserved.

关键词： Computational biology Common string partition parameterized algorithms Kernelization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：