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

On the complexity of coloring (r, l)-graphs

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH 2021年第6期28卷 3172-3189页

作者： Alves, Matheus S. D. Nascimento, Julliano R. Souza, Ueverton S. Univ Fed Fluminense Inst Comp Av Gal Milton Tavares Souza S-N BR-24210346 Niteroi RJ Brazil Univ Fed Goias Inst Informat Quadra DCampus Samambaia BR-74690900 Goiania Go Brazil

An (r, l)-graph is a graph that can be partitioned into r independent sets and l cliques. In the Graph Coloring problem, we are given as input a graph G, and the objective is to determine the minimum integer k such that G admits a proper vertex k-coloring. In this work, we describe a Poly versus NP-hard dichotomy of this problem regarding the parameters r and l of (r, l)-graphs, which determine the boundaries of the NP-hardness of Graph Coloring for such classes. We also analyze the complexity of the problem on (r, l)-graphs under the parameterized complexity perspective. We show that given a (2, 1)-partition S-1,S-2,K-1 of a graph G, finding an optimal coloring of G is NP-complete even when K-1 is a maximal clique of size 3;XP but W[1]-hard when parameterized by min{vertical bar S-1 vertical bar,vertical bar S-2 vertical bar};fixed-parameter tractable (FPT) and admits a polynomial kernel when parameterized by max{vertical bar S-1 vertical bar,vertical bar S-2 vertical bar}. Besides, concerning the case where K-1 is a maximal clique of size 3, a P versus NPh dichotomy regarding the neighborhood of K-1 is provided;furthermore, an FPT algorithm parameterized by the number of vertices having no neighbor in K-1 is presented.

关键词： colorability graph coloring (r, l)-graph list coloring bipartite graphs parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The Small Set Vertex Expansion Problem

引用

THEORETICAL COMPUTER SCIENCE 2021年 886卷 84-93页

作者： Agrawal, Garima Maity, Soumen Indian Inst Sci Educ & Res Pune Maharashtra India

In the SMALL SET VERTEX EXPANSION (SSVE) problem, we are given a graph G = (V, E) and a positive integer k <= vertical bar V(G)vertical bar/2, the goal is to return a set S subset of V (G) of k nodes minimizing the vertex expansion Phi(V) (S) = vertical bar N(S)vertical bar. The SMALL SET VERTEX EXPANSION problem has not been as well studied as its edge-based counterpart SMALL SET EXPANSION (SSE). SSE, and SSVE to a less extend, have been studied due to their connection to other hard problems including the Unique Games Conjecture and Graph Colouring. The SMALL SET VERTEX EXPANSION is known to be NP-complete. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is W[1]-hard when parameterized by the solution size, (2) the problem is fixed-parameter tractable (FPT) when parameterized by the neighbourhood diversity of the input graph, (3) it can be solved in polynomial time for graphs of bounded clique-width, and (4) it is fixed-parameter tractable (FPT) when parameterized by treewidth of the input graph. (C) 2021 Elsevier B.V. All rights reserved.

关键词： parameterized complexity FPT W[1]-hard Treewidth Clique width Neighbourhood diversity

来源：评论

学校读者我要写书评

暂无评论

A parameterized perspective on protecting elections

引用

THEORETICAL COMPUTER SCIENCE 2021年 874卷 15-31页

作者： Dey, Palash Misra, Neeldhara Nath, Swaprava Shakya, Garima Indian Inst Technol Kharagpur W Bengal India Indian Inst Technol Gandhinagar India Indian Inst Technol Kanpur Uttar Pradesh India

We study the parameterized complexity of the OPTIMAL DEFENSE and OPTIMAL ATTACK problems in voting. In both the problems, the input is a set of voter groups (every voter group is a district consisting of a set of votes) and two integers k(a) and k(d) corresponding to respectively the number of voter groups the attacker can attack and the number of voter groups the defender can defend. A voter group gets removed from the election if it is attacked but not defended. In the OPTIMAL DEFENSE problem, we want to know if it is possible for the defender to commit to a strategy of defending at most k(d) voter groups such that, no matter which k(a) voter groups the attacker attacks, the outcome of the election does not change. In the OPTIMAL ATTACK problem, we want to know if it is possible for the attacker to commit to a strategy of attacking k(a) voter groups such that, no matter which k(d) voter groups the defender defends, the outcome of the election is always different from the original one (without any attack). We show that both the OPTIMAL DEFENSE problem and the OPTIMAL ATTACK problem are computationally intractable for every scoring rule and the Condorcet voting rule even when we have only 3 candidates. We also show that the OPTIMAL DEFENSE problem for every scoring rule and the Condorcet voting rule is W[2]-hard for both the parameters k(a) and k(d), while it admits a fixed parameter tractable algorithm parameterized by the combined parameter (k(a), k(d)). The OPTIMAL ATTACK problem for every scoring rule and the Condorcet voting rule turns out to be much harder - it is W[1] hard even for the combined parameter (k(a), k(d)). We propose two greedy algorithms for the OPTIMAL DEFENSE problem and empirically show that they perform effectively on many voting profiles. (C) 2021 Elsevier B.V. All rights reserved.

关键词： parameterized complexity Election control Optimal attack Optimal defense

来源：评论

学校读者我要写书评

暂无评论

A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows

引用

DISCRETE APPLIED MATHEMATICS 2021年 290卷 1-6页

作者： Alix, Munier Kordon Sorbonne Univ LIP6 CNRS F-75005 Paris France

This paper proves that the existence of a feasible schedule for a set of dependent tasks of unit execution times with release dates and deadlines on a limited number of processors is a fixed-parameter tractable problem. The parameter considered is the pathwidth of the interval graph associated with the time windows of the tasks. A fixed-parameter algorithm based on a dynamic programming approach is developed and proved to solve this decision problem. Fixed-parameter algorithms for the two classical problems P vertical bar prec, p(i) = 1, r(i)vertical bar C-max and P vertical bar prec, p(i) = 1, r(i)vertical bar L-max are then derived using a binary search. They are, as far as we know, the first fixed-parameter algorithms for these scheduling problems. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Parallel identical machines Makespan Maximum lateness parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Distance from Triviality 2.0: Hybrid Parameterizations 33rd

Distance from Triviality 2.0: Hybrid Parameterizations

引用

33rd International Workshop on Combinatorial Algorithms (IWOCA)

作者： Agrawal, Akanksha Ramanujan, M. S. Indian Inst Technol Madras Chennai Tamil Nadu India Univ Warwick Coventry W Midlands England

ISBN: (纸本)9783031066788;9783031066771

Vertex deletion problems have been at the heart of numerous major advances in Algorithms and Combinatorial Optimization, and especially so in the area of parameterized complexity. For a family of graphs H, the input to Vertex Deletion to H is a graph G and an integer k, and the objective is to decide whether there is a vertex-subset, called a modulator, whose removal from G results in a graph contained in the family H, and such that |S| <= k. Traditionally, the majority of the study of Vertex Deletion to H problems in parameterized complexity has been limited to parameterization by modulator size and structural graph width measures of the input graph such as treewidth. Recent years have seen systematic efforts at: i) quantifying the complexity of modulators in ways other than their size, and ii) studying the complexity landscape of various graph problems under parameterizations that are simultaneously better than both the modulator size and certain width measures of the graph. In this talk we will look at some exciting developments in this direction in relation to two such parameters that are "hybridizations" of the modulator size, and the well-explored graph parameters - treewidth and treedepth.

关键词： parameterized complexity Vertex deletion Elimination distance H-treewidth

来源：评论

学校读者我要写书评

暂无评论

An improved kernel for the flip distance problem on simple convex polygons

引用

INFORMATION PROCESSING LETTERS 2023年 182卷

作者： Bosch-Calvo, Miguel Kelk, Steven USI SUPSI IDSIA Lugano Switzerland Maastricht Univ Dept Data Sci & Engn Maastricht Netherlands

The complexity of computing the flip distance between two triangulations of a simple convex polygon is unknown. Here we approach the problem from a parameterized complexity perspective and improve upon the 2k kernel of Lucas [12]. Specifically, we describe a kernel of size 4k3 and then show how it can be improved to (1 + c)k for every constant c > 0. By ensuring that the kernel consists of a single instance our result yields a kernel of the same magnitude (up to additive terms) for the almost equivalent rotation distance problem on rooted, ordered binary trees. The earlier work of Lucas left the kernel as a disjoint set of instances, potentially allowing very minor differences in the definition of the size of instances to accumulate, causing a constant-factor distortion in the kernel size when switching between flip distance and rotation distance formulations. Our approach avoids this sensitivity. We have also undertaken experiments to understand how much reduction is achieved by our kernel in practice.(c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

关键词： Algorithms parameterized complexity Kernel Triangulation Simple convex polygons

来源：评论

学校读者我要写书评

暂无评论

Subexponential parameterized Algorithms and Kernelization on Almost Chordal Graphs

引用

ALGORITHMICA 2021年第7期83卷 2170-2214页

作者： Fomin, Fedor, V Golovach, Petr A. Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway

We study algorithmic properties of the graph class CHORDAL-ke, that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. It appears that a number of fundamental intractable optimization problems being parameterized by k admit subexponential algorithms on graphs from CHORDAL-ke. More precisely, we identify a large class of optimization problems on CHORDAL-ke solvable in time 2O((root k log k)) center dot n(O(1)). Examples of the problems from this class are finding an independent set of maximum weight, finding a feedback vertex set or an odd cycle transversal of minimum weight, or the problem of finding a maximum induced planar subgraph. On the other hand, we show that for some fundamental optimization problems, like finding an optimal graph coloring or finding a maximum clique, are FPT on CHORDAL-ke when parameterized by k but do not admit subexponential in k algorithms unless ETH fails. Besides subexponential time algorithms, the class of CHORDAL-ke graphs appears to be appealing from the perspective of kernelization (with parameter k). While it is possible to show that most of the weighted variants of optimization problems do not admit polynomial in k kernels on CHORDAL-ke graphs, this does not exclude the existence of Turing kernelization and kernelization for unweighted graphs. In particular, we construct a polynomial Turing kernel for Weighted Clique on CHORDAL-ke graphs. For (unweighted) Independent Set we design polynomial kernels on two interesting subclasses of CHORDAL-ke, namely, INTERVAL-ke and SPLIT-ke graphs.

关键词： parameterized complexity Structural parameterization Subexponential algorithms Kernelization Chordal graphs Fill-in Independent set Clique Coloring

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized Algorithm for Cluster Vertex Deletion

引用

THEORY OF COMPUTING SYSTEMS 2021年第2期65卷 323-343页

作者： Tsur, Dekel Ben Gurion Univ Negev Beer Sheva Israel

In the Cluster Vertex Deletion problem the input is a graph G and an integer k. The goal is to decide whether there is a set of vertices S of size at most k such that the deletion of the vertices of S from G results in a graph in which every connected component is a clique. We give an algorithm for Cluster Vertex Deletion whose running time is O*(1.811(k)).

关键词： Graph algorithms parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized Intractability of Even Set and Shortest Vector Problem

引用

JOURNAL OF THE ACM 2021年第3期68卷 1–40页

作者： Bhattacharyya, Arnab Bonnet, Edouard Egri, Laszlo Ghoshal, Suprovat Karthik, C. S. Lin, Bingkai Manurangsi, Pasin Marx, Daniel Natl Univ Singapore NUS Sch Comp COM2-03-4413 Comp Dr Singapore 117417 Singapore Univ Claude Bernard Lyon 1 LIP UMR5668 ENS Lyon CNRS Villeurbanne France Hungarian Acad Sci Inst Comp Sci & Control Kende U 13 H-1111 Budapest Hungary Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India Weizmann Inst Sci Jacob Ziskind Bldg IL-76100 Rehovot Israel Nanjing Univ Nanjing Peoples R China Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA CISPA Helmholtz Ctr Informat Secur Campus E1 4Room 304 Saarland Informat Campus D-66123 Saarbrucken Germany

The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over F-2, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k, or, in other words, whether there is a nonzero vector x such that Ax has at most k nonzero coordinates. The question of whether k-Even Set is fixed parameter tractable (FPT) parameterized by the distance k has been repeatedly raised in the literature;in fact, it is one of the few remaining open questions from the seminal book of Downey and Fellows [1999]. In this work, we show that k-Even Set is W[1]-hard under randomized reductions. We also consider the parameterized k-Shortest Vector Problem (SVP), in which we are given a lattice whose basis vectors are integral and an integer k, and the goal is to determine whether the norm of the shortest vector (in the l(p) norm for some fixed p) is at most k. Similar to k-Even Set, understanding the complexity of this problem is also a long-standing open question in the field of parameterized complexity. We show that, for any p > 1, k-SVP is W[1]-hard to approximate (under randomized reductions) to some constant factor.

关键词： parameterized complexity inapproximability even set minimum distance problem shortest vector problem

来源：评论

学校读者我要写书评

暂无评论

A Polynomial Kernel for Distance-Hereditary Vertex Deletion

引用

ALGORITHMICA 2021年第7期83卷 2096-2141页

作者： Kim, Eun Jung Kwon, O-joung Univ Paris 09 CNRS Pl Marechal Lattre Tassigny F-75775 Paris 16 France Incheon Natl Univ Dept Math Incheon South Korea Inst Basic Sci IBS Discrete Math Grp Daejeon South Korea

A graph is distance-hereditary if for any pair of vertices, their distance in every connected induced subgraph containing both vertices is the same as their distance in the original graph. The DISTANCE-HEREDITARY VERTEX DELETION problem asks, given a graph G on n vertices and an integer k, whether there is a set S of at most k vertices in G such that G - S is distance-hereditary. This problem is important due to its connection to the graph parameter rank-width because distance-hereditary graphs are exactly the graphs of rank-width at most 1. Eiben, Ganian, and Kwon (JCSS' 18) proved that DISTANCE-HEREDITARY VERTEX DELETION can be solved in time 2(O(k)) n(O(1)), and asked whether it admits a polynomial kernelization. We show that this problem admits a polynomial kernel, answering this question positively. For this, we use a similar idea for obtaining an approximate solution for CHORDAL VERTEX DELETION due to Jansen and Pilipczuk (SIDMA' 18) to obtain an approximate solution with O(k(3) log n + k(2) log(2) n) vertices when the problem is a YEs-instance, and we exploit the structure of split decompositions of distance-hereditary graphs to reduce the total size.

关键词： parameterized complexity Polynomial kernel Distance-hereditary graph Rank-width

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：