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

Fixed-Parameter Tractability of Maximum Colored Path and Beyond

ACM TRANSACTIONS ON algorithms 2024年第4期20卷 1-48页

作者： V. Fomin, Fedor Golovach, Petr a. Korhonen, Tuukka Simonov, Kirill Plattner, Hasso Stamoulis, Giannos Univ Bergen Dept Informat Bergen Norway Univ Potsdam Hasso Plattner Inst Potsdam Germany Univ Montpellier LIRMM CNRS Montpellier France

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We give a randomized algorithm, that given a colored n-vertex undirected graph, vertices s and t , and an integer k , finds an ( s, t )-path containing at least k different colors in time 2 k n O (1). This is the first fpt algorithm for this problem, and it generalizes the algorithm of Bj & ouml;rklund, Husfeldt, and Taslaman on finding a path through k specified vertices. It also implies the first 2 k n O (1) time algorithm for finding an ( s, t )-path of length at least k . Our method yields fpt algorithms for even more general problems. For example, we consider the problem where the input consists of an n-vertex undirected graph G , a matroid M whose elements correspond to the vertices of G and which is represented over a finite field of order q , a positive integer weight function on the vertices of G , two sets of vertices S, T subset of V ( G ) , and integers p, k, w , and the task is to find p vertex-disjoint paths from S to T so that the union of the vertices of these paths contains an independent set of M of cardinality k and weight w , while minimizing the sum of the lengths of the paths. We give a 2 p+O(k 2 log (q+k)) n O( 1 ) w time randomized algorithm for this problem.

关键词： fpt algorithms finding long paths algebraic techniques in fpt

来源：评论

学校读者我要写书评

暂无评论

On the Parameterized Complexity of Bend-Minimum Orthogonal Planarity

引用

ALGORITHMICA 2024年第10期86卷 3231-3251页

作者： Di Giacomo, Emilio Didimo, Walter Liotta, Giuseppe Montecchiani, Fabrizio Ortali, Giacomo Univ Perugia Dept Engn Perugia Italy

Computing planar orthogonal drawings with the minimum number of bends is one of the most studied topics in Graph Drawing. The problem is known to be NP-hard, even when we want to test the existence of a rectilinear planar drawing, i.e., an orthogonal drawing without bends (Garg and Tamassia in SIAM J Comput 31(2):601-625, 2001). From the parameterized complexity perspective, the problem is fixed-parameter tractable when parameterized by the sum of three parameters: the number b of bends, the number k of vertices of degree at most two, and the treewidth tw\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf{tw}$$\end{document} of the input graph (Di Giacomo et al. in J Comput Syst Sci 125:129-148, 2022). We improve this last result by showing that the problem remains fixed-parameter tractable when parameterized only by b+k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b+k$$\end{document}. As a consequence, rectilinear planarity testing lies in fpt parameterized by the number of vertices of degree at most two. We also prove that our choice of parameters is minimal, as deciding if an orthogonal drawing with at most b bends exists is already NP-hard when k is zero (i.e., the problem is para-NP-hard parameterized in k);hence, there is neither an fpt nor an XP algorithm parameterized only by the parameter k (unless P = NP). In addition, we prove that the problem is W[1]-hard parameterized by k+tw\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{

关键词： Orthogonal drawings Bend minimization Parameterized complexity fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

A 2k-kernelization algorithm for vertex cover based on crown decomposition

引用

THEORETICAL COMPUTER SCIENCE 2018年 739卷 80-85页

作者： Li, Wenjun Zhu, Binhai Changsha Univ Sci & Technol Hunan Prov Key Lab Intelligent Proc Big Data Tran Changsha Hunan Peoples R China Montana State Univ Gianforte Sch Comp Bozeman MT 59717 USA

We revisit crown decomposition for the Vertex Cover problem by giving a simple 2k-kernelization algorithm. Previously, a 2k kernel was known but it was computed using both crown decomposition and linear programming;moreover, with crown decomposition alone only a 3k kernel was known. Our refined crown decomposition carries some extra property and could be used for some other related problems. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Vertex cover Crown decomposition Kernelization fpt algorithms NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Parameterized Complexity of Maximum Edge Colorable Subgraph

引用

ALGORITHMICA 2022年第10期84卷 3075-3100页

作者： Agrawal, Akanksha Kundu, Madhumita Sahu, Abhishek Saurabh, Saket Tale, Prafullkumar Indian Inst Technol Madras Chennai Tamil Nadu India Univ Bergen Bergen Norway HBNI Inst Math Sci Chennai Tamil Nadu India CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany

A graph H is p-edge colorable if there is a coloring psi : E(H) -> {1, 2, ... , p}, such that for distinct uv, vw is an element of E(H), we have psi(uv) not equal psi(vw). The MAXIMUM EDGE-COLORABLE SUBGRAPH problem takes as input a graph G and integers 1 and p, and the objective is to find a subgraph H of G and a p-edge-coloring of H, such that vertical bar E(H)vertical bar >= l. We study the above problem from the viewpoint of Parameterized Complexity. We obtain fpt algorithms when parameterized by: (1) the vertex cover number of G, by using INTEGER LINEAR PROGRAMMING, and (2) 1, a randomized algorithm via a reduction to RAINBOW MATCHING, and a deterministic algorithm by using color coding, and divide and color. With respect to the parameters p + k, where k is one of the following: (1) the solution size,l, (2) the vertex cover number of G, and (3) 1-mm(G), where mm(G) is the size of a maximum matching in G;we show that the (decision version of the) problem admits a kernel with O(k . p) vertices. Furthermore, we show that there is no kernel of size O(k(1-epsilon) . f (p)), for any epsilon > 0 and computable function f, unless NP subset of coN P/poly.

关键词： Edge Coloring Kernelization fpt algorithms Kernel Lower Bound

来源：评论

学校读者我要写书评

暂无评论

Upper Dominating Set: Tight algorithms for pathwidth and sub-exponential approximation

引用

THEORETICAL COMPUTER SCIENCE 2022年 923卷 271-291页

作者： Dublois, Louis Lampis, Michael Paschos, Vangelis Th Univ Paris 09 PSL Univ LAMSADE CNRS Paris France

In the Upper Dominating Set problem, the goal is to find a minimal dominating set of maximum size. We study the complexity of parameterized algorithms for Upper Dominating Set, as well as its sub-exponential approximation. First, we prove that, under the ETH, Upper Dominating Set cannot be solved in time O(n(o(k)))(improving on O((no(root k)))), and in the same time we show under the same complexity assumption that for any constant ratio rand any epsilon > 0, there is no r-approximation algorithm running in time O(nk1- e). Then, we settle the problem's complexity parameterized by pathwidth by giving an algorithm running in time O* (6(pw))(improving the current best O* (7(pw))), and a lower bound showing that our algorithm is the best we can get under the SETH. Furthermore, we obtain a simple sub-exponential approximation algorithm for this problem: an algorithm that produces an r-approximation in time n(O(n/r)), for any desired approximation ratio r < n. We finally show that this time-approximation trade-off is tight, up to an arbitrarily small constant in the second exponent: under the randomized ETH, and for any ratio r > 1and epsilon > 0, no algorithm can output an r-approximation in time n((n/r)1-epsilon). Hence, we completely characterize the approximability of the problem in sub-exponential time. (c) 2022 Elsevier B.V. All rights reserved.

关键词： fpt algorithms Sub-exponential approximation Upper Domination

来源：评论

学校读者我要写书评

暂无评论

Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover

引用

DISCRETE APPLIED MATHEMATICS 2005年第1-3期152卷 229-245页

作者： Nishimura, N Ragde, P Thilikos, DM Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada Univ Politecn Cataluna Dept Llenguatges & Sistemas Informat E-08034 Barcelona Spain

Our goal in this paper is the development of fast algorithms for recognizing general classes of graphs. We seek algorithms whose complexity can be expressed as a linear function of the graph size plus an exponential function of k, a natural parameter describing the class. In particular, we consider the class W-k (G), where for each graph G in W-k(G), the removal of a set of at most k vertices from G results in a graph in the base graph class W. (If W is the class of edgeless graphs, W-k(G) is the class of graphs with bounded vertex cover.) When G, is a minor-closed class such that each graph in W has bounded maximum degree, and all obstructions of (minor-minimal graphs outside G) are connected, we obtain an O((g + k)vertical bar V(G)vertical bar + (fk)(k)) recognition algorithm for W-k(G), where g and f are constants (modest and quantified) depending on the class K If 9 is the class of graphs with maximum degree bounded by D (not closed under minors), we can still obtain a running time of O(vertical bar V(G)vertical bar(D+k) +k(D+k)(k+3)) for recognition of graphs in Wk(G). Our results are obtained by considering bounded-degree minor-closed classes for which all obstructions are connected graphs, and showing that the size of any obstruction for W-k (5) is O(tk(7) + t(7)k(2)), where t is a bound on the size of obstructions for W. A trivial corollary of this result is an upper bound of (k + 1) (k + 2) on the number of vertices in any obstruction of the class of graphs with vertex cover of size at most k. These results are of independent graph-theoretic interest. (c) 2005 Elsevier B.V. All rights reserved.

关键词： parameterized complexity graph minors fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

ON THE FINE-GRAINED COMPLEXITY OF RAINBOW COLORING

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2018年第3期32卷 1672-1705页

作者： Kowalik, Lukasz Lauri, Juho Socala, Arkadiusz Univ Warsaw Inst Informat Fac Math Informat & Mech Warsaw Poland Tampere Univ Technol Tampere Finland Nokia Bell Labs Dublin Ireland

The RAINBOW k-COLORING problem asks whether the edges of a given graph can be colored in k colors so that every pair of vertices is connected by a rainbow path, i. e., a path with all edges of di ff erent colors. Our main result states that for any k >= 2, there is no algorithm for RAINBOW k-COLORING running in time 2(o)(n(3/2)), unless the exponential time hypothesis fails. Motivated by this negative result we consider two parameterized variants of the problem. In the Subset Rainbow k-COLORING problem, introduced by Chakraborty et al. [J. Comb. Optim., 21 (2009), pp. 330{347], we are additionally given a set S of pairs of vertices and we ask if there is a coloring in which all the pairs in S are connected by rainbow paths. We show that Subset RAINBOW k-COLORING is fixed parameter tractable (fpt) when parameterized by jSj. We also study the Maximum RAINBOW k-COLORING problem, where we are additionally given an integer q, and we ask if there is a coloring in which at least q anti-edges are connected by rainbow paths. We show that the problem is fpt when parameterized by q and has a kernel of size O (q) for every k >= 2, extending the result of Ananth, Nasre, and Sarpatwar, in FSTTCS, LIPIcs, Schloss Dagstuhl{Leibniz-Zentum fur Informatik, Dagstuhl, Germany, 2011, pp. 241{251. We believe that our techniques used for the lower bounds may shed some light on the complexity of the classical EDGE COLORING problem, where it is a major open question if a 2(O(n))-time algorithm exists.

关键词： graph coloring computational complexity lower bounds fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

Proper Interval Vertex Deletion

引用

ALGORITHMICA 2013年第4期65卷 845-867页

作者： van 't Hof, Pim Villanger, Yngve Univ Bergen Dept Informat N-5020 Bergen Norway

The NP-complete problem Proper Interval Vertex Deletion is to decide whether an input graph on n vertices and m edges can be turned into a proper interval graph by deleting at most k vertices. Van Bevern et al. (In: Proceedings WG 2010. Lecture notes in computer science, vol. 6410, pp. 232-243, 2010) showed that this problem can be solved in time. We improve this result by presenting an time algorithm for Proper Interval Vertex Deletion. Our fixed-parameter algorithm is based on a new structural result stating that every connected component of a {claw,net,tent,C (4),C (5),C (6)}-free graph is a proper circular arc graph, combined with a simple greedy algorithm that solves Proper Interval Vertex Deletion on {claw,net,tent,C (4),C (5),C (6)}-free graphs in time. Our approach also yields a polynomial-time 6-approximation algorithm for the optimization variant of Proper Interval Vertex Deletion.

关键词： Proper interval graphs Proper circular arc graphs Vertex deletion fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

Colored Hypergraph Isomorphism is Fixed Parameter Tractable

Colored Hypergraph Isomorphism is Fixed Parameter Tractable

引用

30th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)

作者： Arvind, V. Das, Bireswar Koebler, Johannes Toda, Seinosuke Inst Math Sci Madras 600113 Tamil Nadu India Indian Inst Technol Gandhinagar India Humboldt Univ Inst Informat Berlin Germany Nihon Univ Tokyo Japan

ISBN: (纸本)9783939897231

We describe a fixed parameter tractable (fpt) algorithm for COLORED HYPERGRAPH ISOMORPHISM which has running time 2(O(b))N(O(1)), where the parameter b is the maximum size of the color classes of the given hypergraphs and N is the input size. We also describe fpt algorithms for certain permutation group problems that are used as subroutines in our algorithm.

关键词： Fixed parameter tractability fpt algorithms graph isomorphism computational complexity

来源：评论

学校读者我要写书评

暂无评论

Combining Networks Using Cherry Picking Sequences 7th

Combining Networks Using Cherry Picking Sequences

引用

7th International Conference on algorithms for Computational Biology (AlCoB) / 8th International Conference on algorithms for Computational Biology (AlCoB)

作者： Janssen, Remie Jones, Mark Murakami, Yukihiro Delft Univ Technol Delft Inst Appl Math Van Mourik Broekmanweg 6 NL-2628 XE Delft Netherlands Ctr Wiskunde & Informat POB 94079 NL-1090 GB Amsterdam Netherlands

ISBN: (纸本)9783030422660;9783030422653

Phylogenetic networks are important for the study of evolution. The number of methods to find such networks is increasing, but most such methods can only reconstruct small networks. To find bigger networks, one can attempt to combine small networks. In this paper, we study the Network Hybridization problem, a problem of combining networks into another network with low complexity. We characterize this complexity via a restricted problem, Tree-child Network Hybridization, and we present an fpt algorithm to efficiently solve this restricted problem.

关键词： Phylogenetic networks Network hybridization Tree-child networks fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：