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

parameterized Complexity of the Spanning Tree Congestion Problem

ALGORITHMICA 2012年第1期64卷 85-111页

作者： Bodlaender, Hans L. Fomin, Fedor V. Golovach, Petr A. Otachi, Yota van Leeuwen, Erik Jan Univ Bergen Dept Informat N-5020 Bergen Norway Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class of graphs containing planar graphs, graphs of bounded treewidth, and graphs of bounded genus, the problem to determine whether a given graph has spanning tree congestion at most k can be solved in linear time for every fixed k. We also show that for every fixed k and d the problem is solvable in linear time for graphs of degree at most d. In contrast, if we allow only one vertex of unbounded degree, the problem immediately becomes NP-complete for any fixed ka parts per thousand yen8. Moreover, the hardness result holds for graphs excluding the complete graph on 6 vertices as a minor. We also observe that for ka parts per thousand currency sign3 the problem becomes polynomially time solvable.

关键词： Spanning tree congestion Graph minor parameterized algorithms Apex graph

来源：评论

学校读者我要写书评

暂无评论

Faster Exact and parameterized Algorithm for Feedback Vertex Set in Tournaments 33

Faster Exact and Parameterized Algorithm for Feedback Vertex...

引用

33rd Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Kumar, Mithilesh Lokshtanov, Daniel Univ Bergen Dept Informat Bergen Norway

ISBN: (纸本)9783959770019

A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T - S is acyclic. In this article we consider the FEEDBACK VERTEX SET problem in tournaments. Here the input is a tournament T and an integer k, and the task is to determine whether T has a feedback vertex set of size at most k. We give a new algorithm for FEEDBACK VERTEX SET IN TOURNAMENTS. The running time of our algorithm is upper-bounded by O(1.6181(k) + n(O(1))) and by O(1.466(n)). Thus our algorithm simultaneously improves over the fastest known parameterized algorithm for the problem by Dom et al. running in time O(2(k)k(O(1)) + n(O(1))), and the fastest known exact exponential-time algorithm by Gaspers and Mnich with running time O(1.674(n)). On the way to proving our main result we prove a strengthening of a special case of a graph partitioning theorem due to Bollobas and Scott. In particular we show that the vertices of any undirected m-edge graph of maximum degree d can be colored white or black in such a way that for each of the two colors, the number of edges with both endpoints of that color is between m/4 - d/2 and m/4+d/2.

关键词： parameterized algorithms Exact algorithms Feedback vertex set Tournaments Graph partitions

来源：评论

学校读者我要写书评

暂无评论

parameterized Domination in Circle Graphs

Parameterized Domination in Circle Graphs

引用

38th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Bousquet, Nicolas Goncalves, Daniel Mertzios, George B. Paul, Christophe Sau, Ignasi Thomasse, Stephan LIRMM CNRS AlGCo Project Team Montpellier France Univ Durham Sch Engn & Comp Sci Durham DH1 3HP England UCBL Lab LIP U Lyon CNRS ENS LyonINRIA Lyon France

ISBN: (纸本)9783642346118;9783642346101

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Applied Mathematics, 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction: Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution. Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs. If T is a given tree, deciding whether a circle graph has a dominating set isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by vertical bar V(T)vertical bar. We prove that the FPT algorithm is subexponential.

关键词： circle graphs domination problems parameterized complexity parameterized algorithms dynamic programming constrained domination

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

P- Matchings parameterized by Treewidth 49th

P- Matchings Parameterized by Treewidth

引用

49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Chaudhary, Juhi Zehavi, Meirav Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

ISBN: (纸本)9783031433795;9783031433801

A matching is a subset of edges in a graph G that do not share an endpoint. A matching M is a P-matching if the subgraph of G induced by the endpoints of the edges of M satisfies property P. For example, if the property P is that of being a matching, being acyclic, or being disconnected, then we obtain an induced matching, an acyclic matching, and a disconnected matching, respectively. In this paper, we analyze the problems of the computation of these matchings from the viewpoint of parameterized Complexity with respect to the parameter treewidth.

关键词： Matching Treewidth parameterized algorithms Exponential Time Hypothesis

来源：评论

学校读者我要写书评

暂无评论

Paths of Bounded Length and Their Cuts: parameterized Complexity and Algorithm

Paths of Bounded Length and Their Cuts: Parameterized Comple...

引用

4th International Workshop on parameterized and Exact Computation

作者： Golovach, Petr A. Thilikos, Dimitrios M. Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway Univ Athens Dept Math Natl & Kapodistrian GR-15784 Athens Greece

ISBN: (纸本)9783642112683

We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem anti the bounded length cut problem. From Menger's theorem both problems are equivalent (and computationally easy) in the unbounded case for single source, single target;paths. However, in the bounded case, they are combinatorially distinct and are both NP-hard, even to approximate. Our results indicate that a more refined landscape appears when we study these problems with respect to their parameterized complexity. For this, we consider several parameterizations (with respect to the maximum length of paths, the number k of paths or the size of a cut, and the treewidth of the input graph) of all variants of both problems (edge/vertex-disjoint paths or cuts, directed/undirected). We provide FPT-algorithms (for all variants) when parameterized by both A: and I and hardness results when the parameter is only one of A: and I. Our results indicate that the bounded length disjoint-path variants are structurally harder than their bounded length cut counterparts. Also, it appears that the edge variants are harder than their vertex-disjoint counterparts when parameterized by the treewidth of the input graph.

关键词： Bounded length disjoint paths Bounded length cuts parameterized Complexity parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

A Faster parameterized Algorithm for Treedepth

A Faster Parameterized Algorithm for Treedepth

引用

41st International Colloquium on Automata, Languages and Programming (ICALP)

作者： Reidl, Felix Rossmanith, Peter Villaamil, Fernando Sanchez Sikdar, Somnath Rhein Westfal TH Aachen Theoret Comp Sci Dept Comp Sci Aachen Germany

ISBN: (纸本)9783662439487

The width measure treedepth, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence of interest. We present an algorithm which-given as input an n-vertex graph, a tree decomposition of width w, and an integer t-decides whether the input graph has treedepth at most t in time 2(O(wt)) . n. We use this to construct further algorithms which do not require a tree decomposition as part of their input: A simple algorithm which decides treedepth in linear time for a fixed t, thus answering an open question posed by Ossona de Mendez and Nesetril as to whether such an algorithm exists, a fast algorithm with running time 2(O(t2)) . n and an algorithm for chordal graphs with running time 2(O(t log t)) . n.

关键词： treedepth vertex ranking centered coloring width measures parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices 35

Parameterized Approximation Schemes for Steiner Trees with S...

引用

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

作者： Dvorak, Pavel Feldmann, Andreas Emil Knop, Dusan Masarik, Tomas Toufar, Tomas Vesely, Pavel Charles Univ Prague Comp Sci Inst Prague Czech Republic Charles Univ Prague Dept Appl Math Prague Czech Republic Univ Bergen Dept Informat Bergen Norway

ISBN: (纸本)9783959770620

We study the STEINER TREE problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parametrization. In particular, on one hand STEINER TREE is known to be APX-hard, and W[2]-hard on the other, if parameterized by the number of non-terminals (Steiner vertices) in the optimum solution. In contrast to this we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the considered parameter. We further study the parameterized approximability of other variants of STEINER TREE, such as DIRECTED STEINER TREE and STEINER FOREST. For neither of these an EPAS is likely to exist for the studied parameter: for STEINER FOREST an easy observation shows that the problem is APX-hard, even if the input graph contains no Steiner vertices. For DIRECTED STEINER TREE we prove that computing a constant approximation for this parameter is W[1]-hard. Nevertheless, we show that an EPAS exists for UNWEIGHTED DIRECTED STEINER TREE. Also we prove that there is an EPAS and a PSAKS for STEINER FOREST if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter.

关键词： Steiner Tree Steiner Forest Approximation algorithms parameterized algorithms Lossy Kernelization

来源：评论

学校读者我要写书评

暂无评论

parameterized Pre-Coloring Extension and List Coloring Problems 37

Parameterized Pre-Coloring Extension and List Coloring Probl...

引用

37th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Gutin, Gregory Majumdar, Diptapriyo Ordyniak, Sebastian Wahlstrom, Magnus Royal Holloway Univ London London England Univ Sheffield Sheffield S Yorkshire England

ISBN: (纸本)9783959771405

Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the parameterized complexity of the following problems parameterized by k: (1) Given a graph G, a clique modulator D (a clique modulator is a set of vertices, whose removal results in a clique) of size k for G, and a list L(v) of colors for every v epsilon V (G), decide whether G has a proper list coloring;(2) Given a graph G, a clique modulator D of size k for G, and a pre-coloring lambda(P) : X -> Q for X subset of V (G), decide whether lambda(P) can be extended to a proper coloring of G using only colors from Q. For Problem 1 we design an O* (2(k))-time randomized algorithm and for Problem 2 we obtain a kernel with at most 3k vertices. Banik et al. (IWOCA 2019) proved the following problem is fixed-parameter tractable and asked whether it admits a polynomial kernel: Given a graph G, an integer k, and a list L(v) of exactly n - k colors for every v epsilon V (G), decide whether there is a proper list coloring for G. We obtain a kernel with O(k(2)) vertices and colors and a compression to a variation of the problem with O(k) vertices and O(k(2)) colors.

关键词： parameterized algorithms W-hardness Kernelization Graph Coloring List Coloring

来源：评论

学校读者我要写书评

暂无评论

LP can be a cure for parameterized Problems

LP can be a cure for Parameterized Problems

引用

29th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Narayanaswamy, N. S. Raman, Venkatesh Ramanujan, M. S. Saurabh, Saket IIT Madras Dept Comp Sci & Engn Chennai Tamil Nadu India Inst Math Sci Chennai 600113 Tamil Nadu India

ISBN: (纸本)9783939897354

We investigate the parameterized complexity of VERTEX COVER parameterized above the optimum value of the linear programming (LP) relaxation of the integer linear programming formulation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that even the most straightforward branching algorithm (after some preprocessing) results in an O*(2.6181(r)) algorithm for the problem where r is the excess of the vertex cover size over the LP optimum. We write O*(f(k)) for a time complexity of the form O(f(k)n(O(1))), where f(k) grows exponentially with k. Then, using known and new reductions, we give O*(2.6181(k)) algorithms for the parameterized versions of ABOVE GUARANTEE VERTEX COVER, ODD CYCLE TRANSVERSAL, SPLIT VERTEX DELETION AND ALMOST 2-SAT, and an O*(1.6181(k)) algorithm for KONIG VERTEX DELETION, VERTEX COVER PARAM BY OCT and VERTEX COVER PARAM BY KVD. These algorithms significantly improve the best known bounds for these problems. The notable improvement is the bound for ODD CYCLE TRANSVERSAL for which this is the first major improvement after the first algorithm that showed it fixed-parameter tractable in 2003. We also observe that using our algorithm, one can obtain a simple kernel for the classical vertex cover problem with at most 2k - O(log k) vertices.

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：