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

NP-HARDNESS AND FIXED-PARAMETER TRACTABILITY OF REALIZING DEGREE SEQUENCES WITH DIRECTED ACYCLIC GRAPHS

SIAM JOURNAL ON DISCRETE MATHEMATICS 2015年第4期29卷 1931-1960页

作者： Hartung, Sepp Nichterlein, Andre TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

In graph realization problems, one is given a degree sequence and the task is to decide whether there is a graph whose vertex degrees match the given sequence. This realization problem is known to be polynomial-time solvable when the graph is directed or undirected. In contrast, we show NP-completeness for the problem of realizing a given sequence of pairs of nonnegative integers (representing in-and outdegrees) with a directed acyclic graph (DAG), answering an open question of Berger and Muller-Hannemann. Furthermore, we classify the problem as fixed-parameter tractable with respect to the parameter "maximum degree." Investigating sparse and dense settings, we show that the problem remains NP-hard even if the realizing DAG (precisely, the underlying undirected graph) can be transformed into a clique (a tree) by adding (deleting) a constant fraction of the arcs. In contrast, if at most k arcs have to be inserted, respectively, removed to obtain a clique or a tree in the underlying undirected graph, then the problem becomes fixed-parameter tractable with respect to k.

关键词： graph realization problems combinatorial algorithms parameterized complexity structural parameterization

来源：评论

学校读者我要写书评

暂无评论

Pure Nash Equilibria in Graphical Games and Treewidth

引用

ALGORITHMICA 2015年第3期71卷 581-604页

作者： Thomas, Antonis van Leeuwen, Jan ETH Inst Theoret Comp Sci CH-8092 Zurich Switzerland Univ Utrecht Dept Informat & Comp Sci NL-3584 CC Utrecht Netherlands

We treat PNE-GG, the problem of deciding the existence of a Pure Nash Equilibrium in a graphical game, and the role of treewidth in this problem. PNE-GG is known to be -complete in general, but polynomially solvable for graphical games of bounded treewidth. We prove that PNE-GG is -Hard when parameterized by treewidth. On the other hand, we give a dynamic programming approach that solves the problem in time, where is the cardinality of the largest strategy set and is the treewidth of the input graph (and hides polynomial factors). This proves that PNE-GG is in for the combined parameter . Moreover, we prove that there is no algorithm that solves PNE-GG in time for any , unless the Strong Exponential Time Hypothesis fails. Our lower bounds implicitly assume that;we show that for the problem can be solved in polynomial time. Finally, we discuss the implication for computing pure Nash equilibria in graphical games (PNE-GG) of treewidth, the existence of polynomial kernels for PNE-GG parameterized by treewidth, and the construction of a sample and maximum-payoff pure Nash equilibrium.

关键词： Nash equilibria Graphical games parameterized complexity Treewidth

来源：评论

学校读者我要写书评

暂无评论

Interval scheduling and colorful independent sets

引用

JOURNAL OF SCHEDULING 2015年第5期18卷 449-469页

作者： van Bevern, Rene Mnich, Matthias Niedermeier, Rolf Weller, Mathias TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Cluster Excellence Multimodal Comp & Interact Saarbrucken Germany Univ Montpellier 2 LIRMM Montpellier France

Numerous applications in scheduling, such as resource allocation or steel manufacturing, can be modeled using the NP-hard Independent Set problem (given an undirected graph and an integer , find a set of at least pairwise non-adjacent vertices). Here, one encounters special graph classes like 2-union graphs (edge-wise unions of two interval graphs) and strip graphs (edge-wise unions of an interval graph and a cluster graph), on which Independent Set remains -hard but admits constant ratio approximations in polynomial time. We study the parameterized complexity of Independent Set on 2-union graphs and on subclasses like strip graphs. Our investigations significantly benefit from a new structural "compactness" parameter of interval graphs and novel problem formulations using vertex-colored interval graphs. Our main contributions are as follows: 1. We show a complexity dichotomy: restricted to graph classes closed under induced subgraphs and disjoint unions, Independent Set is polynomial-time solvable if both input interval graphs are cluster graphs, and is -hard otherwise. 2. We chart the possibilities and limits of effective polynomial-time preprocessing (also known as kernelization). 3. We extend Halldrsson and Karlsson (2006)'s fixed-parameter algorithm for Independent Set on strip graphs parameterized by the structural parameter "maximum number of live jobs" to show that the problem (also known as Job Interval Selection) is fixed-parameter tractable with respect to the parameter and generalize their algorithm from strip graphs to 2-union graphs. Preliminary experiments with random data indicate that Job Interval Selection with up to 15 jobs and intervals can be solved optimally in less than 5 min.

关键词： Interval graphs 2-union graphs Strip graphs Job interval selection parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Point Line Cover: The Easy Kernel is Essentially Tight

引用

ACM TRANSACTIONS ON ALGORITHMS 2016年第3期12卷 40-40页

作者： Kratsch, Stefan Philip, Geevarghese Ray, Saurabh Tech Univ Berlin Berlin Germany Max Planck Inst Informat Saarbrucken Germany Ben Gurion Univ Negev IL-84105 Beer Sheva Israel Univ Bonn Inst Informat 1 Friedrich Ebert Allee 144 D-53113 Bonn Germany Chennai Math Inst Plot H1SIPCOT IT Pk Madras 603103 Tamil Nadu India NYU Abu Dhabi Off A2 187 Abu Dhabi 129188 U Arab Emirates

The input to the NP-hard POINT LINE COVER problem (PLC) consists of a set P of n points on the plane and a positive integer k;the question is whether there exists a set of at most k lines that pass through all points in P. By straightforward reduction rules, one can efficiently reduce any input to one with at most k(2) points. We show that this easy reduction is already essentially tight under standard assumptions. More precisely, unless the polynomial hierarchy collapses to its third level, for any epsilon > 0, there is no polynomial-time algorithm that reduces every instance (P, k) of PLC to an equivalent instance with O(k(2-epsilon)) points. This answers, in the negative, an open problem posed by Lokshtanov [2009]. Our proof uses the notion of a kernel from parameterized complexity, and the machinery for deriving lower bounds on the size of kernels developed by Dell and van Melkebeek [2010, 2014]. It has two main ingredients: We first show, by reduction from VERTEX COVER, that-unless the polynomial hierarchy collapses-PLC has no kernel of total size O(k(2-epsilon)) bits. This does not directly imply the claimed lower bound on the number of points, since the best-known polynomial-time encoding of a PLC instance with n points requires omega(n(2)) bits. To get around this hurdle, we build on work of Alon [1986] and devise an oracle communication protocol of cost O(n log n) for PLC. This protocol, together with the lower bound on the total size (which also holds for such protocols), yields the stated lower bound on the number of points. While a number of essentially tight polynomial lower bounds on total sizes of kernels are known, our result is-to the best of our knowledge-the first to show a nontrivial lower bound for structural/secondary parameters. It is also the first example of a lower bound for kernelization that makes use of the full power of the oracle communication protocol lower bounds that can be obtained from the work of Dell and van Melkebeek. We combin

关键词： Kernelization lower bounds parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized Algorithms for Deletion to Split Graphs

引用

ALGORITHMICA 2015年第4期71卷 989-1006页

作者： Ghosh, Esha Kolay, Sudeshna Kumar, Mrinal Misra, Pranabendu Panolan, Fahad Rai, Ashutosh Ramanujan, M. S. Inst Math Sci Madras 600113 Tamil Nadu India Indian Inst Technol Madras 600036 Tamil Nadu India Chennai Math Inst Chennai Tamil Nadu India

An undirected graph is said to be split if its vertex set can be partitioned into two sets such that the subgraph induced on one of them is a complete graph and the subgraph induced on the other is an independent set. We initiate a systematic study of parameterized complexity of the problem of deleting the minimum number of vertices or edges from a given input graph so that the resulting graph is split. We give efficient fixed-parameter algorithms and polynomial sized kernels for the problem. More precisely, 1. for Split Vertex Deletion, the problem of determining whether there are k vertices whose deletion results in a split graph, we give an O* (2(k)) algorithm (O* () notation hides factors that are polynomial in the input size) improving on the previous best bound of . We also give an -sized kernel for the problem. 2. For Split Edge Deletion, the problem of determining whether there are k edges whose deletion results in a split graph, we give an algorithm. We also prove the existence of an kernel. In addition, we note that our algorithm for SPLIT EDGE DELETION adds to the small number of subexponential parameterized algorithms not obtained through bidimensionality (Demaine et al. in J. ACM 52(6): 866-893, 2005), and on general graphs.

关键词： parameterized complexity Deletion problems Split graphs Subexponential algorithm

来源：评论

学校读者我要写书评

暂无评论

Combinatorial voter control in elections

引用

THEORETICAL COMPUTER SCIENCE 2015年 589卷 99-120页

作者： Bulteau, Laurent Chen, Jiehua Faliszewski, Piotr Niedermeier, Rolf Talmon, Nimrod Univ Lyon 1 CNRS UMR5558 Inria Grenoble Rhone Alpes LBBE F-69622 Villeurbanne France Tech Univ Berlin Inst Softwaretech & Theoret Informat D-10587 Berlin Germany AGH Univ Sci & Technol PL-30059 Krakow Poland

Voter control problems model situations such as an external agent trying to affect the result of an election by adding voters, for example by convincing some voters to vote who would otherwise not attend the election. Traditionally, voters are added one at a time, with the goal of making a distinguished alternative win by adding a minimum number of voters. In this paper, we initiate the study of combinatorial variants of control by adding voters. In our setting, when we choose to add a voter v, we also have to add a whole bundle kappa(v) of voters associated with v. We study the computational complexity of this problem for two of the most basic voting rules, namely the Plurality rule and the Condorcet rule. (C) 2015 Published by Elsevier B.V.

关键词： Voting NP-hard election control problem Domain restrictions The Plurality rule Condorcet's rule parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The role of planarity in connectivity problems parameterized by treewidth

引用

THEORETICAL COMPUTER SCIENCE 2015年第C期570卷 1-14页

作者： Baste, Julien Sau, Ignasi LIRMM AlGCo Project Team Montpellier France ENS Cachan Cachan France

For some years it was believed that for "connectivity" problems such as HAMILTONIAN CYCLE, algorithms running in time 2(0(tw)).n(0(1)) - called single-exponential - existed only on planar and other topologically constrained graph classes, where tw stands for the treewidth of the n-vertex input graph. This was recently disproved by Cygan et al. [3, FOCS 2011], Bodlaender et al. [1, ICALP 2013], and Fomin et al. [11, SODA 2014], who provided single-exponential algorithms on general graphs for most connectivity problems that were known to be solvable in single-exponential time on topologically constrained graphs. In this article we further investigate the role of planarity in connectivity problems parameterized by treewidth, and convey that several problems can indeed be distinguished according to their behavior on planar graphs. Known results from the literature imply that there exist problems, like CYCLE PACKING, that cannot be solved in time 2(0(tw log tw)).n(0(1)) on general graphs but that can be solved in time 2(0(tw)).n(0(1)) when restricted to planar graphs. Our main contribution is to show that there exist natural problems that can be solved in time 2(0(tw log tw)).n(0(1)) on general graphs but that cannot be solved in time 2(0(tw log tw)).n(0(1)) even when restricted to planar graphs. Furthermore, we prove that PLANAR CYCLE PACKING and PLANAR DISJOINT PATHS cannot be solved in time 2(0(tw)).n(0(1)). The mentioned negative results hold unless the ETH fails. We feel that our results constitute a first step in a subject that can be further exploited. (C) 2015 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Treewidth Connectivity problems Single-exponential algorithms Planar graphs Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Backdoors to tractable answer set programming

引用

ARTIFICIAL INTELLIGENCE 2015年 220卷 64-103页

作者： Fichte, Johannes Klaus Szeider, Stefan Vienna Univ Technol A-1040 Vienna Austria Univ Potsdam D-14482 Potsdam Germany

Answer Set Programming (ASP) is an increasingly popular framework for declarative programming that admits the description of problems by means of rules and constraints that form a disjunctive logic program. In particular, many Al problems such as reasoning in a nonmonotonic setting can be directly formulated in ASP. Although the main problems of ASP are of high computational complexity, complete for the second level of the Polynomial Hierarchy, several restrictions of ASP have been identified in the literature, under which ASP problems become tractable. In this paper we use the concept of backdoors to identify new restrictions that make ASP problems tractable. Small backdoors are sets of atoms that represent "clever reasoning shortcuts" through the search space and represent a hidden structure in the problem input. The concept of backdoors is widely used in theoretical investigations in the areas of propositional satisfiability and constraint satisfaction. We show that it can be fruitfully adapted to ASP. We demonstrate how backdoors can serve as a unifying framework that accommodates several tractable restrictions of ASP known from the literature. Furthermore, we show how backdoors allow us to deploy recent algorithmic results from parameterized complexity theory to the domain of answer set programming. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Answer set programming Backdoors Computational complexity parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

Restricted and Swap Common Superstring: A Multivariate Algorithmic Perspective

引用

ALGORITHMICA 2015年第4期72卷 914-939页

作者： Bonizzoni, Paola Dondi, Riccardo Mauri, Giancarlo Zoppis, Italo Univ Milano Bicocca Dipartimento Informat Sistemist & Comunicaz Milan Italy Univ Bergamo Dipartimento Sci Umane & Sociali Bergamo Italy

In several areas, for example in bioinformatics and in AI planning, the Shortest Common Superstring problem (SCS) and variants thereof have been successfully applied for string comparison. In this paper we consider two variants of SCS recently introduced, namely Restricted Common Superstring (RCS) and Swapped Common Superstring (SRCS). In RCS we are given a set of strings and a multiset of symbols, and we look for an ordering of such that the number of input strings which are substrings of is maximized. In SRCS we are given a set of strings and a text , and we look for a swap ordering of (an ordering of obtained by swapping only some pairs of adjacent symbols) such that the number of input strings which are substrings of is maximized. In this paper we propose a multivariate algorithmic analysis of the complexity of the two problems, aiming at determining how different parameters influence the complexity of the two problems. We consider as interesting parameters the size of the solutions (that is the number of input strings contained in the computed superstring), the maximum length of the given input strings, the size of the alphabet over which the input strings range. First, we give two fixed-parameter algorithms, where the parameter is the size of the solution, for SRCS and lRCS (the RCS problem restricted to strings of length bounded by a parameter ). Furthermore, we complement these results by showing that SRCS and lRCS do not admit a polynomial kernel unless . Then, we show that SRCS is APX-hard even when the input strings have length bounded by a constant (equal to ) or are over a binary alphabet.

关键词： Shortest common superstring String comparison parameterized complexity Algorithms APX-hardness

来源：评论

学校读者我要写书评

暂无评论

Minimum Fill-in of Sparse Graphs: Kernelization and Approximation

引用

ALGORITHMICA 2015年第1期71卷 1-20页

作者： Fomin, Fedor V. Philip, Geevarghese Villanger, Yngve Univ Bergen Dept Informat N-5020 Bergen Norway Max Planck Inst Informat D-66123 Saarbrucken Germany

The Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most k edges. The problem has important applications in numerical algebra, in particular in sparse matrix computations. We develop kernelization algorithms for the problem on several classes of sparse graphs. We obtain linear kernels on planar graphs, and kernels of size in graphs excluding some fixed graph as a minor and in graphs of bounded degeneracy. As a byproduct of our results, we obtain approximation algorithms with approximation ratios on planar graphs and on H-minor-free graphs. These results significantly improve the previously known kernelization and approximation results for Minimum Fill-in on sparse graphs.

关键词： parameterized complexity Kernelization Minimum fill-in Planar graphs Linear kernel d-Degenerate graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：