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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Simultaneous consecutive ones submatrix and editing problems: Classical complexity and fixed-parameter tractable results

引用

THEORETICAL COMPUTER SCIENCE 2020年 812卷 13-38页

作者： Rani, M. R. Subashini, R. Jagalmohanan, Mohith Natl Inst Technol Dept Comp Sci & Engn Calicut Kerala India Dell Int Serv Private Ltd Hyderabad India

A binary matrix M has the consecutive ones property (C1P) for rows (resp. columns) if there exists a permutation of its columns (resp. rows) that arranges the ones consecutively in all the rows (resp. columns). If M has the C1P for rows and the C1P for columns, then M is said to have the simultaneous consecutive ones property (SC1P). In this article, we consider the classical complexity and fixed-parameter tractability of a few variants of decision problems related to the SC1P. Given a binary matrix M and a positive integer d, we focus on problems that decide whether there exists a set of rows, columns, and rows as well as columns, respectively, of size at most d in M, whose deletion results in a matrix with the SC1P. We also consider problems that decide whether there exists a set of 0-entries, 1-entries and 0-entries as well as 1-entries, respectively, of size at most din M, whose flipping results in a matrix with the SC1P. In this paper, we show that all the above mentioned problems are NP-complete. We could also prove that all these problems are fixed-parameter tractable with respect to solution size as the parameter, except for two variants (flipping 1-entries and flipping 0/1-entries). We also give improved FPT algorithms for certain problems on restricted binary matrices. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Consecutive Ones Property (C1P) Simultaneous Consecutive Ones Property (SC1P) Fixed-Parameter Tractable (FPT) parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Pursuing a fast robber on a graph

引用

THEORETICAL COMPUTER SCIENCE 2010年第7-9期411卷 1167-1181页

作者： Fomin, Fedor V. Golovach, Petr A. Kratochvil, Jan Nisse, Nicolas Suchan, Karol Univ Bergen Dept Informat N-5020 Bergen Norway Charles Univ Prague Dept Appl Math Inst Theoret Comp Sci Prague Czech Republic UNS CNRS I3S MASCOTTEINRIA Sophia Antipolis France Univ Adolfo Ibanez Fac Ingn & Ciencias Santiago Chile AGH Univ Sci & Technol Fac Appl Math Krakow Poland

The Cops and Robbers game as originally defined independently by Quilliot and by Nowakowski and Winkler in the 1980s has been Much Studied, but very few results pertain to the algorithmic and complexity aspects of it. In this paper we prove that computing the minimum number of cops that are guaranteed to catch a robber on a given graph is NP-hard and that the parameterized version of the problem is W[2]-hard;the proof extends to the case where the robber moves s time faster than the cops. We show that on split graphs, the problem is polynomially solvable if s = 1 but is NP-hard if s = 2. We further prove that on graphs of bounded cliquewidth the problem is polynomially solvable for s <= 2. Finally, we show that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Pursuit-evasion game on graphs Cops and Robbers complexity parameterized complexity Cliquewidth Planar graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：