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

parameterized complexity analysis for the Closest String with Wildcards problem

THEORETICAL COMPUTER SCIENCE 2015年 600卷 11-18页

作者： Hermelin, Danny Rozenberg, Liat Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Univ Haifa IL-31999 Haifa Israel

The Closest String problem asks to find a string s which is not too far from each string in a set of m input strings, where the distance is taken as the Hamming distance. This well-studied problem has various applications in computational biology and drug design. In this paper, we introduce a new variant of Closest String where the input strings can contain wildcards that can match any letter in the alphabet, and the goal is to find a solution string without wildcards. We call this problem the Closest String with Wildcards problem, and we analyze it in the framework of parameterized complexity. Our study determines for each natural parameterization whether this parameterization yields a fixed-parameter algorithm, or whether such an algorithm is highly unlikely to exist. (C) 2015 Elsevier B.V. All rights reserved.

关键词： parameterized complexity The closest string problem fixed-parameter algorithms Computational biology

来源：评论

学校读者我要写书评

暂无评论

Phylogeny- and parsimony-based haplotype inference with constraints

引用

INFORMATION AND COMPUTATION 2012年 213卷 33-47页

作者： Elberfeld, Michael Tantau, Till Univ Lubeck Inst Theoret Informat D-23538 Lubeck Germany

Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast computational haplotyping method is based on an evolutionary model where a perfect phylogenetic tree is sought that explains the observed data. An extension of this approach tries to incorporate prior knowledge in the form of a set of candidate haplotypes from which the right haplotypes must be chosen. The objective is to increase the accuracy of haplotyping methods, but it was conjectured that the resulting formal problem constrained perfect phylogeny haplotyping might be NP-complete. In the paper at hand we present a polynomial-time algorithm for it. Our algorithmic ideas also yield new fixed-parameter algorithms for related haplotyping problems based on the maximum parsimony assumption. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Haplotype inference Perfect phylogeny Maximum parsimony Polynomial-time algorithms fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

Combinatorial n-fold integer programming and applications

引用

MATHEMATICAL PROGRAMMING 2020年第1-2期184卷 1-34页

作者： Knop, Dusan Koutecky, Martin Mnich, Matthias Czech Tech Univ Fac Informat Technol Dept Theoret Comp Sci Prague Czech Republic Technion Israel Inst Technol Haifa Israel Charles Univ Prague Prague Czech Republic TU Hamburg Inst Algorithms & Complex Hamburg Germany Univ Bonn Bonn Germany

Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is exponential only in the dimension of the program, and polynomial in the size of the ILP. That algorithm became a ubiquitous tool in the design of fixed-parameter algorithms for NP-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, in many cases using Lenstra's algorithm has two drawbacks: First, the run time of the resulting algorithms is often double-exponential in the parameter, and second, an ILP formulation in small dimension cannot easily express problems involving many different costs. Inspired by the work of Hemmecke et al. (Math Program 137(12, Ser. A):325-341, 2013), we develop a single-exponential algorithm for so-called combinatorial n-fold integer programs, which are remarkably similar to prior ILP formulations for various problems, but unlike them, also allow variable dimension. We then apply our algorithm to many relevant problems problems like Closest String, Swap Bribery, Weighted Set Multicover, and several others, and obtain exponential speedups in the dependence on the respective parameters, the input size, or both. Unlike Lenstra's algorithm, which is essentially a bounded search tree algorithm, our result uses the technique of augmenting steps. At its heart is a deep result stating that in combinatorial n-fold IPs, existence of an augmenting step implies existence of a "local" augmenting step, which can be found using dynamic programming. Our results provide an important insight into many problems by showing that they exhibit this phenomenon, and highlights the importance of augmentation techniques.

关键词： Integer programming Augmentation algorithm Closest string fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms for Disjoint Matchings in Weighted Graphs with Applications

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2016年第6期E99A卷 1050-1058页

作者： Chen, Zhi-Zhong Tsukiji, Tatsuie Yamada, Hiroki Tokyo Denki Univ Div Informat Syst Design Hatogaya Saitama 3500394 Japan

It is a well-known and useful problem to find a matching in a given graph G whose size is at most a given parameter k and whose weight is maximized (over all matchings of size at most k in G). In this paper, we consider two natural extensions of this problem. One is to find t disjoint matchings in a given graph G whose total size is at most a given parameter k and whose total weight is maximized, where t is a (small) constant integer. Previously, only the special case where t = 2 was known to be fixed -parameter tractable. In this paper, we show that the problem is fixed parameter tractable for any constant t. When t = 2, the time complexity of the new algorithm is significantly better than that of the previously known algorithm. The other is to find a set of vertex -disjoint paths each of length 1 or 2 in a given graph whose total length is at most a given parameter k and whose total weight is maximized. As interesting applications, we further use the algorithms to speed up several known approximation algorithms (for related NP -hard problems) whose approximation ratio depends on a fixed parameter 0 < epsilon < 1 and whose running time is dominated by the time needed for exactly solving the problems on graphs in which each connected component has at most epsilon(-1) vertices.

关键词： fixed-parameter algorithms randomized algorithms matchings color-coding universal sets

来源：评论

学校读者我要写书评

暂无评论

Computational study on planar dominating set problem

引用

THEORETICAL COMPUTER SCIENCE 2009年第52期410卷 5455-5466页

作者： Marzban, Marjan Gu, Qian-Ping Jia, Xiaohua Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

Recently, there has been significant theoretical progress towards fixed-parameter algorithms for the DOMINATING SET problem of planar graphs. It is known that the problem on a planar graph with n vertices and dominating number k can be solved in 0(2(0(root k))n) time using tree/branch-decomposition based algorithms. In this paper, we report computational results of Fomin and Thilikos algorithm which uses the branch-decomposition based approach. The computational results show that the algorithm can solve the DOMINATING SET problem of large planar graphs in a practical time and memory space for the class of graphs with small branch width. For the class of graphs with large branch width, the size of instances that can be solved by the algorithm in practice is limited to about one thousand edges due to a memory space bottleneck. The practical performances of the algorithm coincide with the theoretical analysis of the algorithm. The results of this paper suggest that the branch-decomposition based algorithms can be practical for some applications on planar graphs. (C) 2009 Elsevier B.V. All rights reserved.

关键词： PLANAR DOMINATING SET Branch-decomposition fixed-parameter algorithms Data reduction Computational study

来源：评论

学校读者我要写书评

暂无评论

Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs

引用

JOURNAL OF THE ACM 2005年第6期52卷 866-893页

作者： Demaine, ED Fomin, FV Hajiaghayi, M Thilikos, DM MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Univ Bergen Dept Informat N-5020 Bergen Norway MIT Cambridge MA 02139 USA Natl & Capodistrian Univ Athens Dept Math GR-15784 Athens Greece

We introduce a new framework for designing fixed-parameter algorithms with subexponential running time-2(O(root k))n(O(1)). Our results apply to a broad family of graph problems, called bidimensional problems, which includes many domination and problems such as vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, disk dimension, and many others restricted to bounded-genus graphs (phrased as bipartite-graph problem). Furthermore, it is fairly straightforward to prove that a problem is bidimensional. In particular, our framework includes, as special cases, all previously known problems to have such subexponential algorithms. Previously, these algorithms applied to planar graphs, single-crossing-minor-free graphs, and/or map graphs;we extend these results to apply to bounded-genus graphs as well. In a parallel development of combinatorial results, we establish an upper bound on the treewidth (or branchwidth) of a bounded-genus graph that excludes some planar graph H as a minor. This bound depends linearly on the size vertical bar V(H)vertical bar of the excluded graph H and the genus g(G) of the graph G, and applies and extends the graph-minors work of Robertson and Seymour. Building on these results, we develop subexponential fixed-parameter algorithms for dominating set, vertex cover, and set cover in any class of graphs excluding a fixed graph H as a minor. In particular, this general category of graphs includes planar graphs, bounded-genus graphs, single-crossing-minor-free graphs, and any class of graphs that is closed under taking minors. Specifically, the running time is 2(O(root k))n(h), where h is a constant depending only on H, which is polynomial for k = O(log(2) n). We introduce a general approach for developing algorithms on H-minor-free graphs, based on structural results about H-minor-free graphs at the heart of Robertson and Seymour's graph-minors work. We believe this approach opens the way to further develo

关键词： algorithms design theory (k, r)-center fixed-parameter algorithms domination planar graph map graph

来源：评论

学校读者我要写书评

暂无评论

Dynamic parameterized Problems and algorithms

引用

ACM TRANSACTIONS ON algorithms 2020年第4期16卷 1–46页

作者： Alman, Josh Mnich, Matthias Williams, Virginia Vassilevska MIT CSAIL 77 Massachusetts Ave Cambridge MA 02139 USA Harvard Univ Cambridge MA 02138 USA TU Hamburg Inst Algorithms & Complex D-21071 Hamburg Germany

fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet so far those algorithms have been largely restricted to static inputs. In this article, we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dynamic inputs. We consider a variety of parameterized graph and hitting set problems that are known to have f(k)n(1+o(1)) time algorithms on inputs of size n, and we consider the question of whether there is a data structure that supports small updates (such as edge/vertex/set/element insertions and deletions) with an update time of.(k)n(o(1));such an update time would be essentially optimal. Update and query times independent of n are particularly desirable. Among many other results, we show that FEEDBACK VERTEX SET and k-PATH admit dynamic algorithms with f (k) log(O(1)) n update and query times for some function f depending on the solution size k only. We complement our positive results by several conditional and unconditional lower bounds. For example, we show that unlike their undirected counterparts, DIRECTED FEEDBACK VERTEX SET and DIRECTED k-PATH do not admit dynamic algorithms with n(o(1)) update and query times even for constant solution sizes k <= 3, assuming popular hardness hypotheses. We also show that unconditionally, in the cell probe model, DIRECTED FEEDBACK VERTEX SET cannot be solved with update time that is purely a function of k.

关键词： fixed-parameter algorithms dynamic algorithms cell probe lower bounds

来源：评论

学校读者我要写书评

暂无评论

A Fast Branching Algorithm for Cluster Vertex Deletion

引用

THEORY OF COMPUTING SYSTEMS 2016年第2期58卷 357-376页

作者： Boral, Anudhyan Cygan, Marek Kociumaka, Tomasz Pilipczuk, Marcin Chennai Math Inst Madras Tamil Nadu India Univ Warsaw Inst Informat Warsaw Poland

In the family of clustering problems we are given a set of objects (vertices of the graph), together with some observed pairwise similarities (edges). The goal is to identify clusters of similar objects by slightly modifying the graph to obtain a cluster graph (disjoint union of cliques). Huffner et al. (Theory Comput. Syst. 47(1), 196-217, 2010) initiated the parameterized study of CLUSTER VERTEX DELETION, where the allowed modification is vertex deletion, and presented an elegant O (min(2(k)k(6) log k + n(3), 2(k)km root n log n))-time fixed-parameter algorithm, parameterized by the solution size. In the last 5 years, this algorithm remained the fastest known algorithm for CLUSTER VERTEX DELETION and, thanks to its simplicity, became one of the textbook examples of an application of the iterative compression principle. In our work we break the 2(k)-barrier for CLUSTER VERTEX DELETION and present an O(1.9102(k)(n + m))-time branching algorithm. We achieve this improvement by a number of structural observations which we incorporate into the algorithm's branching steps.

关键词： fixed-parameter algorithms Cluster vertex deletion Branching

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm for computing network reliability in small treewidth

引用

RELIABILITY ENGINEERING & SYSTEM SAFETY 2020年 193卷 106665-000页

作者： Goharshady, Amir Kafshdar Mohammadi, Fatemeh IST Austria Campus 1 A-3400 Klosterneuburg Austria Univ Bristol Sch Math Bristol BS8 1TW Avon England

We consider the classic problem of NETWORK RELIABILITY. A network is given together with a source vertex, one or more target vertices, and probabilities assigned to each of the edges. Each edge of the network is operable with its associated probability and the problem is to determine the probability of having at least one source-to-target path that is entirely composed of operable edges. This problem is known to be NP-hard. We provide a novel scalable algorithm to solve the NETWORK RELIABILITY problem when the treewidth of the underlying network is small. We also show our algorithm's applicability for real-world transit networks that have small treewidth, including the metro networks of major cities, such as London and Tokyo. Our algorithm leverages tree decompositions to shrink the original graph into much smaller graphs, for which reliability can be efficiently and exactly computed using a brute force method. To the best of our knowledge, this is the first exact algorithm for NETWORK RELIABILITY that can scale to handle real-world instances of the problem.

关键词： Network reliability fixed-parameter algorithms Tree decomposition Treewidth FPT

来源：评论

学校读者我要写书评

暂无评论

On directed covering and domination problems

引用

DISCRETE APPLIED MATHEMATICS 2019年 259卷 76-99页

作者： Hanaka, Tesshu Nishimura, Naomi Ono, Hirotaka Chuo Univ Dept Informat & Syst Engn Tokyo Japan Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON Canada Nagoya Univ Dept Math Informat Nagoya Aichi Japan

In this paper, we study covering and domination problems on directed graphs. Although undirected VERTEX COVER and EDGE DOMINATING SET are well-studied classical graph problems, the directed versions have not been studied much due to the lack of clear definitions. We give natural definitions for DIRECTED r-IN (OUT) VERTEX COVER and DIRECTED (p, q)-EDGE DOMINATING SET as directed generalizations Of VERTEX COVER and EDGE DOMINATING SET. For these problems, we show that (1) DIRECTED r-IN (OUT) VERTEX COVER and DIRECTED (p, q)-EDGE DOMINATING SET are NP-complete on planar directed acyclic graphs except when r = 1 or (p, q) = (0, 0), (2) if r >= 2, DIRECTED r-IN (OUT) VERTEX COVER is W[2]-hard and c In k-inapproximable on directed acyclic graphs, (3) if either p or q is greater than 1, DIRECTED (p, q)-EDGE DOMINATING SET is W[2]-hard and c In k-inapproximable on directed acyclic graphs, (4) all problems can be solved in polynomial time on trees, and (5) DIRECTED (0, 1)-EDGE ((1, 0)-EDGE, (1, 1)-EDGE) DOMINATING SET is fixed-parameter tractable on general graphs. The first result implies that DIRECTED r-DOMINATING SET on directed line graphs is NP-complete even if r = 1. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Directed graph Vertex cover Dominating set Edge dominating set fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：