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

The Tractability Frontier of Graph-Like First-Order Query Sets

JOURNAL OF THE ACM 2017年第4期64卷 26-26页

作者： Chen, Hubie Univ Basque Country Fac Informat Paseo Manuel de Lardizabal 1 E-20018 San Sebastian Spain Basque Fdn Sci Ikerbasque Bilbao Spain

The focus of this work is 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;the 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 that is built on parameterized complexity and includes new notions of reduction.

关键词： First-order model checking parameterized complexity dichotomy theorem

来源：评论

学校读者我要写书评

暂无评论

Tight Kernel Bounds for Problems on Graphs with Small Degeneracy

引用

ACM TRANSACTIONS ON ALGORITHMS 2017年第3期13卷 43-43页

作者： Cygan, Marek Grandoni, Fabrizio Hermelin, Danny Inst Informat Banacha 2 PL-02097 Warsaw Poland Dalle Molle Inst IDSIA Manno Switzerland IDSIA Galleria 1 CH-6928 Manno Switzerland Ben Gurion Univ Negev Dept Ind Engn & Management POB 653 IL-8410501 Beer Sheva Israel

Kernelization is a strong and widely-applied technique in parameterized complexity. In a nutshell, a kernelization algorithm for a parameterized problem transforms a given instance of the problem into an equivalent instance whose size depends solely on the parameter. Recent years have seen major advances in the study of both upper and lower bound techniques for kernelization, and by now this area has become one of the major research threads in parameterized complexity. In this article, We consider kernelization for problems on d-degenerate graphs, i.e. graphs such that any subgraph contains a vertex of degree at most d. This graph class generalizes many classes of graphs for which effective kernelization is known to exist, e.g. planar graphs, H-minor free graphs, H-topological minor free graphs. We show that for several natural problems on d-degenerate graphs the best known kernelization upper bounds are essentially tight. In particular, using intricate constructions of weak compositions, we prove that unless coNP subset of NP/poly: Dominating Set has no kernels of size O(k((d-1)(d-3)-epsilon)) for any epsilon > 0. The current best upper bound is O(k((d+1)2)) . Independent Dominating Set has no kernels of size O(k(d-4-epsilon)) for any epsilon > 0. The current best upper bound is O(k(d+1)). Induced Matching has no kernels of size O(k(d-3-epsilon)) for any epsilon > 0. The current best upper bound is O(k(d)). To the best of our knowledge, DOMINATING SET is the the first problem where a lower bound with superlinear dependence on d (in the exponent) can be proved. In the last section of the article, we also give simple kernels for CONNECTED VERTEX COVER and CAPACITATED VERTEX COVER of size O(k(d)) and O(k(d+1)), respectively. We show that the latter problem has no kernels of size O(k(d-epsilon)) unless coNP subset of NP/poly by a simple reduction from d-EXACT SET COVER (the same lower bound for CONNECTED VERTEX COVER on d-degenerate graphs is already known).

关键词： parameterized complexity kernelization kernelization lower bounds sparse graphs degenerate graphs weak compositions

来源：评论

学校读者我要写书评

暂无评论

Directed Steiner trees with diffusion costs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第4期32卷 1089-1106页

作者： Watel, Dimitri Weisser, Marc-Antoine Bentz, Cedric Barth, Dominique SUPELEC Syst Sci Dept Comp Sci F-91192 Gif Sur Yvette France CNAM CEDRIC 292 Rue St Martin F-75141 Paris 03 France Univ Versailles 45 Ave Etats Unis F-78035 Versailles France

Given a directed arc-weighted graph G with n nodes, a root r and k terminals, the directed steiner tree problem (DST) consists in finding a minimum-weight tree rooted at r and spanning all the terminals. If this problem has several applications in multicast routing in packet switching networks, the modeling is not adapted anymore in networks based upon the circuit switching principle in which some nodes, called non diffusing nodes, are unable to duplicate packets. We define a more general problem, namely the directed steiner tree with a limited number of diffusing nodes (DSTLD), that enables us to model multicast in a network containing at most d diffusing nodes. We show that DSTLD is XP with respect to d, and use this result to build a -approximation algorithm for DST that is XP in d. We deduce from that result a strong inapproximability property. In particular, we prove that, under the assumption that NP ZTIME , there is no polynomial-time approximation algorithm for DSTLD with ratio . We finally give an evaluation of performances of an exact algorithm dedicated to the case .

关键词： Approximation parameterized complexity Directed steiner tree Diffusing node

来源：评论

学校读者我要写书评

暂无评论

parameterized EXACT AND APPROXIMATION ALGORITHMS FOR MAXIMUM k-SET COVER AND RELATED SATISFIABILITY PROBLEMS

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2016年第3期50卷 227-240页

作者： Bonnet, Edouard Paschos, Vangelis Th. Sikora, Florian Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control Budapest Hungary PSL Res Univ Univ Paris Dauphine CNRS LAMSADE Paris France

Given a family of subsets S over a set of elements X and two integers p and k, max k-set cover consists of finding a subfamilyT subset of S of cardinality at most k, covering at least p elements of X. This problem is W[2]-hard when parameterized by k, and FPT when parameterized by p. We investigate the parameterized approximability of the problem with respect to parameters k and p. Then, we show that max sat-k, a satisfiability problem generalizing max k-set cover, is also FPT with respect to parameter p.

关键词： parameterized complexity parameterized approximation max k-set cover

来源：评论

学校读者我要写书评

暂无评论

parameterized approximation algorithms for packing problems

引用

THEORETICAL COMPUTER SCIENCE 2016年第0期648卷 40-55页

作者： Zehavi, Meirav Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

parameterized Approximation is a topic of considerable interest in the field of parameterized complexity. In the past decade, new color coding-related techniques, including the breakthrough representative sets technique, have been proven extremely powerful in the design of fast parameterized algorithms. Furthermore, packing problems, which are often solved via color coding-related techniques, have enjoyed a race towards obtaining the fastest parameterized algorithms that solve them. Therefore, it is natural to ask whether packing problems admit efficient parameterized approximation algorithms. In this paper, we answer this question affirmatively. We present tradeoffs that improve the running times of algorithms for well-known special cases of the 3-SET k-PACKING problem at the cost of their accuracy. Consider a packing problem for which there is no known algorithm with approximation ratio a, and a parameter k. If the value of an optimal solution is at least k, we seek a solution of value at least alpha k;otherwise, we seek an arbitrary solution. Clearly, if the best known parameterized algorithm that finds a solution of value t runs in time O*(f(t)) for some function f, we are interested in running times better than O*(f(alpha k)). Our main contribution lies in the adaptation of notions fundamental to the representative sets technique to the design of approximation algorithms: We introduce the definition of "approximate lopsided universal sets", combine partial executions of representative sets-based algorithms with approximation algorithms, and adapt the iterative expansion framework (in the context of representative sets) to the design of parameterized approximation algorithms. Our ideas are intuitive, and may be relevant to the design of other parameterized approximation algorithms. (C) 2016 Elsevier B.V. All rights reserved.

关键词： parameterized complexity 3-Set k-packing Universal sets

来源：评论

学校读者我要写书评

暂无评论

High-multiplicity scheduling on one machine with forbidden start and completion times

引用

JOURNAL OF SCHEDULING 2016年第5期19卷 609-616页

作者： Gabay, Michael Rapine, Christophe Brauner, Nadia Univ Grenoble Alpes G SCOP F-38000 Grenoble France CNRS G SCOP F-38000 Grenoble France Univ Lorraine Lab LGIPM Ile Saulcy F-57045 Metz France

We are interested in a single machine scheduling problem where jobs can neither start nor end on some specified instants, and the aim is to minimize the makespan. This problem models the situation where an additional resource, subject to unavailability constraints, is required to start and to finish a job. We consider in this paper the high-multiplicity version of the problem, when the input is given using a compact encoding. We present a polynomial time algorithm for large diversity instances (when the number of different processing times is greater than the number of forbidden instants). We also show that this problem is fixed-parameter tractable when the number of forbidden instants is fixed, regardless of jobs characteristics.

关键词： Scheduling High-multiplicity Availability constraints parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

An FPT algorithm for the vertex cover P₄ problem

引用

DISCRETE APPLIED MATHEMATICS 2016年 200卷 186-190页

作者： Tu, Jianhua Jin, Zemin Beijing Univ Chem Technol Sch Sci Beijing 100029 Peoples R China Zhejiang Normal Univ Dept Math Jinhua 321004 Peoples R China

A subset F of vertices of a graph G is called a vertex cover P-t (VCPt) set if every path of order t in G contains at least one vertex from F. The vertex cover P-t (VCPt) problem is to find a minimum VCPt set in a graph. The VCPt problem is NP -complete for any integer t >= 2. In this paper, we restrict our attention to the VCP4 problem and present an FPT algorithm with runtime O*(3(k)) for the VCP4 problem. The algorithm constructs a VCP4 set of size at most k in a given graph G, or reports that no such VCP4 set exists in G. (C) 2015 Elsevier B:V. All rights reserved.

关键词： Graph algorithms parameterized complexity Vertex cover P-4 problem Iterative compression

来源：评论

学校读者我要写书评

暂无评论

Reducing rank of the adjacency matrix by graph modification

引用

THEORETICAL COMPUTER SCIENCE 2016年 654卷 70-79页

作者： Meesum, S. M. Misra, Pranabendu Saurabh, Saket Inst Math Sci Madras Tamil Nadu India Univ Bergen N-5020 Bergen Norway

The main topic of this article is to study a class of graph modification problems. A typical graph modification problem takes as input a graph G, a positive integer k and the objective is to add/delete k vertices (edges) so that the resulting graph belongs to a particular family, F, of graphs. In general the family F is defined by forbidden subgraph/minor characterization. In this paper rather than taking a structural route to define F, we take algebraic route. More formally, given a fixed positive integer r, we define F-r, as the family of graphs where for each G is an element of (F)r, the rank of the adjacency matrix of G is at most r. Using the family Fr we initiate algorithmic study, both in classical and parameterized complexity, of following graph modification problems: r-RANK VERTEX DELETION, r-RANK EDGE DELETION and r-RANK EDITING. These problems generalize the classical VERTEX COVER problem and a variant of the d-CLUSTER EDITING problem. We first show that all the three problems are NP-Complete. Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time 2(O(k log r))n(O(1)) for r-RANK VERTEX DELETION, and an algorithm for r-RANK EDGE DELETION and r-RANK EDITING running in time 2(O(f(r)root k log k))n(O(1)). We complement our FPT result by designing polynomial kernels for these problems. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Graph modification Rank of adjacency matrix Vertex deletion Edge editing Fixed parameter tractable parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Meta-kernelization with structural parameters

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2016年第2期82卷 333-346页

作者： Ganian, Robert Slivovsky, Friedrich Szeider, Stefan TU Wien Algorithms & Complex Grp A-1040 Vienna Austria

Kernelization is a polynomial-time algorithm that reduces an instance of a parameterized problem to a decision-equivalent instance, the kernel, whose size is bounded by a function of the parameter. In this paper we present meta-theorems that provide polynomial kernels for large classes of graph problems parameterized by a structural parameter of the input graph. Let C be an arbitrary but fixed class of graphs of bounded rank-width (or, equivalently, of bounded clique-width). We define the C-cover number of a graph to be the smallest number of modules its vertex set can be partitioned into, such that each module induces a subgraph that belongs to C. We show that each decision problem on graphs which is expressible in Monadic Second Order (MSO) logic has a polynomial kernel with a linear number of vertices when parameterized by the C-cover number. We provide similar results for MSO expressible optimization and modulo-counting problems. (C) 2015 Elsevier Inc. All rights reserved.

关键词： parameterized complexity Kernelization Rank-width Clique-width Boolean-width Monadic second-order logic Modular decomposition

来源：评论

学校读者我要写书评

暂无评论

On the Computational complexity of Vertex Integrity and Component Order Connectivity

引用

ALGORITHMICA 2016年第4期76卷 1181-1202页

作者： Drange, Pal Gronas Dregi, Markus van 't Hof, Pim Univ Bergen Bergen Norway

The Weighted Vertex Integrity (wVI) problem takes as input an n-vertex graph G, a weight function , and an integer p. The task is to decide if there exists a set such that the weight of X plus the weight of a heaviest component of is at most p. Among other results, we prove thatwVI is NP-complete on co-bipartite graphs, even if each vertex has weight 1;wVI can be solved in time;wVI admits a kernel with at most vertices. wCOC can be solved in time on interval graphs, while the unweighted version can be solved in time on this graph class;wCOC is W[1]-hard on split graphs when parameterized by k or by;wCOC can be solved in time;wCOC admits a kernel with at most vertices. Result (1) refutes a conjecture by Ray and Deogun (J Comb Math Comb Comput 16: 65-73, 1994) and answers an open question by Ray et al. (Ars Comb 79: 77-95, 2006). It also complements a result by Kratsch et al. (Discret Appl Math 77(3): 259270, 1997), stating that the unweighted version of the problem can be solved in polynomial time on co-comparability graphs of bounded dimension, provided that an intersection model of the input graph is given as part of the input. An instance of the Weighted Component Order Connectivity (wCOC) problem consists of an nvertex graph G, a weight function w : V(G). N, and two integers k and, and the task is to decide if there exists a set X. V(G) such that the weight of X is at most k and the weight of a heaviest component of G -X is at most. In some sense, the wCOC problem can be seen as a refined version of the wVI problem. We obtain several classical and parameterized complexity results on thewCOC problem, uncovering interesting similarities and differences between wCOC and wVI. We prove, among other results, that: (4) wCOC can be solved in O(min{k, n3) time on interval graphs, while the unweighted version can be solved in O(n2) time on this graph class;(5) wCOC is W[ 1]-hard on split graphs when parameterized by k or by (6) wCOC can be solved in 2O(k log ) n time;(7) w

关键词： Graph vulnerability parameterized complexity complexity Graph algorithms Preprocessing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：