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

The parameterized complexity of counting problems

SIAM JOURNAL ON COMPUTING 2004年第4期33卷 892-922页

作者： Flum, J Grohe, M Univ Freiburg Inst Math Log D-79104 Freiburg Germany Humboldt Univ Inst Informat D-10099 Berlin Germany

We develop a parameterized complexity theory for counting problems. As the basis of this theory, we introduce a hierarchy of parameterized counting complexity classes #W[t], for t greater than or equal to 1, that corresponds to Downey and Fellows's W-hierarchy [R. G. Downey and M. R. Fellows, parameterized complexity, Springer-Verlag, New York, 1999] and we show that a few central W-completeness results for decision problems translate to #W-completeness results for the corresponding counting problems. Counting complexity gets interesting with problems whose decision version is tractable, but whose counting version is hard. Our main result states that counting cycles and paths of length k in both directed and undirected graphs, parameterized by k, is #W[1]-complete. This makes it highly unlikely that these problems are fixed-parameter tractable, even though their decision versions are fixed-parameter tractable. More explicitly, our result shows that most likely there is no f(k) . n(c)-algorithm for counting cycles or paths of length k in a graph of size n for any computable function f : N --> N and constant c, even though there is a 2(O(k)) . n(2.376) algorithm for finding a cycle or path of length k [N. Alon, R. Yuster, and U. Zwick, J. ACM, 42 (1995), pp. 844-856].

关键词： counting complexity parameterized complexity paths and cycles descriptive complexity

来源：评论

学校读者我要写书评

暂无评论

The complexity of homomorphism and constraint satisfaction problems seen from the other side

引用

JOURNAL OF THE ACM 2007年第1期54卷 1-1-1-24页

作者： Grohe, Martin Humboldt Univ Inst Informat D-10099 Berlin Germany

We give a complexity theoretic classification of homomorphism problems for graphs and, more generally, relational structures obtained by restricting the left hand side structure in a homomorphism. For every class C of structures, let HOM(C, -) be the problem of deciding whether a given structure A is an element of C has a homomorphism to a given (arbitrary) structure B. We prove that, under some complexity theoretic assumption from parameterized complexity theory, HOM(C, -) is in polynomial time if and only if C has bounded tree width modulo homomorphic equivalence. Translated into the language of constraint satisfaction problems, our result yields a characterization of the tractable structural restrictions of constraint satisfaction problems. Translated into the language of database theory, it implies a characterization of the tractable instances of the evaluation problem for conjunctive queries over relational databases.

关键词： theory complexity conjunctive queries constraint satisfaction homomorphisms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Longest common subsequence problem for unoriented and cyclic strings

引用

THEORETICAL COMPUTER SCIENCE 2007年第1-3期370卷 1-18页

作者： Nicolas, Francois Rivals, Eric Univ Montpellier 2 LIRMM Dept Comp Sci UMR 5506CNRS F-34392 Montpellier 5 France

Given a finite set of strings X, the LONGEST COMMON SUBSEQUENCE problem (LCS) consists in finding a subsequence common to all strings in X that is of maximal length. LCS is a central problem in stringology and finds broad applications in text compression, conception of error-detecting codes, or biological sequence comparison. However, in numerous contexts, words represent cyclic or unoriented sequences of symbols and LCS must be generalized to consider both orientations and/or all cyclic shifts of the strings involved. This occurs especially in computational biology when genetic material is sequenced from circular DNA or RNA molecules. In this work, we define three variants of LCS when the input words are unoriented and/or cyclic. We show that these problems are NP-hard, and W[1]-hard if parameterized in the number of input strings. These results still hold even if the three LCS variants are restricted to input languages over a binary alphabet. We also settle the parameterized complexity of our problems for most relevant parameters. Moreover, we study the approximability of these problems: we discuss the existence of approximation bounds depending on the cardinality of the alphabet, on the length of the shortest sequence, and on the number of input sequences. For this we prove that MAXIMUM INDEPENDENT SET in r-uniform hypergraphs is W[1]-hard if parameterized in the cardinality of the sought independent set and at least as hard to approximate as MAXIMUM INDEPENDENT SET in graphs. (c) 2006 Elsevier B.V. All rights reserved.

关键词： longest common subsequence LCS cyclic string sequence comparison pattern recognition graph hypergraph maximum stable set maximum independent set approximation parameterized complexity NP-hard w[1]-hard

来源：评论

学校读者我要写书评

暂无评论

A logical approach to multicut problems

引用

INFORMATION PROCESSING LETTERS 2007年第4期103卷 136-141页

作者： Gottlob, Georg Lee, Stephanie Tien Univ Oxford Comp Lab Oxford OX1 3QD England

Multicut problems are well-studied NP-complete problems in the field of network theory. Previously, by using graph theoretic methods, they have been shown to be fixed parameter tractable for different combinations of parameters, but not for any single parameter. In this paper different versions of the multicut problem are expressed in Monadic Second Order Logic (MSO) and an extended version of Courcelle's Theorem due to Amborg, Lagergren and Seese is used to demonstrate that these problems are fixed parameter tractable with respect to the parameter omega*, the treewidth of the input structure. Here, the input structure consists of a set V of vertices with two relations, the edge relation E of the input graph G = (V, E), and a relation H encoding all pairs of vertices to be disconnected. The contribution of this paper is two-fold: to introduce a single parameter for which the major variants of the multicut problem are fixed parameter tractable, and to use multicut problems as examples for demonstrating fruitful practical applications of logical properties and results in network theory. (C) 2007 Elsevier B.V. All rights reserved.

关键词： multicut parameterized complexity fixed-parameter tractability graph algorithms logic complexity networks

来源：评论

学校读者我要写书评

暂无评论

A 2^O(k)poly(n) algorithm for the parameterized Convex Recoloring problem

引用

INFORMATION PROCESSING LETTERS 2007年第2期104卷 53-58页

作者： Razgon, Igor Natl Univ Ireland Univ Coll Cork Dept Comp Sci Cork Ireland

In this paper we present a parameterized algorithm that solves the Convex Recoloring problem for trees in O(256(k) (*) poly(n)). This improves the currently best upper bound of O(k(k/log k)(k) (*) poly(n)) achieved by... 详细信息

关键词： graph algorithms Convex recoloring parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Online promise problems with online width metrics

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2007年第1期73卷 57-72页

作者： Downey, Rodney G. McCartin, Catherine Massey Univ Palmerston North New Zealand Univ Victoria Wellington New Zealand

In this article we consider the application of ideas from parameterized complexity, and topological graph theory, to online problems. We focus on parameterized promise problems, where we are promised that the problem input obeys certain properties, or is presented in a certain fashion. We explore the effects of using graph width metrics as restrictions on the input to online problems. It seems natural to suppose that, for graphs having some form of bounded width, good online algorithms may exist for a number of natural problems. In the work presented we concentrate on online graph coloring problems, where we restrict the allowed input to instances having some form of bounded treewidth or pathwidth. We also consider the effects of restricting the presentation of the input to some form of bounded width decomposition or layout. A consequence of this pan of the work is the clarification of a new parameter for graphs, persistence, which arises naturally in the online setting, and is of interest in its own right. We present some basic results regarding the general recognition of graphs having bounded persistence path decompositions. (C) 2006 Elsevier Inc. All rights reserved.

关键词： parameterized complexity online algorithms online colorings pathwidth treewidth persistence

来源：评论

学校读者我要写书评

暂无评论

Improved fixed parameter tractable algorithms for two "edge" problems: MAXCUT and MAXDAG

引用

INFORMATION PROCESSING LETTERS 2007年第2期104卷 65-72页

作者： Raman, Venkatesh Saurabh, Saket Inst Math Sci Madras 600113 Tamil Nadu India

We give improved parameterized algorithms for two '' edge '' problems MAXCUT and MAXDAG, where the solution sought is a subset of edges. MAXCUT of a graph is a maximum set of edges forming a bipartite subgraph of the given graph. On the other hand, MAXDAG of a directed graph is a set of arcs of maximum size such that the graph induced on these arcs is acyclic. Our algorithms are obtained through new kernelization and efficient exact algorithms for the optimization versions of the problems. More precisely our results include: (i) a kernel with at most alpha k vertices and beta k edges for MAXCUT. Here 0 < alpha <=, 1 and 1 < beta <= 2. Values of alpha and beta depends on the number of vertices and the edges in the graph;(ii) a kernel with at most 4k/3 vertices and 2k edges for MAXDAG;(iii) an O-*(1.2418(k)) parameterized algorithm for MAXCUT in undirected graphs. This improves the O-*(1.4143(k))(1) algorithm presented in [E. Prieto, The method of extremal structure on the k-maximum cut problem, in: The Proceedings of Computing: The Australasian Theory Symposium (CATS), 2005, pp. 119-126];(iv) an O-*(2(k)) algorithm for optimization version of MAXDAG in directed graphs. This is the first such algorithm to the best of our knowledge;(v) an O-*(2(k)) parameterized algorithm for MAXDAG in directed graphs. This improves the previous best of O-*(4(k)) presented in [V. Raman, S. Saurabh, parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458];(vi) an O-*(16(k)) parameterized algorithm to determine whether an oriented graph having m arcs has an acyclic subgraph with at least m/2 + k arcs. This improves the O-*(2(k)) algorithm given in [V. Raman, S. Saurabh, parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458]. In addition, we show that if a directed graph has minimum out degree at least f (n) (some function of n) th

关键词： directed feedback arc set max-cut parameterized complexity exact algorithm graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Representations and Parameterizations of Combinatorial Auctions

Representations and Parameterizations of Combinatorial Aucti...

引用

作者： Loker, David Ryan University of Waterloo

学位级别：master

Combinatorial auctions (CAs) are an important mechanism for allocating multiple items while allowing agents to specify preferences over bundles of items. In order to communicate these preferences, agents submit bids, which consist of one or more items and a value indicating the agent’s preference for these items. The process of determining the allocation of items is known as the winner determination problem (WDP). WDP for CAs is known to be NP-complete in the general *** consider two distinct graph representations of a CA; the bid graph and the item graph. In a bid graph, vertices represent bids, and two vertices are adjacent if and only if the bids share items in common. In an item graph, each vertex represents a unique item, there is a vertex for each item, and any bid submitted by any agent must induce a connected subgraph of the item graph. We introduce a new definition of combinatorialauction equivalence by declaring two CAs equivalent if and only if their bid graphs are *** complexity theory can be used to further distinguish between NP-hardproblems. In order to make use of parameterized complexity theory in the investigation of a problem, we aim to find one or more parameters that describe some aspect of the problem such that if we fix these parameters, then either the problem is still hard (fixed-parameter intractable), or the problem can be solved in polynomial time (fixed-parameter tractable).We analyze WDP using bid graphs from within the formal scope of parameterized complexity theory. This approach has not previously been used to analyze WDP for CAs, although it has been used to solve set packing, which is related to WDP for CAs and is discussed in detail. We investigate a few parameterizations of WDP; some of the parameterizations are shown to be fixed-parameter intractable, while others are fixed-parameter tractable. We also analyze WDP when the graph class of a bid graph is *** also discuss relationships between ite

关键词： combinatorial auctions parameterized complexity bid graphs item graphs

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of vertex colouring

引用

DISCRETE APPLIED MATHEMATICS 2003年第3期127卷 415-429页

作者： Cai, LZ Chinese Univ Hong Kong Dept Comp Sci & Engn Shatin Hong Kong Peoples R China

For a family F of graphs and a nonnegative integer k, F + ke and F - ke, respectively, denote the families of graphs that can be obtained from F graphs by adding and deleting at most k edges, and F + kv denotes the family of graphs that can be made into F graphs by deleting at most k vertices. This paper is mainly concerned with the parameterized complexity of the vertex colouring problem on F + ke, F - ke and F + kv for various families F of graphs. In particular, it is shown that the vertex colouring problem is fixed-parameter tractable (linear time for each fixed k) for split + ke graphs and split - ke graphs, solvable in polynomial time for each fixed k but W[l]-hard for split + kv graphs. Furthermore, the problem is solvable in linear time for bipartite + 1v graphs and bipartite + 2e graphs but, surprisingly, NP-complete for bipartite + 2v graphs and bipartite + 3e graphs. (C) 2002 Published by Elsevier Science B.V.

关键词： vertex colouring fixed-parameter problem parameterized complexity split graph bipartite graph

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2003年第4期67卷 757-771页

作者： Pietrzak, K McGill Univ Computat Biol Lab Montreal PQ Canada

We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W[1]-hard. Unless W[1] = FPT, this rules out the existence of algorithms with time complexity of O(f(k)n(alpha)) for those problems. Here n is the size of the problem instance, alpha is constant, k is the number of strings and f is any function of k. The fixed alphabet version of the LCS problem is of particular interest considering the importance of sequence comparison (e.g. multiple sequence alignment) in the fixed length alphabet world of DNA and protein sequences. (C) 2003 Elsevier Inc. All rights reserved.

关键词： parameterized complexity longest common subsequence shortest common supersequence multiple sequence alignment

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：