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

A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph

INFORMATION PROCESSING LETTERS 2021年 171卷 106137-106137页

作者： Ohsaka, Naoto NEC Corp Ltd Kawasaki Kanagawa 2118666 Japan

We consider the problem of counting the number of vertices reachable from each vertex in a digraph G, which is equal to computing all the out-degrees of the transitive closure of G. The current (theoretically) fastest algorithms run in quadratic time;however, Borassi has shown that this problem is not solvable in truly subquadratic time unless the Strong Exponential Time Hypothesis fails [Borassi, 2016 [13]]. In this paper, we present an O(f(3)n)-time exact algorithm, where n is the number of vertices in G and f is the feedback edge number of G. Our algorithm thus runs in truly subquadratic time for digraphs of f = O(f(1/3-epsilon)) for any epsilon > 0, i.e., the number of edges is n plus O(f(1/3-epsilon)), and is filly polynomial fixed parameter tractable, the notion of which was first introduced by Fomin et al. (2018) [22]. We also show that the same result holds for vertex-weighted digraphs, where the task is to compute the total weights of vertices reachable from each vertex. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Reachability Transitive closure parameterized algorithms FPT in P

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of finding minimum bounded chains

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2024年 122卷

作者： Blaser, Nello Brun, Morten Salbu, Lars M. Vagset, Erlend Raa Univ Bergen Dept Informat Bergen Norway Univ Bergen Dept Math Bergen Norway Univ Bergen Ctr Data Sci Bergen Norway Western Norway Univ Appl Sci Dept Comp Sci Elect Engn & Math Sci Forde Norway

Finding the smallest d-chain with a specific (d - 1)-boundary in a simplicial complex is known as the Minimum Bounded Chain problem (MBCd). MBCd is NP-hard for all d >= 2. In this paper, we prove that it is also W[1]-hard for all d >= 2, if we parameterize the problem by solution size. We also give an algorithm solving MBC1 in polynomial time and introduce and implement two fixed parameter tractable (FPT) algorithms solving MBCd for all d. The first algorithm uses a shortest path approach and is parameterized by solution size and coface degree. The second algorithm is a dynamic programming approach based on treewidth, which has the same runtime as a lower bound we prove under the exponential time hypothesis.(c) 2024 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license(http://***/licenses/by/4.0/).

关键词： Minimum bounded chain Computational topology parameterized algorithms Complexity theory Topological data analysis Treewidth

来源：评论

学校读者我要写书评

暂无评论

A simple and improved parameterized algorithm for bicluster editing

引用

INFORMATION PROCESSING LETTERS 2022年 174卷

作者： Xiao, Mingyu Kou, Shaowei Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

CLUSTER EDITING and BICLUSTER EDITING are classical problems having various applications in computational biology and many other areas. BICLUSTER EDITING asks whether we can transform a bipartite graph into a disjoint union of bicliques by adding and deleting at most kedges. In this paper, we give a branch-and-reduce algorithm for BICLUSTER EDITING that runs in O*(2.9312(k)) time and polynomial space, improving the previous running-time bound of O*(3.24(k)). (C) 2021 Elsevier B.V. All rights reserved.

关键词： parameterized algorithms Analysis of algorithms Bicluster editing Branch-and-reduce

来源：评论

学校读者我要写书评

暂无评论

A parameterized Measure-and-Conquer Analysis for Finding a k-Leaf Spanning Tree in an Undirected Graph

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2014年第1期16卷 179-200页

作者： Binkele-Raible, Daniel Fernau, Henning Univ Trier Abt Informat Wissensch Trier Germany

The problem of finding a spanning tree in an undirected graph with a maximum number of leaves is known to be NP-hard. We present an algorithm which finds a spanning tree with at least k leaves in time O*(3.4575(k)) which improves the currently best algorithm. The estimation of the running time is done by using a non-standard measure. The present paper is one of the still few examples that employ the Measure & Conquer paradigm of algorithm analysis in the area of parameterized Algorithmics.

关键词： parameterized algorithms measure-and-conquer analysis maximum leaf spanning tree

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Techniques for practical fixed-parameter algorithms

引用

COMPUTER JOURNAL 2008年第1期51卷 7-25页

作者： Hueffner, Falk Niedermeier, Rolf Wernicke, Sebastian Univ Jena Inst Informat D-07743 Jena Germany

The fixed-parameter approach is an algorithm design technique for solving combinatorially hard ( mostly NP-hard) problems. For some of these problems, it can lead to algorithms that are both efficient and yet at the same time guaranteed to find optimal solutions. Focusing on their application to solving NP-hard problems in practice, we survey three main techniques to develop fixed-parameter algorithms, namely: kernelization ( data reduction with provable performance guarantee), depth-bounded search trees and a new technique called iterative compression. Our discussion is circumstantiated by several concrete case studies and provides pointers to various current challenges in the field.

关键词： parameterized algorithms fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

On Two Techniques of Combining Branching and Treewidth

引用

ALGORITHMICA 2009年第2期54卷 181-207页

作者： Fomin, Fedor V. Gaspers, Serge Saurabh, Saket Stepanov, Alexey A. Univ Bergen Dept Informat N-5020 Bergen Norway Inst Math Sci Chennai 600113 Tamil Nadu India

Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used in the design of moderately exponential time exact algorithms for NP hard problems. In this paper we discuss the efficiency of simple algorithms based on combinations of these techniques. The idea behind these algorithms is very natural: If a parameter like the treewidth of a graph is small, algorithms based on dynamic programming perform well. On the other side, if the treewidth is large, then there must be vertices of high degree in the graph, which is good for branching algorithms. We give several examples of possible combinations of branching and programming which provide the fastest known algorithms for a number of NP hard problems. All our algorithms require non-trivial balancing of these two techniques. In the first approach the algorithm either performs fast branching, or if there is an obstacle for fast branching, this obstacle is used for the construction of a path decomposition of small width for the original graph. Using this approach we give the fastest known algorithms for MINIMUM MAXIMAL MATCHING and for counting all 3-colorings of a graph. In the second approach the branching occurs until the algorithm reaches a subproblem with a small number of edges (and here the right choice of the size of subproblems is crucial) and then dynamic programming is applied on these subproblems of small width. We exemplify this approach by giving the fastest known algorithm to count all minimum weighted dominating sets of a graph. We also discuss how similar techniques can be used to design faster parameterized algorithms.

关键词： Exact exponential time algorithms parameterized algorithms NP hard problems Treewidth #3-Coloring #Minimum dominating set Minimum maximal matching k-Weighted vertex cover

来源：评论

学校读者我要写书评

暂无评论

A parameterized algorithm for subset feedback vertex set in tournaments

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期975卷

作者： Bai, Tian Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

The SUBSET FEEDBACK VERTEX SET problem (SFVS) takes an n-vertex graph G = (V, E), a terminal set T subset of V, and an integer k as the input. The goal is to determine whether there exists a subset S subset of V of at most k vertices whose removal makes no terminal in T contained in a cycle in the remaining graph. When T = V, SFVS degenerates to the classical FEEDBACK VERTEX SET problem (FVS). Both SFVS and FVS have been extensively studied in parameterized algorithms. In this paper, we study parameterized algorithms for SUBSET FEEDBACK VERTEX SET IN TOURNAMENTS (SFVST), i.e., SFVS with the restriction that the input graph is always a tournament. By using the iterative compression method and a novel dynamic programming, we show that SFVST can be solved in 2k+o(k)nO(1) time, improving the bound obtained from 3-HITTINg SET.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Subset feedback vertex set Tournaments parameterized algorithms Iterative compression

来源：评论

学校读者我要写书评

暂无评论

Compactors for parameterized counting problems

引用

COMPUTER SCIENCE REVIEW 2021年 39卷 100344-100344页

作者： Thilikos, Dimitrios M. Univ Montpellier CNRS LIRMM Montpellier France

The concept of compactor has been introduced in Kim et al. (2018) as a general data-reduction concept for parametrized counting problems. For a function F : Sigma* -> N and a parameterization kappa : Sigma* -> N a compactor (C, E) consists of a polynomial-time computable function P, called condenser, and a computable function M, called extractor, such that F = M o P. If the size of P(x) is bounded by a polynomial function of ic(x), then we say that the compactor (C, E) is of polynomial size. Compactors can be seen as an attempt to formalize the notion of preprocessing for counting problems. (C) 2020 Elsevier Inc. All rights reserved.

关键词： parameterized algorithms Counting algorithms Compactor Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized APPROXIMATION SCHEMES FOR STEINER TREES WITH SMALL NUMBER OF STEINER VERTICES

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2021年第1期35卷 546-574页

作者： Dvorak, Pavel Feldmann, Andreas E. Knop, Dusan Masarik, Tomas Toufar, Tomas Vesely, Pavel Charles Univ Prague Comp Sci Inst Prague 11800 Czech Republic Charles Univ Prague Dept Appl Math Prague 11800 Czech Republic Czech Tech Univ Fac Informat Technol Prague 16000 Czech Republic Univ Warsaw Fac Math Informat & Mech PL-02097 Warsaw Poland Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England

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 parameterization. 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 nonterminals (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 none of these is an EPAS 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 approximating within any function of the studied parameter is W[1]-hard. Nevertheless, we show that an EPAS exists for Unweighted Directed Steiner Tree, but a PSAKS does not. We also 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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：