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

parameterized algorithms for generalizations of Directed Feedback Vertex Set

DISCRETE OPTIMIZATION 2022年第0期46卷

作者： Goke, Alexander Marx, Daniel Mnich, Matthias Hamburg Univ Technol Inst Algorithms & Complex Hamburg Germany CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany

The DIRECTED FEEDBACK VERTEX SET (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp's 21 NP-complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. (2008) showed its fixed-parameter tractability via a 4kk!nO(1)-time algorithm, where k = |S|. Here we show fixed-parameter tractability of two generalizations of DFVS:center dot Find a smallest vertex set S such that every strong component of G - S has size at most s: we give an algorithm solving this problem in time 4k(ks + k + s)! middot nO(1). This generalizes an algorithm by Xiao (2017) for the undirected version of the *** dot Find a smallest vertex set S such that every non-trivial strong component of G - S is 1-out-regular: we give an algorithm solving this problem in time 2O(k3) middot nO(1). We also solve the corresponding arc versions of these problems by fixed-parameter algorithms. (c) 2022 Published by Elsevier B.V.

关键词： fixed-parameter algorithms Directed Feedback Vertex Set

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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 the Relation of Strong Triadic Closure and Cluster Deletion

引用

ALGORITHMICA 2020年第4期82卷 853-880页

作者： Gruettemeier, Niels Komusiewicz, Christian Philipps Univ Marburg Fachbereich Math & Informat Marburg Germany

We study the parameterized and classical complexity of two problems that are concerned with induced paths on three vertices, called P(3)s, in undirected graphs G = ( V, E). In Strong Triadic Closure we aim to label the edges in E as strong and weak such that at most k edges are weak and G contains no induced P-3 with two strong edges. In Cluster Deletion we aim to destroy all induced P3s by a minimum number of edge deletions. We first show that Strong Triadic Closure admits a 4k-vertex kernel. Then, we study parameterization by l := |E|- k and show that both problems are fixed-parameter tractable and unlikely to admit a polynomial kernel with respect to l. Finally, we give a dichotomy of the classical complexity of both problems on H-free graphs for all H of order at most four.

关键词： Social networks fixed-parameter algorithms Kernelization Graph classes

来源：评论

学校读者我要写书评

暂无评论

Stable Matchings with Covering Constraints: A Complete Computational Trichotomy

引用

ALGORITHMICA 2020年第5期82卷 1136-1188页

作者： Mnich, Matthias Schlotter, Ildiko Univ Bonn Bonn Germany TU Hamburg Inst Algorithms & Complex Hamburg Germany Budapest Univ Technol & Econ Budapest Hungary

Stable matching problems with lower quotas are fundamental in academic hiring and ensuring operability of rural hospitals. Only few tractable (polynomial-time solvable) cases of stable matching with lower quotas have been identified;most such problems are NP-hard and also hard to approximate (Hamada et al. in Algorithmica 74(1):440-465, 2016). We therefore consider stable matching problems with lower quotas under a relaxed notion of tractability, namely fixed-parameter tractability. By cloning hospitals we focus on the case when all hospitals have upper quota equal to 1, which generalizes the setting of "arranged marriages" first considered by Knuth (Mariages stables et leurs relations avec d'autres problemes combinatoires, Les Presses de l'Universite de Montreal, Montreal, 1976). We investigate how a set of natural parameters, namely the maximum length of preference lists for men and women, the number of distinguished men and women, and the number of blocking pairs allowed determine the computational tractability of this problem. Our main result is a complete complexity trichotomy: for each choice of parameters we either provide a polynomial-time algorithm, or an NP-hardness proof and fixed-parameter algorithm, or NP-hardness proof and W[1]-hardness proof. As corollary, we negatively answer a question by Hamada et al. (Algorithmica 74(1):440-465, 2016) by showing fixed-parameter intractability parameterized by optimal solution size. We also classify all cases of one-sided constraints where only women may be distinguished.

关键词： Stable marriage Lower quotas fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

Identifying duplications and lateral gene transfers simultaneously and rapidly

引用

JOURNAL OF BIOINFORMATICS AND COMPUTATIONAL BIOLOGY 2022年第1期20卷 2150033-2150033页

作者： Chen, Zhi-Zhong Deng, Fei Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hatoyama Saitama 3500394 Japan City Univ Hong Kong Dept Comp Sci Kowloon Tat Chee Ave Hong Kong Peoples R China

This paper deals with the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Previously, [Tofigh A, Hallett M, Lagergren J, Simultaneous identification of duplications and lateral gene transfers, IEEE/ACM Trans Comput Biol Bioinf 517-535, 2011.] gave a fixed-parameter algorithm for this problem that runs in O(m + 3(k)n) time, where m is the number of vertices in S, n is the number of vertices in G, and k is the minimum cost of an LCA-reconciliation between S and G. In this paper, by refining their algorithm, we obtain a new one for the same problem that finds and outputs the solutions in a compact form within O(mn(2) + 3(k)) time. In the most interesting case where 3(k) >= mn(2) , our algorithm is O(n) times faster.

关键词： Phylogenetic trees reconciliations fixed-parameter algorithms enumerate algorithms

来源：评论

学校读者我要写书评

暂无评论

Designing and implementing algorithms for the closest string problem

引用

THEORETICAL COMPUTER SCIENCE 2019年 786卷 32-43页

作者： Yuasa, Shota Chen, Zhi-Zhong Ma, Bin Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hatoyama Saitama 3500394 Japan Univ Waterloo Sch Comp Sci 200 Univ Ave W Waterloo ON N2L 3G1 Canada City Univ Hong Kong Dept Comp Sci Kowloon Tat Chee Ave Hong Kong Peoples R China City Univ Hong Kong Shenzhen Res Inst Shenzhen Hitech Ind Pk Shenzhen Peoples R China

Given a set of n strings of length L and a radius d, the closest string problem (CSP for short) asks for a string t(sol) that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). A number of parameterized algorithms have been then developed to solve the problem when d is small. Among them, the relatively new ones have not been implemented before and their performance in practice was unknown. In this study, we implement all of them by careful engineering. For those that have been implemented before, our implementation is much faster. For some of those that have not been implemented before, our experimental results show that there exist huge gaps between their theoretical and practical performances. We also design a new parameterized algorithm for the binary case of CSP. The algorithm is deterministic and runs in O (n(2)L + n(2)d. 6.16(d)) time, while the previously best deterministic algorithm runs in O (nL + nd(3). 6.731(d)) time. (C) 2018 Elsevier B.V. All rights reserved.

关键词： The closest string problem fixed-parameter algorithms Computational biology Algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On the tractability of finding disjoint clubs in a network

引用

THEORETICAL COMPUTER SCIENCE 2019年 777卷 243-251页

作者： Dondi, Riccardo Mauri, Giancarlo Zoppis, Italo Univ Bergamo Dipartimento Lettere Filosofia Comunicaz Bergamo Italy Univ Milano Bicocca DISCo Milan Italy

We study a variant of the problem of finding a collection of disjoint s-clubs in a given network. Given a graph, the problem asks whether there exists a collection of at most r disjoint s-clubs that covers at least k vertices of the network. An s-club is a connected graph that has diameter bounded by s, for a positive integer s. We demand that each club is non-trivial, that is it has order at least t >= 2, for some positive integer t. We prove that the problem is APX-hard even when the input graph has bounded degree, s = 2, t = 3 and r = vertical bar V vertical bar. Moreover, we show that the problem is polynomial-time solvable when s >= 4, t = 3 and r = vertical bar V vertical bar, and when s >= 3, t = 2 and r = vertical bar V vertical bar. Finally, for s >= 2, we present a fixed-parameter algorithm for the problem, when parameterized by the number of covered vertices. (C) 2019 Elsevier B.V. All rights reserved.

关键词： s-Clubs Graph problems APX-hardness Graph algorithms fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：