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

Paths of bounded length and their cuts: parameterized complexity and algorithms

DISCRETE OPTIMIZATION 2011年第1期8卷 72-86页

作者： Golovach, Petr A. Thilikos, Dimitrios M. Univ Athens Dept Math GR-15784 Athens Greece Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England

We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem and the bounded length cut problem. From Menger's theorem both problems are equivalent (and computationally easy) in the unbounded case for single source, single target paths. However, in the bounded case, they are combinatorially distinct and are both NP-hard, even to approximate. Our results indicate that a more refined landscape appears when we study these problems with respect to their parameterized complexity. For this, we consider several parameterizations (with respect to the maximum length I of paths, the number k of paths or the size of a cut, and the treewidth of the input graph) of all variants of both problems (edge/vertex-disjoint paths or cuts, directed/undirected). We provide FPT-algorithms (for all variants) when parameterized by both k and I and hardness results when the parameter is only one of k and I. Our results indicate that the bounded length disjoint-path variants are structurally harder than their bounded length cut counterparts. Also, it appears that the edge variants are harder than their vertex-disjoint counterparts when parameterized by the treewidth of the input graph. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Bounded length disjoint paths Bounded length cuts parameterized complexity parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Graph Editing to a Given Neighbourhood Degree List is Fixed-Parameter Tractable

Graph Editing to a Given Neighbourhood Degree List is Fixed-...

引用

作者： Subramanya, Vijay University of Waterloo

学位级别：硕士

Graph editing problems have a long history and have been widely studied, with applications in biochemistry and complex network analysis. They generally ask whether an input graph can be modified by inserting and deleting vertices and edges to a graph with the desired property. We consider the problem \textsc{Graph-Edit-to-NDL} (GEN) where the goal is to modify to a graph with a given neighbourhood degree list (NDL). The NDL lists the degrees of the neighbours of vertices in a graph, and is a stronger invariant than the degree sequence, which lists the degrees of vertices. We show \textsc{Graph-Edit-to-NDL} is NP-complete and study its parameterized complexity. In parameterized complexity, a problem is said to be fixed-parameter tractable with respect to a parameter if it has a solution whose running time is a function that is polynomial in the input size but possibly superpolynomial in the parameter. Golovach and Mertzios [ICSSR, 2016] studied editing to a graph with a given degree sequence and showed the problem is fixed-parameter tractable when parameterized by $\Delta+\ell$, where $\Delta$ is the maximum degree of the input graph and $\ell$ is the number of edits. We prove \textsc{Graph-Edit-to-NDL} is fixed-parameter tractable when parameterized by $\Delta+\ell$. Furthermore, we consider a harder problem \textsc{Constrained-Graph-Edit-to-NDL} (CGEN) that imposes constraints on the NDLs of intermediate graphs produced in the sequence. We adapt our FPT algorithm for \textsc{Graph-Edit-to-NDL} to solve \textsc{Constrained-Graph-Edit-to-NDL}, which proves \textsc{Constrained-Graph-Edit-to-NDL} is also fixed-parameter tractable when parameterized by $\Delta+\ell$. Our results imply that, for graph properties that can be expressed as properties of NDLs, editing to a graph with such a property is fixed-parameter tractable when parameterized by $\Delta+\ell$. We show that this family of graph properties includes some well-known graph measures used in complex network ana

关键词： Graph editing parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Corrigendum to “parameterized tractability of the maximum-duo preservation string mapping problem” [Theoret. Comput. Sci. 646 (2016) 16–25]

引用

Theoretical Computer Science 2016年 653卷 108-110页

作者： Stefano Beretta Mauro Castelli Riccardo Dondi Dipartimento di Informatica Sistemistica e Comunicazione Università degli Studi di Milano – Bicocca Milano Italy NOVA IMS Universidade Nova de Lisboa Lisboa Portugal Dipartimento di Lettere Filosofia e Comunicazione Università degli Studi di Bergamo Bergamo Italy

This is a corrigendum for our paper [1] , as we have found that the first FPT algorithm for the Maximum-Duo Preservation String Mapping Problem we presented is incorrect. However, we show that, by slightly modifying the color-coding technique on which the algorithm is based, we can fix the error, thus giving a correct FPT algorithm for Maximum-Duo Preservation String Mapping Problem.

关键词： Computational biology Common string partition parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments

引用

ALGORITHMICA 2015年第1期71卷 87-97页

作者： Xiao, Mingyu Guo, Jiong Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China Univ Saarland D-66123 Saarbrucken Germany

The k-feedback arc set problem is to determine whether there is a set F of at most k arcs in a directed graph G such that the removal of F makes G acyclic. The k-feedback arc set problems in tournaments and bipartite tournaments (k-FAST and k-FASBT) have applications in ranking aggregation and have been extensively studied from the viewpoint of parameterized complexity. By introducing a new concept called "bimodule", we provide a problem kernel with O(k (2)) vertices for k-FASBT, which improves the previous result by a factor of k.

关键词： Kernelization Feedback arc set Bipartite tournament Graph algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable

引用

ACM TRANSACTIONS ON algorithms 2015年第4期11卷 1–28页

作者： Chitnis, Rajesh Cygan, Marek Hajiaghayi, Mohammataghi Marx, Daniel Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Warsaw Inst Informat PL-02097 Warsaw Poland Hungarian Acad Sci Inst Comp Sci & Control H-1111 Budapest Hungary

Given a graph G and an integer k, the FEEDBACK VERTEX SET (FVS) problem asks if there is a vertex set T of size at most k that hits all cycles in the graph. The first fixed-parameter algorithm for FVS in undirected graphs appeared in a monograph of Mehlhorn in 1984. The fixed-parameter tractability (FPT) status of FVS in directed graphs was a long-standing open problem until Chen et al. (STOC '08, JACM '08) showed that it is fixed-parameter tractable by giving a 4(k)k! . n(O(1)) time algorithm. There are two subset versions of this problems: We are given an additional subset S of vertices (resp., edges), and we want to hit all cycles passing through a vertex of S (resp., an edge of S);the two variants are known to be equivalent in the parameterized sense. Recently, the SUBSET FVS problem in undirected graphs was shown to be FPT by Cygan et al. (ICALP'11, SIDMA'13) and independently by Kakimura et al. (SODA '12). We generalize the result of Chen et al. (STOC '08, JACM '08) by showing that a SUBSET FVS in directed graphs can be solved in time 2(O(k3)) . n(O(1)) (i.e., FPT parameterized by size k of the solution). By our result, we complete the picture for FVS problems and their subset versions in undirected and directed graphs. The technique of random sampling of important separators was used by Marx and Razgon (STOC '11, SICOMP '14) to show that UNDIRECTED MULTICUT is FPT, and it was generalized by Chitnis et al. (SODA '12, SICOMP '13) to directed graphs to show that DIRECTEDMULTIWAY CUT is FPT. In addition to proving the FPT of a DIRECTED SUBSET FVS, we reformulate the random sampling of important separators technique in an abstract way that can be used with a general family of transversal problems. We believe this general approach will be useful for showing the FPT of other problems in directed graphs. Moreover, we modify the probability distribution used in the technique to achieve better running time;in particular, this gives an improvement from 2(2O(k)) to 2(O(k

关键词： algorithms Theory parameterized algorithms important separators subset feedback vertex set directed graphs

来源：评论

学校读者我要写书评

暂无评论

On the kernel size of clique cover reductions for random intersection graphs

引用

JOURNAL OF DISCRETE algorithms 2015年 34卷 128-136页

作者： Friedrich, Tobias Hercher, Christian Hasso Plattner Inst Potsdam Germany Univ Jena D-07745 Jena Germany

Covering all edges of a graph by a minimum number of cliques is a well known NP-hard problem. For the parameter k being the maximal number of cliques to be used, the problem becomes fixed parameter tractable. However, assuming the Exponential Time Hypothesis, there is no kernel of subexponential size in the worst-case. We study the average kernel size for random intersection graphs with n vertices, edge probability p, and clique covers of size k. We consider the well-known set of reduction rules of Gramm, Guo, Huffner, and Niedermeier (2009)[17] and show that with high probability they reduce the graph completely if pis bounded away from 1 and k < c log n for some constant c > 0. This shows that for large probabilistic graph classes like random intersection graphs the expected kernel size can be substantially smaller than the known exponential worst-case bounds. (C) 2015 Elsevier B.V. All rights reserved.

关键词： parameterized algorithms Clique cover Kernelization Average case Random intersection graphs Erdos-Renyi graphs

来源：评论

学校读者我要写书评

暂无评论

Parametrized Complexity of Length-Bounded Cuts and Multi-cuts 12

Parametrized Complexity of Length-Bounded Cuts and Multi-cut...

引用

12th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Dvorak, Pavel Knop, Dusan Charles Univ Prague Dept Appl Math CR-11800 Prague Czech Republic

ISBN: (纸本)9783319171425;9783319171418

We show that the minimal length-bounded L-cut can be computed in linear time with respect to L and the tree-width of the input graph as parameters. We derive an FPT algorithm for a more general multi-commodity length bounded cut problem when parameterized by the number of terminals also. For the former problem we show a W[1]-hardness result when the parameterization is done by the path-width only (instead of the tree-width).

关键词： Length bounded cuts parameterized algorithms W[1]-hardness

来源：评论

学校读者我要写书评

暂无评论

The parameterized Complexity of the Shared Center Problem

引用

ALGORITHMICA 2014年第2期69卷 269-293页

作者： Chen, Zhi-Zhong Ma, Wenji Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hiki Saitama 3590394 Japan City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

Recently, the shared center (SC) problem has been proposed as a mathematical model for inferring the allele-sharing status of a given set of individuals using a database of confirmed haplotypes as reference. The problem was proved to be NP-complete and a ratio-2 polynomial-time approximation algorithm was designed for its minimization version (called the closest shared center (CSC) problem). In this paper, we consider the parameterized complexity of the SC problem. First, we show that the SC problem is W[1]-hard with parameters d and n, where d and n are the radius and the number of (diseased or normal) individuals in the input, respectively. Then, we present two asymptotically optimal parameterized algorithms for the problem and apply them to linkage analysis.

关键词： Haplotype inference Linkage analysis Pedigree Allele-sharing status parameterized complexity parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

parameterized Domination in Circle Graphs

引用

THEORY OF COMPUTING SYSTEMS 2014年第1期54卷 45-72页

作者： Bousquet, Nicolas Goncalves, Daniel Mertzios, George B. Paul, Christophe Sau, Ignasi Thomasse, Stephan CNRS LIRMM AlGCo Project Team Montpellier France Univ Durham Sch Engn & Comp Sci Durham England UCBL CNRS ENS Lyon Lab LIPU LyonINRIA Lyon France

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution. Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs. If T is a given tree, deciding whether a circle graph G has a dominating set inducing a graph isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by t=|V(T)|. We prove that the FPT algorithm runs in subexponential time, namely , where n=|V(G)|.

关键词： Circle graphs Domination problems parameterized complexity parameterized algorithms Dynamic programming Constrained domination

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：