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

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

来源：评论

学校读者我要写书评

暂无评论

One Hierarchy Spawns Another: Graph Deconstructions and the complexity Classification of Conjunctive Queries

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2017年第4期18卷 1–37页

作者： Chen, Hubie Mueller, Moritz Univ Basque Country Bilbao Spain Basque Fdn Sci Ikerbasque Bilbao Spain Birkbeck Univ London Dept Comp Sci & Informat Syst Malet St London WC1E 7HX England Univ Vienna Kurt Godel Res Ctr Wahringer Str 25 A-1090 Vienna Austria

We study the problem of conjunctive query evaluation relative to a class of queries. This problem is formulated here as the relational homomorphism problem relative to a class of structures A, in which each instance must be a pair of structures such that the first structure is an element of A. We present a comprehensive complexity classification of these problems, which strongly links graph-theoretic properties of A to the complexity of the corresponding homomorphism problem. In particular, we define a binary relation on graph classes, which is a preorder, and completely describe the resulting hierarchy given by this relation. This relation is defined in terms of a notion that we call graph deconstruction and that is a variant of the well-known notion of tree decomposition. We then use this hierarchy of graph classes to infer a complexity hierarchy of homomorphism problems that is comprehensive up to a computationally very weak notion of reduction, namely, a parameterized version of quantifier-free, first-order reduction. In doing so, we obtain a significantly refined complexity classification of homomorphism problems as well as a unifying, modular, and conceptually clean treatment of existing complexity classifications. We then present and develop the theory of Ehrenfeucht-Fraisse-style pebble games, which solve the homomorphism problems where the cores of the structures in A have bounded tree depth. This condition characterizes those classical homomorphism problems decidable in logarithmic space, assuming a hypothesis from parameterized space complexity. Finally, we use our framework to classify the complexity of model checking existential sentences having bounded quantifier rank.

关键词： Theory Conjunctive queries homomorphisms graph decompositions parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Chain Minors are FPT

引用

ALGORITHMICA 2017年第3期79卷 698-707页

作者： Blasiok, Jaroslaw Kaminski, Marcin Uniwersytet Warszawski Inst Informatyki Warsaw Poland

Given two finite partially ordered sets P and Q, we say that P is a chain minor of Q if there exists a partial function f from the elements of Q to the elements of P such that for every chain in P there is a chain C-Q in Q with the property that f restricted to C-Q is an isomorphism of chains C and C-Q. We give an algorithm to decide whether a partially ordered set P is a chain minor of a partially ordered set Q, which runs in time O(|Q| log |Q|) for every fixed partially ordered set P. This solves an open problem from the monograph by Downey and Fellows (parameterized complexity. Springer, New York, 1999) who asked whether the problem was fixed parameter tractable.

关键词： Partially ordered sets parameterized complexity Data structures and algorithms

来源：评论

学校读者我要写书评

暂无评论

Turing kernelization for finding long paths and cycles in restricted graph classes

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2017年 85卷 18-37页

作者： Jansen, Bart M. P. Eindhoven Univ Technol NL-5600 MB Eindhoven Netherlands

The k-PATH problem asks whether a given undirected graph has a (simple) path of length k. We prove that k-PATH has polynomial-size Turing kernels when restricted to planar graphs, graphs of bounded degree, claw-free graphs, or to K-3,K-t-minor-free graphs. This means that there is an algorithm that, given a k-PATH instance (G, k) belonging to one of these graph classes, computes its answer in polynomial time when given access to an oracle that solves k-PATH instances of size polynomial in k in a single step. Our techniques also apply to k-CYCLE, which asks for a cycle of length at least k. (C) 2016 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Turing kernelization k-PATH Preprocessing

来源：评论

学校读者我要写书评

暂无评论

The complexity of Finding Effectors

引用

THEORY OF COMPUTING SYSTEMS 2017年第2期60卷 253-279页

作者： Bulteau, Laurent Fafianie, Stefan Froese, Vincent Niedermeier, Rolf Talmon, Nimrod Univ Paris Est Marne La Vallee CNRS UMR 8049 IGM LabInfo Marne La Vallee France Univ Bonn Inst Informat Bonn Germany Weizmann Inst Sci Rehovot Israel TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

The NP-hard Effectors problem on directed graphs is motivated by applications in network mining, particularly concerning the analysis of probabilistic information-propagation processes in social networks. In the corresponding model the arcs carry probabilities and there is a probabilistic diffusion process activating nodes by neighboring activated nodes with probabilities as specified by the arcs. The point is to explain a given network activation state as well as possible by using a minimum number of "effector nodes";these are selected before the activation process starts. We correct, complement, and extend previous work from the data mining community by a more thorough computational complexity analysis of Effectors, identifying both tractable and intractable cases. To this end, we also exploit a parameterization measuring the "degree of randomness" (the number of 'really' probabilistic arcs) which might prove useful for analyzing other probabilistic network diffusion problems as well.

关键词： Probabilistic information propagation Influence maximization etwork activation Social networks Exact algorithms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes

引用

JOURNAL OF THE ACM 2018年第2期65卷 10-10页

作者： Fomin, Fedor V. Lokshtanov, Daniel Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway Inst Math Sci Madras 600113 Tamil Nadu India

Two of the most widely used approaches to obtain polynomial-time approximation schemes (PTASs) on planar graphs are the Lipton-Tarjan separator-based approach and Baker's approach. In 2005, Demaine and Hajiaghayi strengthened both approaches using bidimensionality and obtained efficient polynomial-time approximation schemes (EPTASs) for several problems, including CONNECTED DOMINATING SET and FEEDBACK VERTEX SET. In this work, we unify the two strengthened approaches to combine the best of both worlds. We develop a framework allowing the design of EPTAS on classes of graphs with the subquadratic grid minor (SQGM) property. Roughly speaking, a class of graphs has the SQGM property if, for every graph G from the class, the fact that G contains no t x t grid as a minor guarantees that the treewidth of G is subquadratic in t. For example, the class of planar graphs and, more generally, classes of graphs excluding some fixed graph as a minor, have the SQGM property. At the heart of our framework is a decomposition lemma stating that for "most" bidimensional problems on a graph class G with the SQGM property, there is a polynomial-time algorithm that, given a graph G is an element of G as input and an epsilon > 0, outputs a vertex set X of size *** such that the treewidth of G - X is f (epsilon). Here, OPT is the objective function value of the problem in question and f is a function depending only on epsilon. This allows us to obtain EPTASs on (apex)-minor-free graphs for all problems covered by the previous framework as well as for a wide range of packing problems, partial covering problems and problems that are neither closed under taking minors nor contractions. To the best of our knowledge, for many of these problems-including CYCLE PACKING, F-PACKING, F-DELETION, MAX LEAF SPANNING TREE, or PARTIAL r-DOMINATING SET-no EPTASs, even on planar graphs, were previously known. We also prove novel excluded grid theorems in unit disk and map graphs without large cliq

关键词： Algorithms Design Theory Polynomial-time approximation scheme monadic second-order logic parameterized complexity embedded graph bidimensionality treewidth unit disk graph

来源：评论

学校读者我要写书评

暂无评论

1.5D terrain guarding problem parameterized by guard range

引用

THEORETICAL COMPUTER SCIENCE 2017年 661卷 65-69页

作者： Khodakarami, Farnoosh Didehvar, Farzad Mohades, Ali Amirkabir Univ Technol Dept Math & Comp Sci Lab Algorithms & Computat Geometry Tehran Iran

The 1.5D terrain guarding problem examines a 1.5D terrain as an x-monotone polygonal chain in a plane to find the minimum guarding set for a given input terrain. This problem is NP-complete. In real world applications, guard power is limited and can only cover things within a range. Considering this limitation, the present study introduces the "terrain guard range" as a new geometric parameter by discretizing the definition of range, then presents a fixed-parameter algorithm to demonstrate that the 1.5D terrain guarding problem is fixed-parameter tractable with respect to the introduced parameter. (C) 2016 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Dynamic programming Guarding 1.5D terrain

来源：评论

学校读者我要写书评

暂无评论

Paradigms for parameterized Enumeration

引用

THEORY OF COMPUTING SYSTEMS 2017年第4期60卷 737-758页

作者： Creignou, Nadia Meier, Arne Mueller, Julian-Steffen Schmidt, Johannes Vollmer, Heribert Aix Marseille Univ CNRS LIF UMR 7279 163 Av Luminy F-13288 Marseille 9 France Leibniz Univ Hannover Inst Theoret Informat Appelstr 4 D-30167 Hannover Germany Linkoping Univ Dept Comp & Informat Sci SE-58183 Linkoping Sweden

The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of parameterized complexity. First, we define formally different notions of efficient enumeration in the context of parameterized complexity: FPT-enumeration and delayFPT. Second, we show how different algorithmic paradigms can be used in order to get parameter-efficient enumeration algorithms in a number of examples. These paradigms use well-known principles from the design of parameterized decision as well as enumeration techniques, like for instance kernelization and self-reducibility. The concept of kernelization, in particular, leads to a characterization of fixed-parameter tractable enumeration problems. Furthermore, we study the parameterized complexity of enumerating all models of Boolean formulas having weight at least k, where k is the parameter, in the famous Schaefer's framework. We consider propositional formulas that are conjunctions of constraints taken from a fixed finite set I". Given such a formula and an integer k, we are interested in enumerating all the models of the formula that have weight at least k. We obtain a dichotomy classification and prove that, according to the properties of the constraint language I", either one can enumerate all such models in delayFPT, or no such delayFPT enumeration algorithm exists under some complexity-theoretic assumptions.

关键词： parameterized complexity Kernel Enumeration parameterized enumeration Algorithms Self-reducibility

来源：评论

学校读者我要写书评

暂无评论

Polynomial Kernelization for Removing Induced Claws and Diamonds

引用

THEORY OF COMPUTING SYSTEMS 2017年第4期60卷 615-636页

作者： Cygan, Marek Pilipczuk, Marcin Pilipczuk, Michal van Leeuwen, Erik Jan Wrochna, Marcin Univ Warsaw Inst Informat Warsaw Poland Max Planck Inst Informat Saarbrucken Germany

A graph is called {claw,diamond}-free if it contains neither a claw (a K (1,3)) nor a diamond (a K (4) with an edge removed) as an induced subgraph. Equivalently, {claw,diamond}-free graphs are characterized as line graphs of triangle-free graphs, or as linear dominoes (graphs in which every vertex is in at most two maximal cliques and every edge is in exactly one maximal clique). We consider the parameterized complexity of the {claw,diamond}-free Edge Deletion problem, where given a graph G and a parameter k, the question is whether one can remove at most k edges from G to obtain a {claw,diamond}-free graph. Our main result is that this problem admits a polynomial kernel. We complement this result by proving that, even on instances with maximum degree 6, the problem is NP-complete and cannot be solved in time 2(o(k)) . vertical bar V(G)vertical bar(O(1)) unless the Exponential Time Hypothesis fails.

关键词： Edge deletion parameterized complexity Polynomial kernel {claw, diamond}-free graphs

来源：评论

学校读者我要写书评

暂无评论

On optimal approximability results for computing the strong metric dimension

引用

DISCRETE APPLIED MATHEMATICS 2017年 221卷 18-24页

作者： DasGupta, Bhaskar Mobasheri, Nasim Univ Illinois Dept Comp Sci Chicago IL 60607 USA

The strong metric dimension of a graph was first introduced by Sebo and Tannier (2004) as an alternative to the (weak) metric dimension of graphs previously introduced independently by Slater (1975) and by Harary and Melter (1976), and has since been investigated in several research papers. However, the exact worst-case computational complexity of computing the strong metric dimension has remained open beyond being NP-complete. In this communication, we show that the problem of computing the strong metric dimension of a graph of n nodes admits a polynomial-time 2-approximation, admits a O*(2 (0.287n))- time exact computation algorithm, admits a O(1.2738(k) + n k)-time exact computation algorithm if the strong metric dimension is at most k, does not admit a polynomial time (2 - epsilon)-approximation algorithm assuming the unique games conjecture is true, does not admit a polynomial time (10 root 5 - 21 - epsilon)-approximation algorithm assuming P not equal NP, does not admit a O*(2(0(n)))-time exact computation algorithm assuming the exponential time hypothesis is true, and does not admit a O*(n(0(k)))-time exact computation algorithm if the strong metric dimension is at most k assuming the exponential time hypothesis is true. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Strong metric dimension Minimum node cover Approximability Unique games conjecture Exponential time hypothesis parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：