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

On the kernelization of split graph problems

THEORETICAL COMPUTER SCIENCE 2018年 734卷 72-82页

作者： Yang, Yongjie Shrestha, Yash Raj Li, Wenjun Guo, Jiong Cent S Univ Sch Informat Sci & Engn Changsha Hunan Peoples R China Swiss Fed Inst Technol Dept Management Technol & Econ Zurich Switzerland Changsha Univ Sci & Technol Sch Comp & Commun Engn Hunan Prov Key Lab Intelligent Proc Big Data Tran Changsha Hunan Peoples R China Shandong Univ Sch Comp Sci & Technol Jinan Shandong Peoples R China

A split graph is a graph whose vertices can be partitioned into a clique and an independent set. We study numerous problems on split graphs, namely the k-VERTEx-DISJOINT PATHS, k-CYCLE, k-PATH and k-l-STABLE SET problems. In the k-VERTEX-DISJOINT PATHS problem, we are given a graph and k terminal pairs of vertices, and are asked whether there is a set of k vertex-disjoint paths linking these terminal pairs, respectively. In the k-CYCLE/k-PATH problem, we are given a graph and are asked whether there is a path/cycle of length k. The k-l-STABLE SET problem takes a graph and an integer k as input, and asks whether the graph has a subset of k vertices such that the distance between every two vertices in the subset is at least l + 1. It is known that all the above problems are NP-complete on split graphs. We derive a 4k-vertex kernel for the k-VERTEx-DISJOINT PATHS problem and an O(k(2))-vertex kernel for both the k-PATH problem and the k-CYCLE problem. Concerning the k-l-STABLE SET problem, for l = 1 or l >= 3, the problem is polynomial-time solvable on split graphs. For l = 2, we prove that the k-l-STABLE SET problem is W[1]-complete on split graphs, with respect to k. However, if the given split graph contains no K-1,K-r as an induced subgraph, and every vertex in the independent set of the split graph has degree at most d, we derive a linear vertex kernel for the k-2-STABLE SET problem, where both r and d are constants. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Split graph Kernelization parameterized complexity k-path k-cycle Crown decomposition

来源：评论

学校读者我要写书评

暂无评论

Fixing improper colorings of graphs

引用

THEORETICAL COMPUTER SCIENCE 2018年 711卷 66-78页

作者： Garnero, Valentin Junosza-Szaniawski, Konstanty Liedloff, Mathieu Montealegre, Pedro Rzazewski, Pawel Univ Orleans INSA Ctr Val de Loire LIFO F-45067 Orleans France Warsaw Univ Technol Fac Math & Informat Sci Warsaw Poland Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control Budapest Hungary

In this paper we consider a variation of a recoloring problem, called the Color-Fixing. Let us have some non-proper r-coloring phi of a graph G. We investigate the problem of finding a proper r-coloring of G, which is "the most similar" to phi, i.e., the number k of vertices that have to be recolored is minimum possible. We observe that the problem is NP-complete for any fixed r >= 3, even for bipartite planar graphs. Moreover, it is W[1]-hard even for bipartite graphs, when parameterized by the number k of allowed recoloring transformations. On the other hand, the problem is fixed-parameter tractable, when parameterized by k and the number r of colors. We provide a 2(n) . n(O(1)) algorithm for the problem and a linear algorithm for graphs with bounded treewidth. We also show several lower complexity bounds, using standard complexity assumptions. Finally, we investigate the facing number of a graph G. It is the minimum k such that k recoloring transformations are sufficient to transform any coloring of G into a proper one. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Fixing number Reconfiguration parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

MULTICUT IS FPT

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

parameterized algorithms for conflict-free colorings of graphs

引用

THEORETICAL COMPUTER SCIENCE 2018年 745卷 53-62页

作者： Reddy, I. Vinod Indian Inst Technol Gandhinagar India

In this paper, we study the conflict-free coloring of graphs induced by neighborhoods. A coloring of a graph is conflict-free if every vertex has a uniquely colored vertex in its neighborhood. The conflict-free coloring problem is to color the vertices of a graph using the minimum number of colors such that the coloring is conflict-free. We consider both closed neighborhoods, where the neighborhood of a vertex includes itself, and open neighborhoods, where a vertex does not include in its neighborhood. We study the parameterized complexity of conflict-free closed neighborhood coloring and conflict-free open neighborhood coloring problems. We show that both problems are fixed-parameter tractable (FPT) when parameterized by the cluster vertex deletion number of the input graph. This generalizes the result of Gargano and Rescigno [Theoretical Computer Science, 2015] that conflict-free coloring is FPT parameterized by the vertex cover number. Also, we show that both problems admit an additive constant approximation algorithm when parameterized by the distance to threshold graphs. We also study the complexity of the problem on special graph classes. For split graphs, we give a polynomial time algorithm for closed neighborhood conflict-free coloring problem, whereas we show that open neighborhood conflict-free coloring is NP-complete. For cographs, we show that conflict-free closed neighborhood coloring can be solved in polynomial time and conflict-free open neighborhood coloring need at most three colors. We show that interval graphs can be conflict-free colored using at most four colors. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Conflict-free coloring parameterized complexity NP-complete

来源：评论

学校读者我要写书评

暂无评论

Reconfiguration on sparse graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2018年 95卷 122-131页

作者： Lokshtanov, Daniel Mouawad, Amer E. Panolan, Fahad Ramanujan, M. S. Saurabh, Saket Univ Bergen Bergen Norway TU Wien Vienna Austria Inst Math Sci Madras Tamil Nadu India

A vertex-subset graph problem Q defines which subsets of the vertices of an input graph are feasible solutions. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size k, whether it is possible to transform one into the other by a sequence of vertex additions/deletions such that each intermediate set remains a feasible solution of size bounded by k. We study reconfiguration variants of two classical vertex subset problems, namely INDEPENDENT SET and DOMINATING SET. We denote the former by ISR and the latter by DSR. Both ISR and DSR are PSPACE-complete on graphs of bounded bandwidth and w [1.]-hard parameterized by k on general graphs. We show that ISR is fixed-parameter tractable parameterized by k when the input graph is of bounded degeneracy or nowhere dense. For DSR, we show the problem fixed-parameter tractable parameterized by k when the input graph does not contain large bicliques. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Reconfiguration Dominating set Independent set Sparse graphs parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

COVERING VECTORS BY SPACES: REGULAR MATROIDS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2018年第4期32卷 2512-2565页

作者： Fomin, Fedor, V Golovach, Petr A. Lokshtanov, Daniel Saurabh, Saket Univ Bergen Dept Informat Bergen Norway Inst Math Sci Madras Tamil Nadu India

Seymour's decomposition theorem for regular matroids is a fundamental result with a number of combinatorial and algorithmic applications. In this work we demonstrate how this theorem can be used in the design of parameterized algorithms on regular matroids. We consider the problem of covering a set of vectors of a given finite dimensional linear space (vector space) by a subspace generated by a set of vectors of minimum size. Specifically, in the SPACE COVER problem, we are given a matrix M and a subset of its columns T;the task is to find a minimum set F of columns of M disjoint with T such that the linear span of F contains all vectors of T. For graphic matroids this problem is essentially STEINER FOREST and for cographic matroids this is a generalization of MULTIWAY CUT. Our main result is the algorithm with running time 2(Oh(k)) . parallel to M parallel to(Oh(1)) solving SPACE COVER in the case when M is a totally unimodular matrix over rationals, where k is the size of F. In other words, we show that on regular matroids the problem is fixed-parameter tractable parameterized by the rank of the covering subspace.

关键词： regular matroids spanning set parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Kernels for deletion to classes of acyclic digraphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2018年 92卷 9-21页

作者： Agrawal, Akanksha Saurabh, Saket Sharma, Roohani Zehavi, Meirav Univ Bergen Bergen Norway HBNI Inst Math Sci Bombay Maharashtra India

Given a digraph D and an integer k, DIRECTED FEEDBACK VERTEX SET (DFVS) asks whether there exists a set of vertices S of size at most k such that F = D \ S is DAG. Mnich and van Leeuwen [STACS 2016] considered the kernelization complexity of DFVS with an additional restriction on F, namely that F must be an out-forest (OUT-FOREST VERTEX DELETION SET), an out-tree (OUT-TREE VERTEX DELETION SET), or a (directed) pumpkin (PUMPKIN VERTEX DELETION SET). Their objective was to shed light on the kernelization complexity of DFVS, a well-known open problem in parameterized complexity. We improve the kernel sizes of OUT-FOREST VERTEX DELETION SET from O(k(3)) to O(k(2)) and of PUMPKIN VERTEX DELETION SET from O(k(18)) to O(k(3)). We also prove that the former kernel size is tight under certain complexity theoretic assumptions. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Out-forest Pumpkin parameterized complexity Kernelization

来源：评论

学校读者我要写书评

暂无评论

Meta-kernelization using well-structured modulators

引用

DISCRETE APPLIED MATHEMATICS 2018年 248卷 153-167页

作者： Eiben, Eduard Ganian, Robert Szeider, Stefan TU Wien Algorithms & Complex Grp Vienna Austria

Kernelization investigates exact preprocessing algorithms with performance guarantees. The most prevalent type of parameters used in kernelization is the solution size for optimization problems: however, also structural parameters have been successfully used to obtain polynomial kernels for a wide range of problems. Many of these parameters can be defined as the size of a smallest modulator of the given graph into a fixed graph class (i.e., a set of vertices whose deletion puts the graph into the graph class). Such parameters admit the construction of polynomial kernels even when the solution size is large or not applicable. This work follows up on the research on meta-kernelization frameworks in terms of structural parameters. We develop a class of parameters which are based on a more general view on modulators: instead of size, the parameters employ a combination of rank-width and split decompositions to measure structure inside the modulator. This allows us to lift kernelization results from modulator-size to more general parameters, hence providing small kernels even in cases where previously developed approaches could not be applied. We show (i) how such large but well-structured modulators can be efficiently approximated, (ii) how they can be used to obtain polynomial kernels for graph problems expressible in Monadic Second Order logic, and (iii) how they support the extension of previous results in the area of structural meta-kernelization. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Kernelization parameterized complexity Structural parameters Rank-width Split decompositions

来源：评论

学校读者我要写书评

暂无评论

Ruling out FPT algorithms for Weighted Coloring on forests

引用

THEORETICAL COMPUTER SCIENCE 2018年 729卷 11-19页

作者： Araujo, Julio Baste, Julien Sau, Ignasi Univ Fed Ceara Dept Matemat Fortaleza Ceara Brazil Univ Montpellier LIRMM CNRS Montpellier France

Given a graph G, a proper k-coloring of G is a partition c = (Si)i is an element of[0,k-1] of V(G) into k stable sets S0,...,Sk-1. Given a weight function w : V (G) -> R+, the weight of a color S-i is defined as w(i) = max(v is an element of Si) w(v) and the weight of a coloring c as w(c) = Sigma(k-1)(i-0) w(i). Guan and Zhu (1997) [11] defined the weighted chromatic number of a pair (G, w), denoted by sigma(G, w), as the minimum weight of a proper coloring of G. For a positive integer r, they also defined sigma(G, w;r) as the minimum of w(c) among all proper r-colorings c of G. The complexity of determining sigma(G, w) when G is a tree was open for almost 20 years, until Araujo et al. (2014) [1] recently proved that the problem cannot be solved in time n(o(logn)) on n-vertex trees unless the Exponential Time Hypothesis (ETH) fails. The objective of this article is to provide hardness results for computing sigma(G, w) and sigma(G, w;r) when G is a tree or a forest, relying on complexity assumptions weaker than the ETH. Namely, we study the problem from the viewpoint of parameterized complexity, and we assume the weaker hypothesis FPT not equal W[1]. Building on the techniques of Araujo et al., we prove that when G is a forest, the decision problem of computing sigma(G, w) is W[1]-hard parameterized by the size of a largest connected component of G, and that computing sigma(G, w;r) is W[2]-hard parameterized by r. Our results rule out the existence of FPT algorithms for computing these invariants on trees or forests for many natural choices of the parameter. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Weighted coloring Max-coloring Forests parameterized complexity W[1]-hard

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：