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

Polynomial time approximation schemes and parameterized complexity

DISCRETE APPLIED MATHEMATICS 2007年第2期155卷 180-193页

作者： Chen, Jianer Huang, Xiuzhen Kanj, Iyad A. Xia, Ge Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA Cent S Univ Coll Informat Sci & Engn Changsha 410083 Peoples R China Arkansas State Univ Dept Comp Sci State Univ AR 72467 USA Depaul Univ Sch CTI Chicago IL 60604 USA Lafayette Coll Dept Comp Sci Easton PA 18042 USA

In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce a notion of polynomial fixed-parameter tractability and prove that, under a very general constraint, an NP optimization problem has a fully polynomial time approximation scheme if and only if the problem is polynomial fixed-parameter tractable. By enforcing a constraint of planarity on the W-hierarchy studied in parameterized complexity theory, we obtain a class of NP optimization problems, the planar W-hierarchy, and prove that all problems in this class have efficient polynomial time approximation schemes (EPTAS). The planar W-hierarchy seems to contain most of the known EPTAS problems, and is significantly different from the class introduced by Khanna and Motwani in their efforts in characterizing optimization problems with polynomial time approximation schemes. (c) 2006 Elsevier B.V. All rights reserved.

关键词： approximation algorithm polynomial time approximation scheme parameterized complexity W-hierarchy

来源：评论

学校读者我要写书评

暂无评论

parameterized Algorithmics for Finding Connected Motifs in Biological Networks

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2011年第5期8卷 1296-1308页

作者： Betzler, Nadja van Bevern, Rene Fellows, Michael R. Komusiewicz, Christian Niedermeier, Rolf Tech Univ Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany Charles Darwin Univ Sch Engn & Informat Technol Darwin NT 0909 Australia

We study the NP-hard LIST-COLORED GRAPH MOTIF problem which, given an undirected list-colored graph G = (V, E) and a multiset M of colors, asks for maximum-cardinality sets S subset of V and M' subset of M such that G vertical bar S vertical bar is connected and contains exactly ( with respect to multiplicity) the colors in M'. LIST-COLORED GRAPH MOTIF has applications in the analysis of biological networks. We study LIST-COLORED GRAPH MOTIF with respect to three different parameterizations. For the parameters motif size vertical bar M vertical bar and solution size vertical bar S vertical bar, we present fixed-parameter algorithms, whereas for the parameter vertical bar V vertical bar - vertical bar M vertical bar, we show W[1]-hardness for general instances and achieve fixed-parameter tractability for a special case of LIST-COLORED GRAPH MOTIF. We implemented the fixed-parameter algorithms for parameters vertical bar M vertical bar and vertical bar S vertical bar, developed further speed-up heuristics for these algorithms, and applied them in the context of querying protein-interaction networks, demonstrating their usefulness for realistic instances. Furthermore, we show that extending the request for motif connectedness to stronger demands, such as biconnectedness or bridge-connectedness leads to W[1]-hard problems when the parameter is the motif size vertical bar M vertical bar.

关键词： parameterized complexity color-coding list-colored graphs pattern matching in graphs protein-interaction networks

来源：评论

学校读者我要写书评

暂无评论

Implicit branching and parameterized partial cover problems

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2011年第6期77卷 1159-1171页

作者： Amini, Omid Fomin, Fedor V. Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway Ecole Normale Super CNRS DMA F-75005 Paris France Inst Math Sci Madras 600113 Tamil Nadu India

Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite universe and the goal is to cover the elements of the universe with as few sets of the family as possible. The variations of covering problems include well-known problems like SET COVER, VERTEX COVER, DOMINATING SET and FACILITY LOCATION to name a few. Recently there has been a lot of study on partial covering problems, a natural generalization of covering problems. Here, the goal is not to cover all the elements but to cover the specified number of elements with the minimum number of sets. In this paper we study partial covering problems in graphs in the realm of parameterized complexity. Classical (non-partial) version of all these problems has been intensively studied in planar graphs and in graphs excluding a fixed graph H as a minor. However, the techniques developed for parameterized version of non-partial covering problems cannot be applied directly to their partial counterparts. The approach we use, to show that various partial covering problems are fixed parameter tractable on planar graphs, graphs of bounded local treewidth and graph excluding some graph as a minor, is quite different from previously known techniques. The main idea behind our approach is the concept of implicit branching. We find implicit branching technique to be interesting on its own and believe that it can be used for some other problems. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Graph algorithms parameterized complexity Partial Vertex Cover Dominating Set Planar graphs Minor-free graphs Treewidth

来源：评论

学校读者我要写书评

暂无评论

On the algorithmic effectiveness of digraph decompositions and complexity measures

引用

DISCRETE OPTIMIZATION 2011年第1期8卷 129-138页

作者： Lampis, Michael Kaouri, Georgia Mitsou, Valia CUNY Grad Ctr Dept Comp Sci New York NY 10016 USA Natl Tech Univ Athens Sch Elect & Comp Engn Computat & Reasoning Lab GR-10682 Athens Greece

We place our focus on the gap between treewidth's success in producing fixed-parameter polynomial algorithms for hard graph problems, and specifically HAMILTONIAN CIRCUIT and MAX CUT, and the failure of its directed variants (directed treewidth (Johnson et al., 2001 [13]), DAG-width (Obdrzalek, 20061141) and Kelly-width (Hunter and Kreutzer, 2007[15]) to replicate it in the realm of digraphs. We answer the question of why this gap exists by giving two hardness results: we show that DIRECTED HAMILTONIAN CIRCUIT is W[2]-hard when the parameter is the width of the input graph, for any of these widths, and that MAX DI CUT remains NP-hard even when restricted to DAGs, which have the minimum possible width under all these definitions. Along the way, we extend our reduction for DIRECTED HAMILTONIAN CIRCUIT to show that the related MINIMUM LEAF OUTBRANCHING problem is also W[2]-hard when naturally parameterized by the number of leaves of the solution, even if the input graph has constant width. All our results also apply to directed pathwidth and cycle rank. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Treewidth Digraph decompositions parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Vertex Cover Problem parameterized Above and Below Tight Bounds

引用

THEORY OF COMPUTING SYSTEMS 2011年第2期48卷 402-410页

作者： Gutin, Gregory Kim, Eun Jung Lampis, Michael Mitsou, Valia Univ London Egham TW20 0EX Surrey England CUNY Dept Comp Sci New York NY 10021 USA

We study the well-known Vertex Cover problem parameterized above and below tight bounds. We show that two of the parameterizations (both were suggested by Mahajan et al. in J. Comput. Syst. Sci. 75(2):137-153, 2009) a... 详细信息

关键词： parameterized algorithms parameterized complexity Vertex cover

来源：评论

学校读者我要写书评

暂无评论

Tractable cases of the extended global cardinality constraint

引用

CONSTRAINTS 2011年第1期16卷 1-24页

作者： Samer, Marko Szeider, Stefan Tech Univ Darmstadt Dept Comp Sci Darmstadt Germany Univ Durham Dept Comp Sci Durham England

We study the consistency and domain consistency problem for extended global cardinality (EGC) constraints. An EGC constraint consists of a set X of variables, a set D of values, a domain D(x) subset of D for each variable x, and a "cardinality set" K(d) of non-negative integers for each value d. The problem is to instantiate each variable x with a value in D(x) such that for each value d, the number of variables instantiated with d belongs to the cardinality set K(d). It is known that this problem is NP-complete in general, but solvable in polynomial time if all cardinality sets are intervals. First we pinpoint connections between EGC constraints and general factors in graphs. This allows us to extend the known polynomial-time case to certain non-interval cardinality sets. Second we consider EGC constraints under restrictions in terms of the treewidth of the value graph (the bipartite graph representing variable-value pairs) and the cardinality-width (the largest integer occurring in the cardinality sets). We show that EGC constraints can be solved in polynomial time for instances of bounded treewidth, where the order of the polynomial depends on the treewidth. We show that (subject to the complexity theoretic assumption FPT not equal W[1]) this dependency cannot be avoided without imposing additional restrictions. If, however, also the cardinality-width is bounded, this dependency gets removed and EGC constraints can be solved in linear time.

关键词： Global constraints General factor problem Domain consistency Bounded treewidth parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The complexity of Konig Subgraph Problems and Above-Guarantee Vertex Cover

引用

ALGORITHMICA 2011年第4期61卷 857-881页

作者： Mishra, Sounaka Raman, Venkatesh Saurabh, Saket Sikdar, Somnath Subramanian, C. R. Inst Math Sci Chennai 600113 Tamil Nadu India Indian Inst Technol Dept Math Chennai 600036 Tamil Nadu India Rhein Westfal TH Aachen Dept Comp Sci D-52056 Aachen Germany

A graph is Konig-Egervary if the size of a minimum vertex cover equals that of a maximum matching in the graph. These graphs have been studied extensively from a graph-theoretic point of view. In this paper, we introduce and study the algorithmic complexity of finding Konig-Egervary subgraphs of a given graph. In particular, given a graph G and a nonnegative integer k, we are interested in the following questions: 1. does there exist a set of k vertices (edges) whose deletion makes the graph Konig-Egervary? 2. does there exist a set of k vertices (edges) that induce a Konig-Egervary subgraph?.

关键词： Vertex cover Above guarantee vertex cover Konig graphs Konig vertex/edge deletion sets Maximum matching parameterized complexity Approximation algorithms Unique game conjecture

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds for Kernelizations and Other Preprocessing Procedures

引用

THEORY OF COMPUTING SYSTEMS 2011年第4期48卷 803-839页

作者： Chen, Yijia Flum, Joerg Mueller, Moritz Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai 200240 Peoples R China Univ Freiburg Abt Math Log D-79104 Freiburg Germany Ctr Recerca Matemat Barcelona Bellaterra 08193 Spain

We first present a method to rule out the existence of parameter non-increasing polynomial kernelizations of parameterized problems under the hypothesis P not equal NP. This method is applicable, for example, to the problem SAT parameterized by the number of variables of the input formula. Then we obtain further improvements of corresponding results in (Bodlaender et al. in Lecture Notes in Computer Science, vol. 5125, pp. 563-574, Springer, Berlin, 2008;Fortnow and Santhanam in Proceedings of the 40th ACM Symposium on the Theory of Computing (STOC'08), ACM, New York, pp. 133-142, 2008) by refining the central lemma of their proof method, a lemma due to Fortnow and Santhanam. In particular, assuming that the polynomial hierarchy does not collapse to its third level, we show that every parameterized problem with a "linear OR" and with NP-hard underlying classical problem does not have polynomial self-reductions that assign to every instance x with parameter k an instance y with vertical bar y vertical bar = k(O(1)) . vertical bar x vertical bar(1-epsilon) (here e is any given real number greater than zero). We give various applications of these results. On the structural side we prove several results clarifying the relationship between the different notions of pre-processing procedures, namely the various notions of kernelizations, self-reductions and compressions.

关键词： Kernelization parameterized complexity Lower bound

来源：评论

学校读者我要写书评

暂无评论

Haplotype Inference Constrained by Plausible Haplotype Data

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2011年第6期8卷 1692-1699页

作者： Fellows, Michael R. Hartman, Tzvika Hermelin, Danny Landau, Gad M. Rosamond, Frances Rozenberg, Liat Charles Darwin Univ Darwin NT 0909 Australia Google Tel Aviv Israel Max Planck Inst Informat Saarbrucken Germany Univ Haifa IL-31999 Haifa Israel Polytech Univ New York NY USA IBM Corp Haifa Israel

The haplotype inference problem (HIP) asks to find a set of haplotypes which resolve a given set of genotypes. This problem is important in practical fields such as the investigation of diseases or other types of genetic mutations. In order to find the haplotypes which are as close as possible to the real set of haplotypes that comprise the genotypes, two models have been suggested which are by now well-studied: The perfect phylogeny model and the pure parsimony model. All known algorithms up till now for haplotype inference may find haplotypes that are not necessarily plausible, i.e., very rare haplotypes or haplotypes that were never observed in the population. In order to overcome this disadvantage, we study in this paper, a new constrained version of HIP under the above-mentioned models. In this new version, a pool of plausible haplotypes (H) over tilde is given together with the set of genotypes G, and the goal is to find a subset H subset of (H) over tilde that resolves G. For constrained perfect phylogeny haplotyping (CPPH), we provide initial insights and polynomial-time algorithms for some restricted cases of the problem. For constrained parsimony haplotyping (CPH), we show that the problem is fixed parameter tractable when parameterized by the size of the solution set of haplotypes.

关键词： Haplotyping perfect phylogeny pure parsimony polynomial-time algorithms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Editing Graphs into Disjoint Unions of Dense Clusters

引用

ALGORITHMICA 2011年第4期61卷 949-970页

作者： Guo, Jiong Kanj, Iyad A. Komusiewicz, Christian Uhlmann, Johannes Univ Jena Inst Informat D-07743 Jena Germany Univ Saarland D-66123 Saarbrucken Germany Depaul Univ Sch Comp Chicago IL 60604 USA

In the I -Cluster Editing problem, one is given an undirected graph G, a density measure I , and an integer ka parts per thousand yen0, and needs to decide whether it is possible to transform G by editing (deleting and inserting) at most k edges into a dense cluster graph. Herein, a dense cluster graph is a graph in which every connected component K=(V (K) ,E (K) ) satisfies I . The well-studied Cluster Editing problem is a special case of this problem with I :="being a clique". In this work, we consider three other density measures that generalize cliques: (1) having at most s missing edges (s-defective cliques), (2) having average degree at least |V (K) |-s (average-s-plexes), and (3) having average degree at least mu a <...(|V (K) |-1) (mu-cliques), where s and mu are a fixed integer and a fixed rational number, respectively. We first show that the I -Cluster Editing problem is NP-complete for all three density measures. Then, we study the fixed-parameter tractability of the three clustering problems, showing that the first two problems are fixed-parameter tractable with respect to the parameter (s,k) and that the third problem is W[1]-hard with respect to the parameter k for 0

关键词： CLUSTER EDITING parameterized complexity Data reduction Forbidden subgraph characterization NP-hardness Clique relaxations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：