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

A fixed-parameter algorithm for minimum quartet inconsistency

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2003年第4期67卷 723-741页

作者： Gramm, J Niedermeier, R Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany

Given n taxa, exactly one topology for every subset of four taxa, and a positive integer k (the parameter), the MINIMUM QUARTET INCONSISTENCY (MQI) problem is the question whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in only k quartet topologies. The more general problem where we are not necessarily given a topology for every subset of four taxa appears to be fixed-parameter intractable. For MQI, however, which is also NP-complete, we can compute the required tree in time O(4(k)n + n(4)). This means that the problem is fixed-parameter tractable and that in the case of a small number k of "errors" the tree reconstruction can be done efficiently. In particular, for minimal k, our algorithm can produce all solutions that resolve k errors. Additionally, we discuss significant heuristic improvements. Experiments underline the practical relevance of our solutions. (C) 2003 Elsevier Inc. All rights reserved.

关键词： computational biology minimum quartet inconsistency parameterized complexity Phylogeny quartet methods

来源：评论

学校读者我要写书评

暂无评论

Meta-kernelization with structural parameters

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2016年第2期82卷 333-346页

作者： Ganian, Robert Slivovsky, Friedrich Szeider, Stefan TU Wien Algorithms & Complex Grp A-1040 Vienna Austria

Kernelization is a polynomial-time algorithm that reduces an instance of a parameterized problem to a decision-equivalent instance, the kernel, whose size is bounded by a function of the parameter. In this paper we present meta-theorems that provide polynomial kernels for large classes of graph problems parameterized by a structural parameter of the input graph. Let C be an arbitrary but fixed class of graphs of bounded rank-width (or, equivalently, of bounded clique-width). We define the C-cover number of a graph to be the smallest number of modules its vertex set can be partitioned into, such that each module induces a subgraph that belongs to C. We show that each decision problem on graphs which is expressible in Monadic Second Order (MSO) logic has a polynomial kernel with a linear number of vertices when parameterized by the C-cover number. We provide similar results for MSO expressible optimization and modulo-counting problems. (C) 2015 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Kernelization Rank-width Clique-width Boolean-width Monadic second-order logic Modular decomposition

来源：评论

学校读者我要写书评

暂无评论

On the Computational complexity of Vertex Integrity and Component Order Connectivity

引用

ALGORITHMICA 2016年第4期76卷 1181-1202页

作者： Drange, Pal Gronas Dregi, Markus van 't Hof, Pim Univ Bergen Bergen Norway

The Weighted Vertex Integrity (wVI) problem takes as input an n-vertex graph G, a weight function , and an integer p. The task is to decide if there exists a set such that the weight of X plus the weight of a heaviest component of is at most p. Among other results, we prove thatwVI is NP-complete on co-bipartite graphs, even if each vertex has weight 1;wVI can be solved in time;wVI admits a kernel with at most vertices. wCOC can be solved in time on interval graphs, while the unweighted version can be solved in time on this graph class;wCOC is W[1]-hard on split graphs when parameterized by k or by;wCOC can be solved in time;wCOC admits a kernel with at most vertices. Result (1) refutes a conjecture by Ray and Deogun (J Comb Math Comb Comput 16: 65-73, 1994) and answers an open question by Ray et al. (Ars Comb 79: 77-95, 2006). It also complements a result by Kratsch et al. (Discret Appl Math 77(3): 259270, 1997), stating that the unweighted version of the problem can be solved in polynomial time on co-comparability graphs of bounded dimension, provided that an intersection model of the input graph is given as part of the input. An instance of the Weighted Component Order Connectivity (wCOC) problem consists of an nvertex graph G, a weight function w : V(G). N, and two integers k and, and the task is to decide if there exists a set X. V(G) such that the weight of X is at most k and the weight of a heaviest component of G -X is at most. In some sense, the wCOC problem can be seen as a refined version of the wVI problem. We obtain several classical and parameterized complexity results on thewCOC problem, uncovering interesting similarities and differences between wCOC and wVI. We prove, among other results, that: (4) wCOC can be solved in O(min{k, n3) time on interval graphs, while the unweighted version can be solved in O(n2) time on this graph class;(5) wCOC is W[ 1]-hard on split graphs when parameterized by k or by (6) wCOC can be solved in 2O(k log ) n time;(7) w

关键词： Graph vulnerability parameterized complexity complexity Graph algorithms Preprocessing

来源：评论

学校读者我要写书评

暂无评论

A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs

引用

ALGORITHMICA 2016年第1期75卷 84-117页

作者： Bruner, Marie-Louise Lackner, Martin Vienna Univ Technol Inst Discrete Math & Geometry A-1040 Vienna Austria Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria

The NP-complete Permutation Pattern Matching problem asks whether a k-permutation P is contained in a n-permutation T as a pattern. This is the case if there exists an order-preserving embedding of P into T. In this paper, we present a fixed-parameter algorithm solving this problem with a worst-case runtime of , where denotes the number of alternating runs of T. This algorithm is particularly well-suited for instances where T has few runs, i.e., few ups and downs. Moreover, since , this can be seen as a algorithm which is the first to beat the exponential runtime of brute-force search. Furthermore, we prove that under standard complexity theoretic assumptions such a fixed-parameter tractability result is not possible for run(P).

关键词： Permutation patterns parameterized complexity Pattern matching Fixed-parameter tractability Exponential algorithms Combinatorics

来源：评论

学校读者我要写书评

暂无评论

Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential parameterized Algorithms

引用

ALGORITHMICA 2019年第10期81卷 3890-3935页

作者： Bonnet, Edouard Brettell, Nick Kwon, O-joung Marx, Daniel Univ Claude Bernard Lyon 1 Univ Lyon CNRS ENS LyonLIP UMR5668 Lyon France Eindhoven Univ Technol Dept Math & Comp Sci Eindhoven Netherlands Incheon Natl Univ Dept Math Incheon South Korea Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control Budapest Hungary

It has long been known that Feedback Vertex Set can be solved in time 2 O-(w log w) n(O(1)) on n-vertex graphs of treewidth w, but it was only recently that this running time was improved to 2(O(w))n(O(1)), that is, to single-exponential parameterized by treewidth. We investigate which generalizations of Feedback Vertex Set can be solved in a similar running time. Formally, for a class P of graphs, the Bounded P-Block Vertex Deletion problem asks, given a graph G on n vertices and positive integers k and d, whether G contains a set S of at most k vertices such that each block of G -S has at most d vertices and is in P. Assuming that P is recognizable in polynomial time and satisfies a certain natural hereditary condition, we give a sharp characterization of when single-exponential parameterized algorithms are possible for fixed values of d: - if P consists only of chordal graphs, then the problem can be solved in time 2(O(wd2))n(O(1)), - if P contains a graph with an induced cycle of length l >= 4, then the problem is not solvable in time 2(o(w log w))n(O(1)) even for fixed d = l, unless the ETH fails. We also study a similar problem, called Bounded P-Component Vertex Deletion, where the target graphs have connected components of small size rather than blocks of small size, and we present analogous results. For this problem, we also show that if d is part of the input and P contains all chordal graphs, then it cannot be solved in time f(w)n(o(w)) for some function f, unless the ETH fails.

关键词： parameterized complexity Feedback Vertex Set Treewidth Chordal graph

来源：评论

学校读者我要写书评

暂无评论

Editing to a Graph of Given Degrees

引用

THEORETICAL COMPUTER SCIENCE 2015年 591卷 72-84页

作者： Golovach, Petr A. Univ Bergen Dept Informat N-5020 Bergen Norway Russian Acad Sci Steklov Inst Math St Petersburg Moscow 117901 Russia

We consider the EDITING TO A GRAPH OF GIVEN DEGREES problem that asks for a graph G, non-negative integers d,k and a function delta: V(G) -> {1, ... , d}, whether it is possible to obtain a graph G' from G such that the degree of v is delta(v) for any vertex v by at most k vertex or edge deletions or edge additions. We construct an FPT-algorithm for EDITING TO A GRAPH OF GIVEN DEGREES parameterized by d + k. We complement this result by showing that the problem has no polynomial kernel unless NP subset of coNP/poly. (C) 2015 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Graph editing Graphs of given degrees

来源：评论

学校读者我要写书评

暂无评论

An improved algorithm for the (n, 3)-MaxSAT problem: asking branchings to satisfy the clauses

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第3期42卷 524-542页

作者： Xu, Chao Li, Wenjun Wang, Jianxin Yang, Yongjie Cent South Univ Sch Comp Sci & Engn Changsha Peoples R China Changsha Univ Sci & Technol Hunan Prov Key Lab Intelligent Proc Big Data Tran Changsha Peoples R China Saarland Univ Econ Theory Saarbrucken Germany

We study the (n, 3)-MaxSAT problem where we are given an integer k and a CNF formula with n variables, each of which appears in at most 3 clauses, and the question is whether there is an assignment that satisfies at least k clauses. Based on refined observations, we propose a branching algorithm for the (n, 3)-MaxSAT problem which significantly improves the previous results. More precisely, the running time of our algorithm can be bounded by O* (1.175(k)) and O* (1.194(n)), respectively. Prior to our study, the running time of the best known exact algorithm can be bounded by O* (1.194(k)) and O*(1.237n), respectively.

关键词： CNF formula 3-SAT Branching algorithm complexity parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Dual Parameterization of Weighted Coloring

引用

ALGORITHMICA 2020年第8期82卷 2316-2336页

作者： Araujo, Julio Campos, Victor A. Lima, Carlos Vinicius G. C. dos Santos, Vinicius Fernandes Sau, Ignasi Silva, Ana Univ Fed Ceara Dept Matemat Fortaleza Ceara Brazil Univ Fed Ceara Dept Comp Fortaleza Ceara Brazil Univ Fed Minas Gerais Dept Ciencia Comp Belo Horizonte MG Brazil Univ Montpellier LIRMM CNRS Montpellier France

Given a graph G, a properk-coloring of G is a partition c=(Si)i is an element of[1,k] of V(G) into k stable sets S1, horizontal ellipsis ,Sk. Given a weight function w:V(G)-> R+, the weight of a colorSi is defined as w(i)=maxv is an element of Siw(v) and the weight of a coloringc as w(c)= n-ary sumation i=1kw(i). Guan and Zhu (Inf Process Lett 61(2):77-81, 1997) defined the weighted chromatic number of a pair (G, w), denoted by sigma(G,w), as the minimum weight of a proper coloring of G. The problem of determining sigma(G,w) has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time no(logn) unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph (G, w) and an integer k, is sigma(G,w)<= n-ary sumation v is an element of V(G)w(v)-k? This parameterization has been recently considered by Escoffier (in: Proceedings of the 42nd international workshop on graph-theoretic concepts in computer science (WG). LNCS, vol 9941, pp 50-61, 2016), who provided an FPT algorithm running in time 2O(klogk)center dot nO(1), and asked which kernel size can be achieved for the problem. We provide an FPT algorithm in time 9k center dot nO(1), and prove that no algorithm in time 2o(k)center dot nO(1) exists under the ETH. On the other hand, we present a kernel with at most (2k-1+1)(k-1) vertices, and rule out the existence of polynomial kernels unless NP subset of coNP/poly, even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

关键词： Weighted coloring Max coloring parameterized complexity Dual parameterization FPT algorithms Polynomial kernels Split graphs Interval graphs

来源：评论

学校读者我要写书评

暂无评论

Graph Isomorphism parameterized by Elimination Distance to Bounded Degree

引用

ALGORITHMICA 2016年第2期75卷 363-382页

作者： Bulian, Jannis Dawar, Anuj Univ Cambridge Comp Lab Pembroke St Cambridge CB2 3QG England

A commonly studied means of parameterizing graph problems is the deletion distance from triviality (Guo et al., parameterized and exact computation, Springer, Berlin, pp. 162-173, 2004), which counts vertices that need to be deleted from a graph to place it in some class for which efficient algorithms are known. In the context of graph isomorphism, we define triviality to mean a graph with maximum degree bounded by a constant, as such graph classes admit polynomial-time isomorphism tests. We generalise deletion distance to a measure we call elimination distance to triviality, based on elimination trees or tree-depth decompositions. We establish that graph canonisation, and thus graph isomorphism, is when parameterized by elimination distance to bounded degree, extending results of Bouland et al. (parameterized and exact computation, Springer, Berlin, pp. 218-230, 2012).

关键词： Graph Isomorphism Canonization parameterized complexity Fixed-parameter tractable Bounded degree Graph theory complexity theory Tree-depth

来源：评论

学校读者我要写书评

暂无评论

A survey of graph layout problems

引用

ACM COMPUTING SURVEYS 2002年第3期34卷 313-356页

作者： Díaz, J Petit, J Serna, M Univ Politecn Cataluna Dept Llenguatges & Sistemes Informat ES-08034 Barcelona Spain

Graph layout problems are a particular class of combinatorial optimization problems whose goal is to find a linear layout of an input graph in such way that a certain objective cost is optimized. This survey considers their motivation, complexity, approximation properties, upper and lower bounds, heuristics and probabilistic analysis on random graphs. The result is a complete view of the current state of the art with respect to layout problems from an algorithmic point of view.

关键词： algorithms experimentation theory approximation algorithms complexity embedding heuristics layout parameterized complexity random graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：