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

fpt algorithms for Connected Feedback Vertex Set

JOURNAL OF COMBINATORIAL OPTIMIZATION 2012年第2期24卷 131-146页

作者： Misra, Neeldhara Philip, Geevarghese Raman, Venkatesh Saurabh, Saket Sikdar, Somnath Inst Math Sci Madras 600113 Tamil Nadu India Rhein Westfal TH Aachen Aachen Germany

We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=(V,E) and an integer k, decide whether there exists FaS dagger V, |F|a parts per thousand currency signk, such that G[Va-F] is a forest and G[F] is connected. We show that Connected Feedback Vertex Set can be solved in time O(2 (O(k)) n (O(1))) on general graphs and in time on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses, as a subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it could be useful for obtaining parameterized algorithms for other connectivity problems.

关键词： Parameterized algorithms fpt algorithms Connected Feedback Vertex Set Feedback Vertex Set Group Steiner Tree Steiner Tree Directed Steiner Out-Tree Hardness of polynomial kernelization Subexponential fpt algorithms H-minor-free graphs Dynamic programming over tree decompositions

来源：评论

学校读者我要写书评

暂无评论

fpt algorithms to Enumerate and Count Acyclic and Totally Cyclic Orientations 10th

FPT Algorithms to Enumerate and Count Acyclic and Totally Cy...

引用

10th Latin and American algorithms, Graphs, and Optimization Symposium (LAGOS)

作者： Oliveira, Farley Soares Hiraishi, Hidefumi Imai, Hiroshi Univ Tokyo Dept Comp Sci Tokyo Japan

In this paper, we deal with counting and enumerating problems for two types of graph orientations: acyclic and totally cyclic orientations. Counting is known to be #P-hard for both of them. To circumvent this issue, we propose Fixed Parameter Tractable (fpt) algorithms. For the enumeration task, we construct a Binary Decision Diagram (BDD) to represent all orientations of the two kinds, instead of explicitly enumerating them. We prove that the running time of this construction is bounded by O*(2(pw2/4+o(PW2))) with respect to the pathwidth pw. We then develop faster fpt algorithms to count acyclic and totally acyclic orientations, running in O*(2(bw2/2+o(bw2))) time, where bw denotes the branch-width of the given graph. These counting algorithms are obtained by applying the observations in our enumerating algorithm to branch decomposition.

关键词： Acyclic Orientations Totally Cyclic Orientations Parameterized algorithms fpt algorithms Path-width Branch-width Binary Decision Diagram

来源：评论

学校读者我要写书评

暂无评论

Branch-and-reduce exponential/fpt algorithms in practice: A case study of vertex cover

引用

THEORETICAL COMPUTER SCIENCE 2016年第Part1期609卷 211-225页

作者： Akiba, Takuya Iwata, Yoichi Natl Inst Informat Chiyoda Ku Tokyo Japan Univ Tokyo Dept Comp Sci Bunkyo Ku Tokyo Japan

We investigate the gap between theory and practice for exact branching algorithms. In theory, branch-and-reduce algorithms currently have the best time complexity for numerous important problems. On the other hand, in practice, state-of-the-art methods are based on different approaches, and the empirical efficiency of such theoretical algorithms has seldom been investigated probably because they are seemingly inefficient because of the plethora of complex reduction rules. In this paper, we design a branch-and-reduce algorithm for the vertex cover problem using the techniques developed for theoretical algorithms and compare its practical performance with other state-of-the-art empirical methods. The results indicate that branch-and-reduce algorithms are actually quite practical and competitive with other state-of-the-art approaches for several kinds of instances, thus showing the practical impact of theoretical research on branching algorithms. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Branch-and-reduce Vertex cover Exact exponential algorithms fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

0/1/all CSPs, Half-Integral A-path Packing, and Linear-Time fpt algorithms 59

0/1/all CSPs, Half-Integral <i>A</i>-path Packing, and Linea...

引用

59th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Iwata, Yoichi Yamaguchi, Yutaro Yoshida, Yuichi Natl Inst Informat Tokyo Japan Osaka Univ Suita Osaka Japan

ISBN: (纸本)9781538642306

A recent trend in the design of fpt algorithms is exploiting the half-integrality of LP relaxations. In other words, starting with a half-integral optimal solution to an LP relaxation, we assign integral values to variables one-by-one by branch and bound. This technique is general and the resulting time complexity has a low dependency on the parameter. However, the time complexity often becomes a large polynomial in the input size because we need to compute half-integral optimal LP solutions. In this paper, we address this issue by providing an O(km)-time algorithm for solving the LPs arising from various fpt problems, where k is the optimal value and m is the number of edges/constraints. Our algorithm is based on interesting connections among 0/1/all constraints, which has been studied in the field of constraints satisfaction, A-path packing, which has been studied in the field of combinatorial optimization, and the LPs used in fpt algorithms. With the aid of this algorithm, we obtain linear-time fpt algorithms for various problems. The obtained running time for each problem is linear in the input size and has the current smallest dependency on the parameter. Most importantly, instead of using problem-specific approaches, we obtain all of these results by a unified approach, i.e., the branch-and-bound framework combined with the efficient computation of half-integral LPs, which demonstrates its generality.

关键词： fpt algorithms Combinatorial Optimization Half-integrality

来源：评论

学校读者我要写书评

暂无评论

fpt algorithms to Enumerate and Count Acyclic and Totally Cyclic Orientations

引用

Electronic Notes in Theoretical Computer Science 2019年 346卷 655-666页

作者： Farley Soares Oliveira Hidefumi Hiraishi Hiroshi Imai Department of Computer Science The University of Tokyo Tokyo Japan

In this paper, we deal with counting and enumerating problems for two types of graph orientations: acyclic and totally cyclic orientations. Counting is known to be #P-hard for both of them. To circumvent this issue, we propose Fixed Parameter Tractable (fpt) algorithms. For the enumeration task, we construct a Binary Decision Diagram (BDD) to represent all orientations of the two kinds, instead of explicitly enumerating them. We prove that the running time of this construction is bounded by O* (2 pw 2 /4+ o (pw 2 ) ) with respect to the pathwidth pw. We then develop faster fpt algorithms to count acyclic and totally acyclic orientations, running in O* (2 bw 2 /2+o(bw 2 ) ) time, where bw denotes the branch-width of the given graph. These counting algorithms are obtained by applying the observations in our enumerating algorithm to branch decomposition.

关键词： Acyclic Orientations Totally Cyclic Orientations Parameterized algorithms fpt algorithms Path-width Branch-width Binary Decision Diagram

来源：评论

学校读者我要写书评

暂无评论

Tree diet: reducing the treewidth to unlock fpt algorithms in RNA bioinformatics

引用

algorithms FOR MOLECULAR BIOLOGY 2022年第1期17卷 8-8页

作者： Marchand, Bertrand Ponty, Yann Bulteau, Laurent Inst Polytech Paris Ecole Polytech LIX CNRS UMR 7161 Palaiseau France Univ Gustave Eiffel LIGM CNRS F-77454 Marne La Vallee France

Hard graph problems are ubiquitous in Bioinformatics, inspiring the design of specialized Fixed-Parameter Tractable algorithms, many of which rely on a combination of tree-decomposition and dynamic programming. The time/space complexities of such approaches hinge critically on low values for the treewidth tw of the input graph. In order to extend their scope of applicability, we introduce the TREE DIET problem, i.e. the removal of a minimal set of edges such that a given tree-decomposition can be slimmed down to a prescribed treewidth tw'. Our rationale is that the time gained thanks to a smaller treewidth in a parameterized algorithm compensates the extra post-processing needed to take deleted edges into account. Our core result is an fpt dynamic programming algorithm for TREE DIET, using 2(O(tw)) n time and space. We complement this result with parameterized complexity lower-bounds for stronger variants (e.g., NP-hardness when tw' or tw - tw' is constant). We propose a prototype implementation for our approach which we apply on difficult instances of selected RNA-based problems: RNA design, sequence-structure alignment, and search of pseudoknotted RNAs in genomes, revealing very encouraging results. This work paves the way for a wider adoption of tree-decomposition-based algorithms in Bioinformatics.

关键词： RNA treewidth fpt algorithms RNA design structure sequence alignment

来源：评论

学校读者我要写书评

暂无评论

How similar are two elections?

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2025年 150卷

作者： Faliszewski, Piotr Skowron, Piotr Slinko, Arkadii Sornat, Krzysztof Szufa, Stanislaw Talmon, Nimrod AGH Univ Sci & Technol Krakow Poland Univ Warsaw Warsaw Poland Univ Auckland Auckland New Zealand Ben Gurion Univ Negev Beer Sheva Israel

We introduce and study isomorphic distances between ordinal elections (with the same numbers of candidates and voters). The main feature of these distances is that they are invariant to renaming the candidates and voters, and two elections are at distance zero if and only if they are isomorphic. Specifically, we consider isomorphic extensions of distances between preference orders: Given such a distance d, we extend it to distance d-ID between elections by unifying candidate names and finding a matching between the votes, so that the sum of the d-distances between the matched votes is as small as possible. We show that testing isomorphism of two elections can be done in polynomial time so, in principle, such distances can be tractable. Yet, we show that two very natural isomorphic distances are NP-complete and hard to approximate. We attempt to rectify the situation by showing fpt algorithms for several natural parameterizations. (c) 2025 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Elections Distances Election isomorphism Swap distance Spearman distance Approximation fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

Finding disjoint dense clubs in a social network

引用

THEORETICAL COMPUTER SCIENCE 2018年 734卷 15-23页

作者： Zou, Peng Li, Hui Wang, Wencheng Xin, Chunlin Zhu, Binhai Montana State Univ Gianforte Sch Comp Bozeman MT 59717 USA Beijing Univ Chem Technol Dept Comp Sci Beijing Peoples R China Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing Peoples R China Beijing Univ Chem Technol Sch Econ & Management Beijing Peoples R China

In a social network, the trust among its members usually cannot be carried over many hops. So it is important to find disjoint clusters with a small diameter and with a decent size, formally called dense clubs. We focus on handling this NP-complete problem in this paper. First, from the parameterized computational complexity point of view, we show that this problem does not admit a polynomial kernel (implying that it is unlikely to apply some reduction rules to obtain a practically small problem size). Then, we focus on the dual version of the problem, i.e., deleting d vertices to obtain some isolated dense clubs. We show that this dual problem admits a simple fpt algorithm using a bounded search tree method (the running time is still too high for practical datasets). Finally, we combine a simple reduction rule together with two branching rules to obtain a practical solution (verified by extensive testing on practical datasets). (C) 2017 Elsevier B.V. All rights reserved.

关键词： Social networks Clusters Clubs fpt algorithms Kernelization

来源：评论

学校读者我要写书评

暂无评论

Parameterized complexity of a coupled-task scheduling problem

引用

JOURNAL OF SCHEDULING 2019年第3期22卷 305-313页

作者： Bessy, S. Giroudeau, R. LIRMM UMR 5506 Rue Ada F-34392 Montpellier 5 France

In this article, we investigate the parameterized complexity of coupled-task scheduling in the presence of compatibility constraints given by a compatibility graph. In this model, each task contains two sub-tasks delayed by an idle time. Moreover, a sub-task can be performed during the idle time of another task if the two tasks are compatible. We consider a parameterized version of the scheduling problem: is there a schedule in which at least k coupled-tasks have a completion time before a fixed due date? It is known that this problem is NP-complete. We prove that it is fixed-parameter tractable (fpt) parameterized by k the standard parameter if the total duration of each task is bounded by a constant, whereas the problem becomes W[1]-hard otherwise. We also show that in the former case, the problem does not admit a polynomial kernel under some standard complexity assumptions. Moreover, we obtain an fpt algorithm when the problem is parameterized by the size of a vertex cover of the compatibility graph.

关键词： Coupled-task scheduling model fpt algorithms W-hardness Kernel lower bound

来源：评论

学校读者我要写书评

暂无评论

On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties

引用

ALGORITHMICA 2015年第3期72卷 687-713页

作者： Heggernes, Pinar van't Hof, Pim Marx, Daniel Misra, Neeldhara Villanger, Yngve Univ Bergen Dept Informat N-5008 Bergen Norway Hungarian Acad Sci MTA SZTAKI Comp & Automat Res Inst Budapest Hungary Indian Inst Sci Bangalore 560012 Karnataka India

We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221-232, 1985), while for example the problems of finding a minimum s-t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. algorithms 9(4): 30, 2013). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: Finding a minimum c-connected s-t separator is fpt for c=2 and W[1]-hard for any ca parts per thousand yen3. Finding a minimum s-t separator with diameter at most d is W[1]-hard for any da parts per thousand yen2. Finding a minimum r-regular s-t separator is W[1]-hard for any ra parts per thousand yen1. For any decidable graph property, finding a minimum s-t separator with this property is fpt parameterized jointly by the size of the separator and the maximum degree. Finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless .

关键词： Vertex separators Non-hereditary properties Parameterized complexity fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：