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

parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover

THEORETICAL COMPUTER SCIENCE 2012年 452卷 39-46页

作者： Damaschke, Peter Molokov, Leonid Chalmers Univ Technol Dept Comp Sci & Engn S-41296 Gothenburg Sweden

We study a novel generalization of the VERTEX COVER problem which is motivated by, e.g., error correction (data cleaning) prior to inference of chemical mixtures by their observable reaction products. We focus on the important case of deciding on one of two candidate substances. This problem has nice graph-theoretic formulations situated between VERTEX COVER and 3-HITTING SET. In order to characterize its parameterized complexity we devise parameter-preserving reductions, and we show that some minimum solution can be computed faster than by solving 3-HITTING SET in general. More explicitly, we introduce the UNION EDITING problem: In a hypergraph with red and blue vertices, edit the colors so that the red set becomes exactly the union of some hyperedges. The case of degree 2 is equivalent to STAR EDITING: in a graph with red and blue edges, edit the colors so that the red set becomes exactly the union of some stars, i.e., vertices with all their incident edges. Our time bound is O*(1.84(c)) where c denotes the total number of recolored edges. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Vertex cover Hitting set Graph editing Error correction parameterized complexity Problem kernel

来源：评论

学校读者我要写书评

暂无评论

Hardness of discrepancy computation and ε-net verification in high dimension

引用

JOURNAL OF complexity 2012年第2期28卷 162-176页

作者： Giannopoulos, Panos Knauer, Christian Wahlstroem, Magnus Werner, Daniel Free Univ Berlin Inst Informat D-14195 Berlin Germany Univ Bayreuth Inst Informat D-95447 Bayreuth Germany Max Planck Inst Informat D-66123 Saarbrucken Germany

Discrepancy measures how uniformly distributed a point set is with respect to a given set of ranges. Depending on the ranges, several variants arise, including star discrepancy, box discrepancy, and discrepancy of halfspaces. These problems are solvable in time n(0(d)), where d is the dimension of the underlying space. As such a dependency on d becomes intractable for high-dimensional data, we ask whether it can be moderated. We answer this question negatively by proving that the canonical decision problems are Will-hard with respect to the dimension, implying that no f(d) . n(0(1))-time algorithm is possible for any function f(d) unless FPT=W[1]. We also discover the Will-hardness of other well known problems, such as determining the largest empty box that contains the origin and is inside the unit cube. This is shown to be hard even to approximate within a factor of 2(n). (C) 2011 Elsevier Inc. All rights reserved.

关键词： Discrepancy Epsilon-nets Geometric dimension parameterized complexity Inapproximability

来源：评论

学校读者我要写书评

暂无评论

Tractability and approximability of maximal strip recovery

引用

THEORETICAL COMPUTER SCIENCE 2012年 440卷 14-28页

作者： Bulteau, Laurent Fertin, Guillaume Jiang, Minghui Rusu, Irena Utah State Univ Dept Comp Sci Logan UT 84322 USA Univ Nantes LINA UMR CNRS 6241 F-44322 Nantes 3 France

An essential task in comparative genomics is to decompose two or more genomes into synteny blocks that are segments of chromosomes with similar contents. Given a set of d genomic maps each containing the same n markers without duplicates, the problem MAXIMAL STRIP RECOVERY (MSR) aims at finding a decomposition of the genomic maps into synteny blocks (strips) of the maximum total length l, by deleting the minimum number k = n - l of markers which are probably noise and ambiguities. In this paper, we present a collection of new or improved FPT and approximation algorithms for MSR and its variants. Our main results include a 2(0(d delta l))poly(nd) time FPT algorithm for delta-gap-MSR-d, a 2.36(k) poly(nd) time FPT algorithm for both CMSR-d and delta-gap-CMSR-d, and a (d + 1.5)-approximation algorithm for both CMSR-d and delta-gap-CMSR-d. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Bioinformatics Comparative genomics Synteny blocks Approximation algorithms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Polynomial Kernelizations for MIN F⁺I ₁ and MAX NP

引用

ALGORITHMICA 2012年第1-2期63卷 532-550页

作者： Kratsch, Stefan Univ Utrecht Utrecht Netherlands

It has been observed in many places that constant-factor approximable problems often admit polynomial or even linear problem kernels for their decision versions, e.g., Vertex Cover, Feedback Vertex Set, and Triangle Packing. While there exist examples like Bin Packing, which does not admit any kernel unless P = NP, there apparently is a strong relation between these two polynomial-time techniques. We add to this picture by showing that the natural decision versions of all problems in two prominent classes of constant-factor approximable problems, namely MIN F+I (1) and MAX NP, admit polynomial problem kernels. Problems in MAX SNP, a subclass of MAX NP, are shown to admit kernels with a linear base set, e.g., the set of vertices of a graph. This extends results of Cai and Chen (J. Comput. Syst. Sci. 54(3): 465-474, 1997), stating that the standard parameterizations of problems in MAX SNP and MIN F+I (1) are fixed-parameter tractable, and complements recent research on problems that do not admit polynomial kernelizations (Bodlaender et al. in J. Comput. Syst. Sci. 75(8): 423-434, 2009).

关键词： Combinatorial optimization Kernelization parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Local search: Is brute-force avoidable?

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第3期78卷 707-719页

作者： Fellows, Michael R. Fomin, Fedor V. Lokshtanov, Daniel Rosamond, Frances Saurabh, Saket Villanger, Yngve Univ Bergen Dept Informat N-5008 Bergen Norway Charles Darwin Univ Darwin NT 0909 Australia Inst Math Sci Madras 600113 Tamil Nadu India

Many local search algorithms are based on searching in the k-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most k elements. As a rule of thumb, the larger k is, the better are the chances of finding an improved solution. However, for inputs of size n, a naive brute-force search of the k-exchange neighborhood requires n(O(k)) time, which is not practical even for very small values of k. We show that for several classes of sparse graphs, including planar graphs, graphs of bounded vertex degree and graphs excluding some fixed graph as a minor, an improved solution in the k-exchange neighborhood for many problems can be found much more efficiently. Our algorithms run in time O(tau(k) . n(c)), where tau is a function depending Only on k and c is a constant independent of k and n. We demonstrate the applicability of this approach on a variety of problems including r-CENTER, VERTEX COVER, ODD CYCLE TRANSVERSAL, MAX-CUT, and MIN-BISECTION. In particular, on planar graphs, all our algorithms searching for a k-local improvement run in time O(2(O(k)) . n(2)), which is polynomial for k = O(log n). We complement these fixed-parameter tractable algorithms for k-local search with parameterized intractability results indicating that brute-force search is unavoidable in more general classes of graphs. (C) 2011 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Local search Local treewidth

来源：评论

学校读者我要写书评

暂无评论

Parameterizing by the Number of Numbers

引用

THEORY OF COMPUTING SYSTEMS 2012年第4期50卷 675-693页

作者： Fellows, Michael R. Gaspers, Serge Rosamond, Frances A. Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria Charles Darwin Univ Sch Engn & IT Darwin NT 0909 Australia

The usefulness of parameterized algorithmics has often depended on what Niedermeier has called "the art of problem parameterization". In this paper we introduce and explore a novel but general form of parameterization: the number of numbers. Several classic numerical problems, such as Subset Sum, Partition, 3-Partition, Numerical 3-Dimensional Matching, and Numerical Matching with Target Sums, have multisets of integers as input. We initiate the study of parameterizing these problems by the number of distinct integers in the input. We rely on an FPT result for Integer Linear Programming Feasibility to show that all the above-mentioned problems are fixed-parameter tractable when parameterized in this way. In various applied settings, problem inputs often consist in part of multisets of integers or multisets of weighted objects (such as edges in a graph, or jobs to be scheduled). Such number-of-numbers parameterized problems often reduce to subproblems about transition systems of various kinds, parameterized by the size of the system description. We consider several core problems of this kind relevant to number-of-numbers parameterization. Our main hardness result considers the problem: given a non-deterministic Mealy machine M (a finite state automaton outputting a letter on each transition), an input word x, and a census requirement c for the output word specifying how many times each letter of the output alphabet should be written, decide whether there exists a computation of M reading x that outputs a word y that meets the requirement c. We show that this problem is hard for W[1]. If the question is whether there exists an input word x such that a computation of M on x outputs a word that meets c, the problem becomes fixed-parameter tractable.

关键词： parameterized complexity Problem parameterization Variety of a multiset Numerical problems

来源：评论

学校读者我要写书评

暂无评论

Augmenting tractable fragments of abstract argumentation

引用

ARTIFICIAL INTELLIGENCE 2012年 186卷 157-173页

作者： Dvorak, Wolfgang Ordyniak, Sebastian Szeider, Stefan Vienna Univ Technol Inst Informat Syst Vienna Austria

We present a new approach to the efficient solution of important computational problems that arise in the context of abstract argumentation. Our approach makes known algorithms defined for restricted fragments generally applicable, at a computational cost that scales with the distance from the fragment. Thus, in a certain sense, we gradually augment tractable fragments. Surprisingly, it turns out that some tractable fragments admit such an augmentation and that others do not. More specifically, we show that the problems of Credulous and Skeptical Acceptance are fixed-parameter tractable when parameterized by the distance from the fragment of acyclic argumentation frameworks-for most semantics. Other tractable fragments such as the fragments of symmetrical and bipartite frameworks seem to prohibit an augmentation: the acceptance problems are already intractable for frameworks at distance 1 from the fragments. For our study we use a broad setting and consider several different semantics. For the algorithmic results we utilize recent advances in fixed-parameter tractability. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Abstract argumentation Backdoors Computational complexity parameterized complexity Fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Editing graphs to satisfy degree constraints: A parameterized approach

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第1期78卷 179-191页

作者： Mathieson, Luke Szeider, Stefan Vienna Univ Technol Inst Informat Syst 184 3 A-1040 Vienna Austria Univ Newcastle CIBM Discipline Comp Sci & Software Engn Callaghan NSW 2308 Australia

We study a wide class of graph editing problems that ask whether a given graph can be modified to satisfy certain degree constraints, using a limited number of vertex deletions. edge deletions, or edge additions. The problems generalize several well-studied problems such as the General Factor Problem and the Regular Subgraph Problem. We classify the parameterized complexity of the considered problems taking upper bounds on the number of editing steps and the maximum degree of the resulting graph as parameters. (C) 2011 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Computational complexity Kernelization Graph editing Regular subgraph General factor

来源：评论

学校读者我要写书评

暂无评论

Fast Minor Testing in Planar Graphs

引用

ALGORITHMICA 2012年第1期64卷 69-84页

作者： Adler, Isolde Dorn, Frederic Fomin, Fedor V. Sau, Ignasi Thilikos, Dimitrios M. Univ Bergen Dept Informat N-5008 Bergen Norway Goethe Univ Frankfurt Inst Informat Frankfurt Germany LIRMM CNRS AlGCo Team Montpellier France Natl & Kapodistrian Univ Athens Dept Math Athens 11528 Greece

Minor Containment is a fundamental problem in Algorithmic Graph Theory used as a subroutine in numerous graph algorithms. A model of a graph H in a graph G is a set of disjoint connected subgraphs of G indexed by the vertices of H, such that if {u,v} is an edge of H, then there is an edge of G between components C (u) and C (v) . A graph H is a minor of G if G contains a model of H as a subgraph. We give an algorithm that, given a planar n-vertex graph G and an h-vertex graph H, either finds in time a model of H in G, or correctly concludes that G does not contain H as a minor. Our algorithm is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs. Our technique is based on a novel approach called partially embedded dynamic programming.

关键词： Graph minors Planar graphs Branchwidth parameterized complexity Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Multivariate complexity Analysis of Swap Bribery

引用

ALGORITHMICA 2012年第1期64卷 126-151页

作者： Dorn, Britta Schlotter, Ildiko Budapest Univ Technol & Econ Dept Comp Sci & Informat Theory H-1117 Budapest Hungary Univ Ulm Fak Math & Wirtschaftswissensch D-89081 Ulm Germany

We consider the computational complexity of a problem modeling bribery in the context of voting systems. In the scenario of Swap Bribery, each voter assigns a certain price for swapping the positions of two consecutive candidates in his preference ranking. The question is whether it is possible, without exceeding a given budget, to bribe the voters in a way that the preferred candidate wins in the election. We initiate a parameterized and multivariate complexity analysis of Swap Bribery, focusing on the case of k-approval. We investigate how different cost functions affect the computational complexity of the problem. We identify a special case of k-approval for which the problem can be solved in polynomial time, whereas we prove NP-hardness for a slightly more general scenario. We obtain fixed-parameter tractability as well as W[1]-hardness results for certain natural parameters.

关键词： Computational social choice parameterized complexity Swap Bribery

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：