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

Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) / 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

作者： Chen, Hubie Univ Basque Country Dept LSI E-20018 San Sebastian Spain Ikerbasque Basque Fdn Sci E-20018 San Sebastian Spain

ISBN: (纸本)9781450328869

We study first-order model checking, by which we refer to the problem of deciding whether or not a given first-order sentence is satisfied by a given finite structure. In particular, we aim to understand on which sets of sentences this problem is tractable, in the sense of parameterized complexity theory. To this end, we define the notion of a graph-like sentence set, which definition is inspired by previous work on first-order model checking wherein the permitted connectives and quantifiers were restricted. Our main theorem is the complete tractability classification of such graph-like sentence sets, which is (to our knowledge) the first complexity classification theorem concerning a class of sentences that has no restriction on the connectives and quantifiers. To present and prove our classification, we introduce and develop a novel complexity-theoretic framework which is built on parameterized complexity and includes new notions of reduction.

关键词： first-order queries query evaluation parameterized complexity treewidth

来源：评论

学校读者我要写书评

暂无评论

Model Checking Existential Logic on Partially Ordered Sets 14

Model Checking Existential Logic on Partially Ordered Sets

引用

Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) / 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

作者： Bova, Simone Ganian, Robert Szeider, Stefan Vienna Univ Technol Vienna Austria

ISBN: (纸本)9781450328869

We study the problem of checking whether an existential sentence (that is, a first-order sentence in prefix form built using existential quantifiers and all Boolean connectives) is true in a finite partially ordered set (in short, a poset). A poset is a reflexive, antisymmetric, and transitive digraph. The problem encompasses the fundamental embedding problem of finding an isomorphic copy of a poset as an induced substructure of another poset. Model checking existential logic is already NP-hard on a fixed poset;thus we investigate structural properties of posets yielding conditions for fixed-parameter tractability when the problem is parameterized by the sentence. We identify width as a central structural property (the width of a poset is the maximum size of a subset of pairwise incomparable elements);our main algorithmic result is that model checking existential logic on classes of finite posets of bounded width is fixed-parameter tractable. We observe a similar phenomenon in classical complexity, where we prove that the isomorphism problem is polynomial-time tractable on classes of posets of bounded width;this settles an open problem in order theory. We surround our main algorithmic result with complexity results on less restricted, natural neighboring classes of finite posets, establishing its tightness in this sense. We also relate our work with (and demonstrate its independence of) fundamental fixedparameter tractability results for model checking on digraphs of bounded degree and bounded clique-width.

关键词： Partially Ordered Sets Model Checking Width parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Paths of Bounded Length and Their Cuts: parameterized complexity and Algorithm

Paths of Bounded Length and Their Cuts: Parameterized Comple...

引用

4th International Workshop on parameterized and Exact Computation

作者： Golovach, Petr A. Thilikos, Dimitrios M. Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway Univ Athens Dept Math Natl & Kapodistrian GR-15784 Athens Greece

ISBN: (纸本)9783642112683

We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem anti 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 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 A: and I and hardness results when the parameter is only one of A: 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.

关键词： Bounded length disjoint paths Bounded length cuts parameterized complexity parameterized Algorithms

来源：评论

学校读者我要写书评

暂无评论

A note on the parameterized complexity of the maximum independent set problem 8

A note on the parameterized complexity of the maximum indepe...

引用

8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2009

作者： Lozin, Vadim V. DIMAP Mathematics Institute University of Warwick Coventry United Kingdom

来源：评论

学校读者我要写书评

暂无评论

Kernelization Lower Bounds Through Colors and IDs

引用

ACM TRANSACTIONS ON ALGORITHMS 2014年第2期11卷 13-13页

作者： Dom, Michael Lokshtanov, Daniel Saurabh, Saket Univ Jena Inst Informat D-07743 Jena Germany Univ Bergen N-5020 Bergen Norway Inst Math Sci Chennai 600113 Tamil Nadu India

In parameterized complexity, each problem instance comes with a parameter k, and a parameterized problem is said to admit a polynomial kernel if there are polynomial time preprocessing rules that reduce the input instance to an instance with size polynomial in k. Many problems have been shown to admit polynomial kernels, but it is only recently that a framework for showing the nonexistence of polynomial kernels for specific problems has been developed by Bodlaender et al. [2009] and Fortnow and Santhanam [2008]. With few exceptions, all known kernelization lower bounds results have been obtained by directly applying this framework. In this article, we show how to combine these results with combinatorial reductions that use colors and IDs in order to prove kernelization lower bounds for a variety of basic problems. To follow we give a summary of our main results. All results are under the assumption that the polynomial hierarchy does not collapse to the third level. -We show that the STEINER TREE problem parameterized by the number of terminals and solution size k, and the CONNECTED VERTEX COVER and CAPACITATED VERTEX COVER problems do not admit a polynomial kernel. The two latter results are surprising because the closely related VERTEX COVER problem admits a kernel with at most 2k vertices. -Alon and Gutner [2008] obtain a k(poly(h)) kernel for DOMINATING SET IN H-MINOR FREE GRAPHS parameterized by h = vertical bar H vertical bar and solution size k, and ask whether kernels of smaller size exist. We partially resolve this question by showing that DOMINATING SET IN H-MINOR FREE GRAPHS does not admit a kernel with size polynomial in k + h. -Harnik and Naor [2007] obtain a "compression algorithm" for the SPARSE SUBSET SUM problem. We show that their algorithm is essentially optimal by showing that the instances cannot be compressed further. -The HITTING SET and SET COVER problems are among the most-studied problems in algorithmics. Both problems admit a kernel of size

关键词： Kernelization lower bounds parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Co-Nondeterminism in Compositions: A Kernelization Lower Bound for a Ramsey-Type Problem

引用

ACM TRANSACTIONS ON ALGORITHMS 2014年第4期10卷 19-19页

作者： Kratsch, Stefan Tech Univ Berlin Dept Software Engn & Theoret Comp Sci Berlin Germany

The field of kernelization offers a rigorous way of studying the ubiquitous technique of data reduction and preprocessing for combinatorially hard problems. A widely accepted definition of useful data reduction is that of a polynomial kernelization where the output instance is guaranteed to be of size polynomial in some parameter of the input. The fairly recent development of a framework for kernelization lower bounds has made this notion even more attractive as we can now classify many problems into admitting or not admitting polynomial kernelizations. The central notion of the framework is that of a polynomial-time composition algorithm due to Bodlaender et al. (ICALP 2008, JSCC 2009): given t input instances, an OR-composition algorithm returns a single-output instance with bounded parameter value that is yes if and only if one of t input instances is yes;it encodes the logical OR of the input instances. Based on a result of Fortnow and Santhanam (STOC 2008, JSCC 2011), Bodlaender et al. show that an OR-composition for an NP-hard problem rules out polynomial kernelizations for it unless NP subset of coNP/poly (which is known to imply a collapse of the polynomial hierarchy). It is implicit in the work of Fortnow and Santhanam that even co-nondeterministic composition algorithms suffice to rule out polynomial kernelizations. This was first observed in unpublished work of Chen and Muller, and it is an explicit conclusion of recent results by Dell and van Melkebeek (STOC 2010). However, in contrast to the numerous applications of deterministic composition, the added power of co-nondeterminism has not yet been harnessed to obtain kernelization lower bounds. In this work, we present the first example of how co-nondeterminism can help to make a composition algorithm. We study the existence of polynomial kernels for a Ramsey-type problem where, given a graph G and an integer k, the question is whether G contains an independent set or a clique of size at least k. It was a

关键词： Algorithms Theory Kernelization parameterized complexity nondeterminism Ramsey numbers

来源：评论

学校读者我要写书评

暂无评论

Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal

引用

ACM TRANSACTIONS ON ALGORITHMS 2014年第4期10卷 20-20页

作者： Kratsch, Stefan Wahlstroem, Magnus Tech Univ Berlin Berlin Germany Max Planck Inst Informat Dresden Germany

The Odd Cycle Transversal problem (OCT) asks whether a given undirected graph can be made bipartite by deleting at most k of its vertices. In a breakthrough result, Reed, Smith, and Vetta (Operations Research Letters, 2004) gave a O(4(k) kmn) time algorithm for it;this also implies that instances of the problem can be reduced to a so-called problem kernel of size O(4(k)) Since then, the existence of a polynomial kernel for OCT (i.e., a kernelization with size bounded polynomially in k) has turned into one of the main open questions in the study of kernelization, open even for the special case of planar input graphs. This work provides the first (randomized) polynomial kernelization for OCT. We introduce a novel kernelization approach based on matroid theory, where we encode all relevant information about a problem instance into a matroid with a representation of size polynomial in k. This represents the first application of matroid theory to kernelization.

关键词： Kernelization parameterized complexity matroids odd cycle transversal

来源：评论

学校读者我要写书评

暂无评论

MODEL CHECKING LOWER BOUNDS FOR SIMPLE GRAPHS

引用

LOGICAL METHODS IN COMPUTER SCIENCE 2014年第1期10卷

作者： Lampis, Michael Kyoto Univ RIMS Kyoto 6068501 Japan

A well-known result by Frick and Grohe shows that deciding FO logic on trees involves a parameter dependence that is a tower of exponentials. Though this lower bound is tight for Courcelle's theorem, it has been evaded by a series of recent meta-theorems for other graph classes. Here we provide some additional non-elementary lower bound results, which are in some sense stronger. Our goal is to explain common traits in these recent meta-theorems and identify barriers to further progress. More specifically, first, we show that on the class of threshold graphs, and therefore also on any union and complement-closed class, there is no model-checking algorithm with elementary parameter dependence even for FO logic. Second, we show that there is no model-checking algorithm with elementary parameter dependence for MSO logic even restricted to paths (or equivalently to unary strings), unless E=NE. As a corollary, we resolve an open problem on the complexity of MSO model-checking on graphs of bounded max-leaf number. Finally, we look at MSO on the class of colored trees of depth d. We show that, assuming the ETH, for every fixed d >= 1 at least d + 1 levels of exponentiation are necessary for this problem, thus showing that the (d + 1)-fold exponential algorithm recently given by Gajarsky and Hlineny is essentially optimal.

关键词： MSO logic Model checking Courcelle's theorem Algorithmic meta-theorems parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses

引用

JOURNAL OF THE ACM 2014年第4期61卷 23-23页

作者： Dell, Holger Van Melkebeek, Dieter Univ Paris Diderot LIAFA F-75205 Paris 13 France Univ Wisconsin Dept Comp Sci Madison WI 53706 USA

Consider the following two-player communication process to decide a language L: The first player holds the entire input x but is polynomially bounded;the second player is computationally unbounded but does not know any part of x;their goal is to decide cooperatively whether x belongs to L at small cost, where the cost measure is the number of bits of communication from the first player to the second player. For any integer d >= 3 and positive real is an element of, we show that, if satisfiability for n-variable d-CNF formulas has a protocol of cost O(n(d-is an element of)), then coNP is in NP/poly, which implies that the polynomial-time hierarchy collapses to its third level. The result even holds when the first player is conondeterministic, and is tight as there exists a trivial protocol for is an element of = 0. Under the hypothesis that coNP is not in NP/poly, our result implies tight lower bounds for parameters of interest in several areas, namely sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs. By reduction, similar results hold for other NP-complete problems For the vertex cover problem on n-vertex d-uniform hypergraphs, this statement holds for any integer d >= 2. The case d = 2 implies that no NP-hard vertex deletion problem based on a graph property that is inherited by subgraphs can have kernels consisting of O(k(2-is an element of)) edges unless coNP is in NP/poly, where k denotes the size of the deletion set. Kernels consisting of O(k(2)) edges are known for several problems in the class, including vertex cover, feedback vertex set, and bounded-degree deletion.

关键词： Algorithms Theory Sparsification kernelization parameterized complexity probabilistically checkable proofs satisfiability vertex cover feedback vertex set hereditary graph properties vertex deletion problems arithmetic progression free sets

来源：评论

学校读者我要写书评

暂无评论

FPT is Characterized by Useful Obstruction Sets: Connecting Algorithms, Kernels, and Quasi-Orders

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2014年第4期6卷 16-16页

作者： Fellows, Michael R. Jansen, Bart M. P. Charles Darwin Univ Parameterized Complex Res Unit Darwin NT Australia Univ Bergen Dept Informat Bergen Norway

Many graph problems were first shown to be fixed-parameter tractable using the results of Robertson and Seymour on graph minors. We show that the combination of finite, computable obstruction sets and efficient order tests is not just one way of obtaining strongly uniform FPT algorithms, but that all of FPT may be captured in this way. Our new characterization of FPT has a strong connection to the theory of kernelization, as we prove that problems with polynomial kernels can be characterized by obstruction sets whose elements have polynomial size. Consequently we investigate the interplay between the sizes of problem kernels and the sizes of the elements of such obstruction sets, obtaining several examples of how results in one area yield new insights in the other. We show how exponential-size minor-minimal obstructions for pathwidth k form the crucial ingredient in a novel OR-cross-composition for k-PATHWIDTH, complementing the trivial AND-composition that is known for this problem. In the other direction, we show that OR-cross-compositions into a parameterized problem can be used to rule out the existence of efficiently generated quasi-orders on its instances that characterize the NO-instances by polynomial-size obstructions.

关键词： Algorithms Theory Kernelization parameterized complexity pathwidth well-quasi-ordering

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：