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

FROM GAP-EXPONENTIAL TIME HYPOTHESIS TO FIXED PARAMETER TRACTABLE IN APPROXIMABILITY: CLIQUE, DOMINATING SET, AND MORE

引用

SIAM JOURNAL ON COMPUTING 2020年第4期49卷 772-810页

作者： Chalermsook, Parinya Cygan, Marek Kortsarz, Guy Laekhanukit, Bundit Manurangsi, Pasin Nanongkai, Danupon Trevisan, Luca Aalto Univ Aalto Finland Univ Warsaw Dept Math Informat & Mech PL-02097 Warsaw Poland Rutgers Univ Camden Dept Comp Sci Camden NJ 08102 USA Max Planck Inst Informat Saarbrucken Germany Shanghai Univ Finance & Econ Shanghai Peoples R China Univ Calif Berkeley Berkeley CA 94720 USA KTH Royal Inst Technol Dept Theoret Comp Sci S-10044 Stockholm Sweden

We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable (FPT) algorithms. The questions, which have been asked several times, are whether there is a nontrivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT)poly(N) time and outputs a solution of size f(OPT) for any computable functions t and f that are independent of N (for Clique, we want f (OPT) = omega(1))? In this paper, we show that both Clique and DomSet admit no nontrivial FPT-approximation algorithm, i.e., there is no o(OPT)-FPT-approximation algorithm for Clique and no f (OPT)-FPT-approximation algorithm for DomSet for any function f. In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis [I. Dinur. ECCC, TR16-128, 2016;P. Manurangsi and P. Raghavendra, preprint, arXiv:1607.02986, 2016], which states that no 2(o(n))-time algorithm can distinguish between a satisfiable 3 SAT formula and one which is not even (1 - epsilon)-satisfiable for some constant epsilon > 0. Besides Clique and DomSet, we also rule out nontrivial FPT-approximation for the Maximum Biclique problem, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs, and we rule out the k(o(1))-FPT-approximation algorithm for the Densest k-Subgraph problem.

关键词： hardness of approximation parameterized complexity subexponential-time algorithms fine-grained complexity clique dominating set

来源：评论

学校读者我要写书评

暂无评论

On the DISTANCE IDENTIFYING SET Meta-problem and Applications to the complexity of Identifying Problems on Graphs

引用

ALGORITHMICA 2020年第8期82卷 2243-2266页

作者： Barbero, Florian Isenmann, Lucas Thiebaut, Jocelyn Univ Montpellier LIRMM 161 Rue Ada F-34095 Montpellier France

Numerous problems consisting in identifying vertices in graphs using distances are useful in domains such as network verification and graph isomorphism. Unifying them into a meta-problem may be of main interest. We introduce here a promising solution named Distance Identifying Set. The model contains Identifying Code (IC), Locating Dominating Set (LD) and their generalizations r-IC and r-LD where the closed neighborhood is considered up to distance r. It also contains Metric Dimension (MD) and its refinement r-MD in which the distance between two vertices is considered as infinite if the real distance exceeds r. Note that while IC = 1-IC and LD = 1-LD, we have MD = infinity-MD;we say that MD is not local. In this article, we prove computational lower bounds for several problems included in Distance Identifying Set by providing generic reductions from (Planar) Hitting Set to the meta-problem. We focus on two families of problems from the meta-problem: the first one, called local, contains r-IC, r-LD and r-MD for each positive integer r while the second one, called 1-layered, contains LD, MD and r-MD for each positive integer r. We have: (1) the 1-layered problems are NP-hard even in bipartite apex graphs, (2) the local problems are NP-hard even in bipartite planar graphs, (3) assuming ETH, all these problems cannot be solved in 2o(n) when restricted to bipartite planar or apex graph, respectively, and they cannot be solved in 2o(n) on bipartite graphs, and (4) except if W[0]=W[2], they do not admit parameterized algorithms in 2O(k)center dot nO(1) even when restricted to bipartite graphs. Here k is the solution size of a relevant identifying set. In particular, Metric Dimension cannot be solved in 2o(n) under ETH, answering a question of Hartung and Nichterlein (Proceedings of the 28th conference on computational complexity, CCC, 2013).

关键词： Identifying code Resolving set Metric dimension Distance identifying set parameterized complexity W-hierarchy Meta-problem Hitting set

来源：评论

学校读者我要写书评

暂无评论

Counting Induced Subgraphs: A Topological Approach to #W-hardness

引用

ALGORITHMICA 2020年第8期82卷 2267-2291页

作者： Roth, Marc Schmitt, Johannes Saarland Univ Saarbrucken Germany Cluster Excellence MMCI Saarbrucken Germany Univ Oxford Merton Coll Oxford England Swiss Fed Inst Technol Zurich Switzerland Univ Bonn Bonn Germany

We investigate the problem #IndSub(Phi) of counting all induced subgraphs of size k in a graph G that satisfy a given property Phi. This continues the work of Jerrum and Meeks who proved the problem to be #W[1]-hard for some families of properties which include (dis)connectedness [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Using the recent framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], we discover that for monotone properties Phi, the problem #IndSub(Phi)) is hard for #W[1] if the reduced Euler characteristic of the associated simplicial (graph) complex of Phi is non-zero. This observation links #IndSub(Phi) to Karp's famous Evasiveness Conjecture, as every graph complex with non-vanishing reduced Euler characteristic is known to be evasive. Applying tools from the "topological approach to evasiveness" which was introduced in the seminal paper of Khan, Saks and Sturtevant [FOCS 83], we prove that #IndSub(Phi) is #W[1]-hard for every monotone property Phi that does not hold on the Hamilton cycle as well as for some monotone properties that hold on the Hamilton cycle such as being triangle-free or not k-edge-connected for k > 2. Moreover, we show that for those properties #IndSub(Phi) can not be solved in time f (k) center dot no(k) for any computable function f unless the Exponential Time Hypothesis (ETH) fails. In the final part of the paper, we investigate non-monotone properties and prove that #IndSub(Phi) is #W[1]-hard if Phi is any non-trivial modularity constraint on the number of edges with respect to some prime q or if Phi enforces the presence of a fixed isolated subgraph.

关键词： Counting complexity Euler characteristic Homomorphisms parameterized complexity Simplicial complexes

来源：评论

学校读者我要写书评

暂无评论

A Polynomial Sized Kernel for Tracking Paths Problem

引用

ALGORITHMICA 2020年第1期82卷 41-63页

作者： Banik, Aritra Choudhary, Pratibha Lokshtanov, Daniel Raman, Venkatesh Saurabh, Saket Natl Inst Sci Educ & Res Bhubaneswar Bhubaneswar Odisha India Indian Inst Technol Jodhpur Jodhpur Rajasthan India Univ Calif Santa Barbara Santa Barbara CA 93106 USA HBNI Inst Math Sci Chennai Tamil Nadu India UMI ReLaX Chennai Tamil Nadu India

Consider a secure environment (say an airport) that has a unique entry and a unique exit point with multiple inter-crossing paths between them. We want to place (minimum number of) trackers (or check points) at some specific intersections so that based on the sequence of trackers a person has encountered, we can identify the exact path traversed by the person. Motivated by such applications, we study the Tracking Paths problem in this paper. Given an undirected graph with a source s, a destination t and a non-negative integer k, the goal is to find a set of at most k vertices, a tracking set, that intersects each s-t path in a unique sequence. Such a set enables a central controller to track all the paths from s to t. We first show that the problem is NP-complete. Then we show that finding a tracking set of size at most k is fixed-parameter tractable when parameterized by the solution size. More specifically, given an undirected graph on n vertices and an integer k, we give a polynomial time algorithm that either determines that the graph cannot be tracked by k trackers or produces an equivalent instance with O(k(7)) edges.

关键词： Graph s-t paths Tracking paths parameterized complexity FPT Kernel Feedback vertex set

来源：评论

学校读者我要写书评

暂无评论

Mixed integer programming with convex/concave constraints: Fixed-parameter tractability and applications to multicovering and voting

引用

THEORETICAL COMPUTER SCIENCE 2020年 814卷 86-105页

作者： Bredereck, Robert Faliszewski, Piotr Niedermeier, Rolf Skowron, Piotr Talmon, Nimrod TU Berlin Berlin Germany AGH Univ Sci & Technol Krakow Poland Univ Warsaw Warsaw Poland Ben Gurion Univ Negev Beer Sheva Israel

A classic result of Lenstra [Math. Oper. Res. 1983] says that an integer linear program can be solved in fixed-parameter tractable (FPT) time for the parameterization by the number of variables. We extend this result by incorporating piecewise linear convex or concave functions to our (mixed) integer programs. This general technique allows us to analyze the parameterized complexity of a number of classic NP-hard computational problems. In particular, we prove that WEIGHTED SET MULTICOVER is in FPT when parameterized by the number of elements to cover, and that there exists an FPT-time approximation scheme for MULTISET MULTICOVER for the same parameter-this is our most technical result. Further, we use our general technique to prove that a number of problems from computational social choice (e.g., problems related to bribery and control in elections) are in FPT when parameterized by the number of candidates. For bribery, this resolves a nearly 10-year old family of open problems, and for weighted electoral control of Approval voting, this improves some previously known XP-memberships to FPT-memberships. (C) 2020 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Max cover Multiset multicover Weighted set multicover

来源：评论

学校读者我要写书评

暂无评论

Finding connected secluded subgraphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2020年 113卷 101-124页

作者： Golovach, Petr A. Heggernes, Pinar Lima, Paloma T. Montealegre, Pedro Univ Bergen Dept Informat N-5020 Bergen Norway Univ Adolfo Ibanez Fac Ingn & Ciencias Santiago Chile

Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. However, for many applications, it is desirable that the found subgraph has as few connections to the rest of the graph as possible, which gives rise to the SECLUDED Pi-SUBGRAPH problem. Here, input k is the size of the desired subgraph, and input t is a limit on the number of neighbors this subgraph has in the rest of the graph. This problem has been studied from a parameterized perspective, and unfortunately it turns out to be W[1]-hard for many graph properties Pi, even when parameterized by k + t. We show that the situation changes when we are looking for a connected induced subgraph satisfying Pi. In particular, we show that the CONNECTED SECLUDED Pi-SUBGRAPH problem is FPT when parameterized by just t for many important graph properties Pi. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Secluded subgraph parameterized complexity Forbidden subgraphs

来源：评论

学校读者我要写书评

暂无评论

Using decomposition-parameters for QBF: Mind the prefix!

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2020年第0期110卷 1-21页

作者： Eiben, Eduard Ganian, Robert Ordyniak, Sebastian Vienna Univ Technol Algorithms & Complex Grp Vienna Austria Univ Sheffield Dept Comp Sci Sheffield S Yorkshire England Royal Holloway Univ London London England

Similar to the satisfiability (SAT) problem, which can be seen to be the archetypical problem for NP, the quantified Boolean formula problem (QBF) is the archetypical problem for PSPACE. Recently, Atserias and Oliva (2014) showed that, unlike for SAT, many of the well-known decompositional parameters (such as treewidth and pathwidth) do not allow efficient algorithms for QBF. The main reason for this seems to be the lack of awareness of these parameters towards the dependencies between variables of a QBF formula. In this paper we extend the ordinary pathwidth to the QBF-setting by introducing prefix pathwidth, which takes into account the dependencies between variables in a QBF, and show that it leads to an efficient algorithm for QBF. We hope that our approach will help to initiate the study of novel tailor-made decompositional parameters for QBF and thereby help to lift the success of these decompositional parameters from SAT to QBF. (C) 2020 Published by Elsevier Inc.

关键词： Quantified Boolean formulas Dependency schemes Treewidth Pathwidth parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The Inverse Voronoi Problem in Graphs I: Hardness

引用

ALGORITHMICA 2020年第10期82卷 3018-3040页

作者： Bonnet, Edouard Cabello, Sergio Mohar, Bojan Perez-Roses, Hebert Univ Claude Bernard Lyon 1 Univ Lyon LIP CNRSENS LyonUMR5668 Lyon France Univ Ljubljana Fac Math & Phys Ljubljana Slovenia IMFM Ljubljana Slovenia Simon Fraser Univ Dept Math Burnaby BC Canada Univ Rovira & Virgili Dept Engn Informat & Matemat Tarragona Spain

We introduce the inverse Voronoi diagram problem in graphs: given a graph G with positive edge-lengths and a collection U\ of subsets of vertices of V(G), decide whether U\ is a Voronoi diagram in G with respect to the shortest-path metric. We show that the problem is NP-hard, even for planar graphs where all the edges have unit length. We also study the parameterized complexity of the problem and show that the problem is W[1]-hard when parameterized by the number of Voronoi cells or by the pathwidth of the graph.

关键词： Distances in graphs Voronoi diagram Inverse Voronoi problem NP-complete parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the Fixed-Parameter Tractability of the Maximum Connectivity Improvement Problem

引用

THEORY OF COMPUTING SYSTEMS 2020年第6期64卷 1094-1109页

作者： Coro, Federico D'Angelo, Gianlorenzo Mkrtchyan, Vahan Sapienza Univ Rome Rome Italy Gran Sasso Sci Inst Laquila Italy

In the Maximum Connectivity Improvement (MCI) problem, we are given a directed graph G = (V,E) and an integer B and we are asked to find B new edges to be added to G in order to maximize the number of connected pairs of vertices in the resulting graph. The MCI problem has been studied from the approximation point of view. In this paper, we approach it from the parameterized complexity perspective in the case of directed acyclic graphs. We show several hardness and algorithmic results with respect to different natural parameters. Our main result is that the problem is W[2]-hard for parameter B and it is FPT for parameters |V |- B and nu, the matching number of G. We further characterize the MCI problem with respect to other complementary parameters.

关键词： Graph augmentation Connectivity parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Partitioning graphs into induced subgraphs

引用

DISCRETE APPLIED MATHEMATICS 2020年第0期272卷 31-42页

作者： Knop, Dusan TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany Czech Tech Univ Fac Informat Technol Dept Theoret Comp Sci Prague Czech Republic

We study the PARTITION INTO H problem from the parameterized complexity point of view. In the PARTITION INTO H problem the task is to partition the vertices of a graph G into sets, V-1,V-2, ..., V-r. such that the graph His isomorphic to the subgraph of G induced by each set V-i for i = 1, 2, ..., r. the pattern graph H is fixed. For the parameterization we consider three distinct structural parameters of the graph G - namely the tree-width, the neighborhood diversity, and the modular-width. For the parameterization by the neighborhood diversity we obtain an FPT algorithm for every graph H. For the parameterization by the tree-width we obtain an FPT algorithm for every connected graph H, thus resolving an open question of Gajarsky et al. (2013). Finally, for the parameterization by the modular-width we derive an FPT algorithm for every prime graph H. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Graph matching Graph partitioning parameterized complexity Dense graphs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：