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

SIAM JOURNAL ON COMPUTING 2018年第1期47卷 166-207页

作者： Bousquet, Nicolas Daligault, Jean Thomasse, Stephan Univ Grenoble Alpes CNRS G SCOP 46 Ave Felix Viallet F-38031 Grenoble France Univ Montpellier 2 CNRS LIRMM 161 Rue Ada F-34392 Montpellier France Univ Lyon ENS Lyon LIP CNRSINRIAUCBL 46 Allee Italie F-69364 Lyon 07 France

Let G = (V, E) be a graph on n vertices and R be a set of pairs of vertices in V called requests. A multicut is a subset F of E such that every request xy of R is separated by F, i.e., every xy-path of G intersects F. We show that there exists an O(f(k)n(c)) algorithm which decides if there exists a multicut of size at most k. In other words, the MULTICUT problem parameterized by the solution size k is fixed -parameter tractable (FPT).

关键词： multicut cut problems FPT parameterized complexity important separators

来源：评论

学校读者我要写书评

暂无评论

Covering graphs with few complete bipartite subgraphs

引用

THEORETICAL COMPUTER SCIENCE 2009年第21-23期410卷 2045-2053页

作者： Fleischner, Herbert Mujuni, Egbert Paulusma, Daniel Szieder, Stefan Univ Durham Dept Comp Sci Durham DH1 3LE England Vienna Univ Technol Dept Comp Sci A-1040 Vienna Austria Univ Dar Es Salaam Dept Math Dar Es Salaam Tanzania

We consider computational problems on covering graphs with bicliques (complete bipartite subgraphs). Given a graph and an integer k, the biclique cover problem asks whether the edge-set of the graph can be covered with at most k bicliques;the biclique partition problem is defined similarly with the additional condition that the bicliques are required to be mutually edge-disjoint. The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most k bicliques, the biclique vertex-partition problem is defined similarly with the additional condition that the bicliques are required to be mutually vertex-disjoint. All these four problems are known to be NP-complete even if the given graph is bipartite. In this paper, we investigate them in the framework of parameterized complexity: do the problems become easier if k is assumed to be small? We show that, considering k as the parameter, the first two problems are fixed-parameter tractable, while the latter two problems are not fixed-parameter tractable unless P = NP. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Bicliques parameterized complexity Covering and partitioning problems

来源：评论

学校读者我要写书评

暂无评论

complexity of Token Swapping and Its Variants

引用

ALGORITHMICA 2018年第9期80卷 2656-2682页

作者： Bonnet, Edouard Miltzow, Tillmann Rzazewski, Pawel Middlesex Univ Dept Comp Sci London England ULB Brussels Belgium Warsaw Univ Technol Fac Math & Informat Sci Warsaw Poland

In the Token Swapping problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their destinations, using the minimum number of swaps, i.e., operations of exchanging the tokens on two adjacent vertices. As the main result of this paper, we show that Token Swapping is -hard parameterized by the length k of a shortest sequence of swaps. In fact, we prove that, for any computable function f, it cannot be solved in time where n is the number of vertices of the input graph, unless the ETH fails. This lower bound almost matches the trivial -time algorithm. We also consider two generalizations of the Token Swapping, namely Colored Token Swapping (where the tokens have colors and tokens of the same color are indistinguishable), and Subset Token Swapping (where each token has a set of possible destinations). To complement the hardness result, we prove that even the most general variant, Subset Token Swapping, is FPT in nowhere-dense graph classes. Finally, we consider the complexities of all three problems in very restricted classes of graphs: graphs of bounded treewidth and diameter, stars, cliques, and paths, trying to identify the borderlines between polynomial and NP-hard cases.

关键词： Token swapping parameterized complexity W[1]-hardness

来源：评论

学校读者我要写书评

暂无评论

Parameterizing above or below guaranteed values

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2009年第2期75卷 137-153页

作者： Mahajan, Meena Raman, Venkatesh Sikdar, Somnath Inst Math Sci Madras 600113 Tamil Nadu India

We consider new parameterizations of NP-optimization problems that have nontrivial lower and/or upper bounds oil their optimum Solution size. The natural parameter, we argue, is the quantity above the lower bound or below the upper bound. We show that for every problem in MAX SNP, the optimum Value is bounded below by all unbounded function of the input-size, and that the above-guarantee parameterization with respect to this lower bound is fixed-parameter tractable. We also observe that approximation algorithms give nontrivial lower or upper bounds oil the solution size and that the above or below guarantee question with respect to these bounds is fixed-parameter tractable for a Subclass of NP-optimization problems. We then introduce the notion of 'tight' lower and upper bounds and exhibit a number of problems for which the above-guarantee and below-guarantee parameterizations with respect to a tight bound is fixed-parameter tractable or W-hard. We show that if we parameterize "sufficiently" above or below the tight bounds, then these parameterized versions are nor fixed-parameter tractable unless P = NP. for a Subclass of NP-optimization problems. We also list several directions to explore in this paradigm. (c) 2009 Elsevier Inc. All rights reserved.

关键词： parameterized complexity NP-optimization problems Fixed-parameter tractability Above guarantee parameterizations

来源：评论

学校读者我要写书评

暂无评论

Constant Thresholds Can Make Target Set Selection Tractable

引用

THEORY OF COMPUTING SYSTEMS 2014年第1期55卷 61-83页

作者： Chopin, Morgan Nichterlein, Andre Niedermeier, Rolf Weller, Mathias Univ Paris 09 LAMSADE Paris France TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany

Target Set Selection, which is a prominent NP-hard problem occurring in social network analysis and distributed computing, is notoriously hard both in terms of achieving useful polynomial-time approximation as well as fixed-parameter algorithms. Given an undirected graph, the task is to select a minimum number of vertices into a "target set" such that all other vertices will become active in the course of a dynamic process (which may go through several activation rounds). A vertex, equipped with a threshold value t, becomes active once at least t of its neighbors are active;initially, only the target set vertices are active. We contribute further insights into the existence of islands of tractability for Target Set Selection by spotting new parameterizations characterizing some sparse graphs as well as some "cliquish" graphs and developing corresponding fixed-parameter tractability and (parameterized) hardness results. In particular, we demonstrate that upper-bounding the thresholds by a constant may significantly alleviate the search for efficiently solvable, but still meaningful special cases of Target Set Selection.

关键词： Spread of influence Dynamics in social networks parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

Searching the k-change neighborhood for TSP is W -hard

引用

OPERATIONS RESEARCH LETTERS 2008年第1期36卷 31-36页

作者： Marx, Daniel Humboldt Univ Inst Informat D-10099 Berlin Germany

We show that searching the k-change neighborhood is W[1]-hard for metric TSP, which means that finding the best tour in the k-change neighborhood essentially requires complete search (modulo some complexity-theoretic ... 详细信息

关键词： traveling salesperson problem W[1]-hardness parameterized complexity local search

来源：评论

学校读者我要写书评

暂无评论

Refining the complexity of the sports elimination problem

引用

DISCRETE APPLIED MATHEMATICS 2016年 199卷 172-186页

作者： Cechlarova, Katarina Potpinkova, Eva Schlotter, Ildiko Safarik Univ Fac Sci Inst Math Kosice 04001 Slovakia Budapest Univ Technol & Econ H-1521 Budapest Hungary

The sports elimination problem asks whether a team participating in a competition still has a chance to win, given the current standings and the remaining matches to be played among the teams. This problem can be viewed as a graph labelling problem, where arcs receive labels that contribute to the score of both endpoints of the arc, and the aim is to label the arcs in a way that each vertex obtains a score not exceeding its capacity. We investigate the complexity of this problem in detail, using a multivariate approach to examine how various parameters of the input graph (such-as the maximum degree, the feedback vertex/edge number, and different width parameters) influence the computational tractability. We obtain several efficient algorithms, as well as certain hardness results. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Sports elimination problem Graph labelling parameterized complexity Multivariate complexity analysis

来源：评论

学校读者我要写书评

暂无评论

Spy game: FPT-algorithm, hardness and graph products

引用

THEORETICAL COMPUTER SCIENCE 2022年 923卷 304-317页

作者： Costa, Eurinardo Rodrigues Martins, Nicolas Almeida Sampaio, Rudini Univ Fed Ceara Campus Russas Russas Brazil Univ Integr Int Lusofonia Afrobrasileira Unilab Redencao Brazil Univ Fed Ceara Dept Comp Fortaleza Ceara Brazil

In the (s, d)-spy game over a graph G, k guards and one spy occupy some vertices of G and, at each turn, the spy may move with speed s(along at most sedges) and each guard may move along one edge. The spy and the guards may occupy the same vertices. The spy wins if she reaches a vertex at distance more than the surveilling distance d from every guard. This game was introduced by Cohen et al. (2016) [15] and is related to two wellstudied games: Cops and Robber game and Eternal Dominating game. The guard number gns,d(G) is the minimum number of guards such that the guards have a winning strategy (of controlling the spy) in the graph G. In 2018, it was proved that deciding if the spy has a winning strategy is NP-hard for every speed s >= 2and distance d >= 0. In this paper, we initiate the investigation of the guard number in grids and in graph products. We obtain a strict upper bound on the strong product of two general graphs and obtain examples with King grids that match this bound and other examples for which the guard number is smaller. We also obtain the exact value of the guard number in the lexicographical product of two general graphs for any distance d >= 2. From the algorithmic point of view, we prove a positive result: if the number k of guards is fixed, the spy game is solvable in polynomial XP time O(n(3k+2)) for every speed s >= 2and distance d = 0. In other words, the spy game is XP when parameterized by the number of guards. This XP algorithm is used to obtain an FPT algorithm on the P-4-fewness of the graph. As a negative result, we prove that the spy game is W[2]-hard even in bipartite graphs when parameterized by the number of guards, for every speed s >= 2and distance d >= 0, extending the hardness result of Cohen et al. in 2018. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Games on graphs Spy game Graph products XP algorithm parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms of fundamental NP-hard problems: a survey

引用

HUMAN-CENTRIC COMPUTING AND INFORMATION SCIENCES 2020年第1期10卷 1-24页

作者： Li, Wenjun Ding, Yang Yang, Yongjie Sherratt, R. Simon Park, Jong Hyuk Wang, Jin Changsha Univ Sci & Technol Dept Comp & Commun Engn Changsha Peoples R China Saarland Univ Saarbrucken Germany Univ Reading Sch Syst Engn Reading Berks England Seoul Natl Univ Sci & Technol Dept Comp Sci & Engn Seoul South Korea

parameterized computation theory has developed rapidly over the last two decades. In theoretical computer science, it has attracted considerable attention for its theoretical value and significant guidance in many practical applications. We give an overview on parameterized algorithms for some fundamental NP-hard problems, including MaxSAT, Maximum Internal Spanning Trees, Maximum Internal Out-Branching, Planar (Connected) Dominating Set, Feedback Vertex Set, Hyperplane Cover, Vertex Cover, Packing and Matching problems. All of these problems have been widely applied in various areas, such as Internet of Things, Wireless Sensor Networks, Artificial Intelligence, Bioinformatics, Big Data, and so on. In this paper, we are focused on the algorithms' main idea and algorithmic techniques, and omit the details of them.

关键词： NP-hard parameterized complexity FPT W[t]-hard AI IoT

来源：评论

学校读者我要写书评

暂无评论

Graph separators: a parameterized view

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2003年第4期67卷 808-832页

作者： Alber, J Fernau, H Niedermeier, R Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany

Graph separation is a well-known tool to make (hard) graph problems accessible to a divide-and-conquer approach. We show how to use graph separator theorems in combination with (linear) problem kernels in order to develop fixed parameter algorithms for many well-known NP-hard (planar) graph problems. We coin the key notion of glueable select&verify graph problems and derive from that a prospective way to easily check whether a planar graph problem will allow for a fixed parameter algorithm of running time c(rootk)n(o(1)) for constant c. One of the main contributions of the paper is to exactly compute the base c of the exponential term and its dependence on the various parameters specified by the employed separator theorem and the underlying graph problem. We discuss several strategies to improve on the involved constant c. (C) 2003 Elsevier Science (USA). All rights reserved.

关键词： planar graph problems fixed parameter tractability parameterized complexity graph separator theorems divide-and-conquer algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：