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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Fixed-parameter tractability, definability, and model-checking

引用

SIAM JOURNAL ON COMPUTING 2001年第1期31卷 113-145页

作者： Flum, J Grohe, M Inst Math Log D-79104 Freiburg Germany Univ Illinois Dept Math Stat & Comp Sci Chicago IL 60607 USA

In this article, we study parameterized complexity theory from the perspective of logic, or more specifically, descriptive complexity theory. We propose to consider parameterized model-checking problems for various fragments of first-order logic as generic parameterized problems and show how this approach can be useful in studying both fixed-parameter tractability and intractability. For example, we establish the equivalence between the model-checking for existential first-order logic, the homomorphism problem for relational structures, and the substructure isomorphism problem. Our main tractability result shows that model-checking for first-order formulas is fixed-parameter tractable when restricted to a class of input structures with an excluded minor. On the intractability side, for every t greater than or equal to 0 we prove an equivalence between model-checking for first-order formulas with t quanti er alternations and the parameterized halting problem for alternating Turing machines with t alternations. We discuss the close connection between this alternation hierarchy and Downey and Fellows W-hierarchy. On a more abstract level, we consider two forms of definability, called Fagin definability and slicewise definability, that are appropriate for describing parameterized problems. We give a characterization of the class FPT of all fixed-parameter tractable problems in terms of slicewise definability in finite variable least fixed-point logic, which is reminiscent of the Immerman-Vardi theorem characterizing the class PTIME in terms of definability in least fixed-point logic.

关键词： parameterized complexity model-checking descriptive complexity

来源：评论

学校读者我要写书评

暂无评论

The parameterized Hardness of the k-Center Problem in Transportation Networks

引用

ALGORITHMICA 2020年第7期82卷 1989-2005页

作者： Feldmann, Andreas Emil Marx, Daniel Charles Univ Prague Dept Appl Math Prague Czech Republic Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control Budapest Hungary

In this paper we study the hardness of the k-Center problem on inputs that model transportation networks. For the problem, a graph G = (V, E) with edge lengths and an integer k are given and a center set C subset of V needs to be chosen such that vertical bar C vertical bar <= k. The aim is to minimize the maximum distance of any vertex in the graph to the closest center. This problem arises in many applications of logistics, and thus it is natural to consider inputs that model transportation networks. Such inputs are often assumed to be planar graphs, low doubling metrics, or bounded highway dimension graphs. For each of these models, parameterized approximation algorithms have been shown to exist. We complement these results by proving that the k-Center problem is W[1]-hard on planar graphs of constant doubling dimension, where the parameter is the combination of the number of centers k, the highway dimension h, and the pathwidth p. Moreover, under the exponential time hypothesis there is no f (k, p, h) center dot n(o(p+root k+h)) time algorithm for any computable function f. Thus it is unlikely that the optimum solution to k-Center can be found efficiently, even when assuming that the input graph abides to all of the above models for transportation networks at once! Additionally we give a simple parameterized (1 + epsilon)-approximation algorithm for inputs of doubling dimension d with runtime (k(k)/epsilon(O(kd))) center dot n(O(1)). This generalizes a previous result, which considered inputs in D-dimensional L-q metrics.

关键词： k-Center problem parameterized complexity Planar graphs Highway dimension Doubling dimension Pathwidth

来源：评论

学校读者我要写书评

暂无评论

parameterized maximum path coloring

引用

THEORETICAL COMPUTER SCIENCE 2013年 511卷 42-53页

作者： Lampis, Michael CUNY Grad Ctr New York NY 10016 USA

We study the well-known MAX PATH COLORING problem from a parameterized point of view, focusing on trees and low-treewidth networks. We observe the existence of a variety of reasonable parameters for the problem, such as the maximum degree and treewidth of the network graph, the number of available colors and the number of requests one seeks to satisfy or reject. In an effort to understand the impact of each of these parameters on the problem's complexity we study various parameterized versions of the problem deriving fixed-parameter tractability and hardness results both for undirected and bi-directed graphs. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Path coloring EPT graphs parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The complexity of homomorphism and constraint satisfaction problems seen from the other side

引用

JOURNAL OF THE ACM 2007年第1期54卷 1-1-1-24页

作者： Grohe, Martin Humboldt Univ Inst Informat D-10099 Berlin Germany

We give a complexity theoretic classification of homomorphism problems for graphs and, more generally, relational structures obtained by restricting the left hand side structure in a homomorphism. For every class C of structures, let HOM(C, -) be the problem of deciding whether a given structure A is an element of C has a homomorphism to a given (arbitrary) structure B. We prove that, under some complexity theoretic assumption from parameterized complexity theory, HOM(C, -) is in polynomial time if and only if C has bounded tree width modulo homomorphic equivalence. Translated into the language of constraint satisfaction problems, our result yields a characterization of the tractable structural restrictions of constraint satisfaction problems. Translated into the language of database theory, it implies a characterization of the tractable instances of the evaluation problem for conjunctive queries over relational databases.

关键词： theory complexity conjunctive queries constraint satisfaction homomorphisms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Collapsing the Tower-On the complexity of Multistage Stochastic IPs

引用

ACM TRANSACTIONS ON ALGORITHMS 2024年第3期20卷 1-21页

作者： Klein, Kim-manuel Reuter, Janina Univ Kiel Christian Albrechts Pl 4 D-24118 Kiel Germany

In this article, we study the computational complexity of solving a class of block structured integer programs (IPs), the so-called multistage stochastic IPs. A multistage stochastic IP is an IP of the form min { cTx T x | Ax = b, , x >= 0 , x integral } where the constraint matrix A consists of small block matrices ordered on the diagonal line, and for each stage there are larger blocks with few columns connecting the blocks in a treelike fashion. Over the past few years there was enormous progress in the area of block structured IPs. For many of the known block IP classes, such as n-fold, tree-fold, and two-stage stochastic IPs, nearly matching upper and lower bounds are known concerning their computational complexity. One of the major gaps that remained, however, was the parameter dependency in the running time for an algorithm solving multistage stochastic IPs. Previous algorithms require a tower of t exponentials, where t is the number of stages. In contrast, only a double exponential lower bound was known based on the exponential time hypothesis. In this article, we show that the tower of t exponentials is actually not necessary. We show an improved running time of 2 (d l1 A l infinity ) O(d 3 t +1 ) r n logO(2d)(r n) O (2 d ) (r n) for the algorithm solving multistage stochastic IPs, where d is the sum of columns in the connecting blocks and rn is the number of rows. Hence, we obtain the first bound by an elementary function for the running time of an algorithm solving multistage stochastic IPs. In contrast to previous works, our algorithm has only a triple exponential dependency on the parameters and only doubly exponential for every constant t. By this, we come very close to the known double exponential bound that holds already for two-stage stochastic IPs, i.e., multistage stochastic IPs with two stages. The improved running time of the algorithm is based on new bounds for the proximity of multistage stochastic IPs. The idea behind the bound i

关键词： Multistage stochastic integer programming parameterized complexity stochastic programming

来源：评论

学校读者我要写书评

暂无评论

Above guarantee parameterization for vertex cover on graphs with maximum degree 4

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第1期45卷 1-15页

作者： Tsur, Dekel Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

In the vertex cover problem the input is a graph G and an integer k, and the goal is to decide whether there is a set of vertices S of size at most k such that every edge of G is incident on at least one vertex in S. We study the vertex cover problem on graphs with maximum degree 4 and minimum degree at least 2, parameterized by r = k -n/3. We give an algorithm for this problem whose running time is O*(1.6253r). As a corollary, we obtain an O*(1.2403k)-time algorithm for vertex cover on graphs with maximum degree 4.

关键词： Vertex cover Graph algorithms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for vertex partitioning problems parameterized by clique-width

引用

THEORETICAL COMPUTER SCIENCE 2014年 535卷 16-24页

作者： Oum, Sang-il Saether, Sigve Hortemo Vatshelle, Martin Korea Adv Inst Sci & Technol Dept Math Sci Taejon 305701 South Korea Univ Bergen Dept Informat N-5020 Bergen Norway

Many NP-hard problems, such as DOMINATING SET, are FPT parameterized by clique-width. For graphs of clique-width k given with a k-expression, DOMINATING SET can be solved in 4(k)n(O(1)) time. However, no FPT algorithm is known for computing an optimal k-expression. For a graph of clique-width k, if we rely on known algorithms to compute a (2(3k)-1)-expression via rank-width and then solving DOMINATING SET using the (2(3k)-1)-expression, the above algorithm will only give a runtime of 4(23k)n(O(1)). There have been results which overcome this exponential jump;the best known algorithm can solve DOMINATING SET in time 2(O(k2))n(O(1)) by avoiding constructing a k-expression Bui-Xuan et al. (2013) [7]. We improve this to 2O((k logk))n(O(1)). Indeed, we show that for a graph of clique-width k, a large class of domination and partitioning problems (LC-VSP), including DOMINATING SET, can be solved in 2(O(k log k))n(O(1)). Our main tool is a variant of rank-width using the rank of a 0-1 matrix over the rational field instead of the binary field. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Clique-width parameterized complexity Dynamic programming Generalized domination Rank-width

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：