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

p-Edge/vertex-connected vertex cover: parameterized and approximation algorithms

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2023年 133卷 23-40页

作者： Einarson, Carl Gutin, Gregory Jansen, Bart M. P. Majumdar, Diptapriyo Wahlstrom, Magnus Royal Holloway Univ London Egham Surrey England Eindhoven Univ Technol Eindhoven Netherlands Indraprastha Inst Informat Technol Delhi New Delhi India

We introduce and study two natural generalizations of the Connected Vertex Cover (VC) problem: the p-Edge-Connected and p-Vertex-Connected VC problem (where p >= 2 is a fixed integer). We obtain an 2O(pk)nO(1)-time algorithm for p-Edge-Connected VC and an 2O(k2)nO(1)-time algorithm for p-Vertex-Connected VC. Thus, like Connected VC, both constrained VC problems are FPT. Furthermore, like Connected VC, neither problem admits a polynomial kernel unless NP subset of coNP/poly, which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. Finally, we describe a 2(p + 1)-approximation algorithm for the p-Edge-Connected VC. The proofs for the new VC problems require more sophisticated arguments than for Connected VC. In particular, for the approximation algorithm we use Gomory-Hu trees and for the approximate kernels a result on small-size spanning p- vertex/edge-connected subgraphs of a p-vertex/edge-connected graph by Nishizeki and Poljak (1994) [30] and Nagamochi and Ibaraki (1992) [27].(c) 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Vertex cover Connectivity parameterized algorithms Kernels Approximate kernels Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized Approximation algorithms for Weighted Vertex Cover 16th

Parameterized Approximation Algorithms for Weighted Vertex C...

引用

16th Latin American Symposium on Theoretical Informatics (LATIN)

作者： Mandal, Soumen Misra, Pranabendu Rai, Ashutosh Saurabh, Saket IIT Delhi Dept Math New Delhi India Chennai Math Inst Chennai Tamil Nadu India Inst Math Sci Chennai Tamil Nadu India Univ Bergen Bergen Norway

ISBN: (纸本)9783031556005;9783031556012

A vertex cover of a graph is a set of vertices of the graph such that every edge has at least one endpoint in it. In this work, we study WEIGHTED VERTEX COVER with solution size as a parameter. Formally, in the (k, W)-VERTEX COVER problem, given a graph G, an integer k, a positive rational W, and a weight function w : V (G) -> Q(+), the question is whether G has a VERTEX COVER of size at most k of weight at most W, with k being the parameter. An (a, b)-bi-criteria approximation algorithm for (k, W)-VERTEX COVER either produces a vertex cover S such that |S| <= ak and w(S) <= bW, or decides that there is no vertex cover of size at most k of weight at most W. We obtain the following results. - A simple (2, 2)-bi-criteria approximation algorithm for (k, W)-VERTEX COVER in polynomial time by modifying the standard LP-rounding algorithm. - A simple exact parameterized algorithm for (k, W)-VERTEX COVER running in O* (1.4656(k)) time (Here, the O* notation hides factors polynomial in n.). - A(1+epsilon, 2)-approximation algorithm for (k, W)-VERTEX COVER running in O* (1.4656((1- epsilon)k)) time. - A (1.5, 1.5)-approximation algorithm for (k, W)-VERTEX COVER running in O* (1.414(k)) time. - A (2 - delta, 2 - delta)-approximation algorithm for (k, W)-VERTEX COVER running in O* (Sigma(i= delta k(1-2 delta)/1+2 delta) (delta k(1-2 delta)/2 delta) ((delta k+i)(delta k-2i delta/1-2 delta))) time for any delta < 0.5. For example, for (1.75, 1.75) and (1.9, 1.9)-approximation algorithms, we get running times of O* (1.272k) and O* (1.151k) respectively. Our algorithms (expectedly) do not improve upon the running times of the existing algorithms for the unweighted version of Vertex Cover. When compared to algorithms for the weighted version, our algorithms are the first ones to the best of our knowledge which work with arbitrary weights, and they perform well when the solution size is much smaller than the total weight of the desired solution.

关键词： Weighted Vertex Cover parameterized algorithms Approximation algorithms parameterized Approximation

来源：评论

学校读者我要写书评

暂无评论

Improved parameterized algorithms and kernels for mixed domination

引用

THEORETICAL COMPUTER SCIENCE 2020年 815卷 109-120页

作者： Xiao, Mingyu Sheng, Zimo Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

A mixed domination of a graph G =(V, E) is a mixed set Dof vertices and edges such that for every edge or vertex, if it is not in D, then it is adjacent or incident to at least one vertex or edge in D. TheMixed Dominationproblem is to check whether there is a mixed domination of size at most kin a graph. Mixed domination is a mixture concept of vertex domination and edge domination, and the mixed domination problem has been studied from the view of approximation algorithms, parameterized algorithms, and so on. In this paper, we give a branch-and-search algorithm with running time bound of O*(4.172k), which improves the previous bound of O* (7.465k). For kernelization, it is known that the problem parameterized by kin general graphs is unlikely to have a polynomial kernel. We show the problem in planar graphs allows linear kernel by giving a kernel of 11k - 16 vertices. (C) 2020 Elsevier B.V. All rights reserved.

关键词： parameterized algorithms Mixed domination Graph algorithms Kernelization Branch-and-search

来源：评论

学校读者我要写书评

暂无评论

Covering Small Independent Sets and Separators with Applications to parameterized algorithms

引用

ACM TRANSACTIONS ON algorithms 2020年第3期16卷 1–31页

作者： Lokshtanov, Daniel Panolan, Fahad Saurabh, Saket Sharma, Roohani Zehavi, Meirav Univ Calif Santa Barbara Santa Barbara CA 93106 USA IIT Hyderabad Dept Comp Sci & Engn Sangareddy India HBNI Inst Math Sci Chennai Tamil Nadu India Univ Bergen Bergen Norway Ben Gurion Univ Negev Beer Sheva Israel

We present two new combinatorial tools for the design of parameterized algorithms. The first is a simple linear time randomized algorithm that given as input a d-degenerate graph G and an integer k, outputs an independent set Y, such that for every independent set X in G of size at most k, the probability that X is a subset of Y is at least ((((d+1)k)(k)) . k(d + 1))(-1). The second is a new (deterministic) polynomial time graph sparsification procedure that given a graph G, a set T = {{s(1), t(1)}, {s(2), t(2)},..., {s(l), t(l)}} of terminal pairs, and an integer k, returns an induced subgraph G(star) of G that maintains all the inclusion minimal multicuts of G of size at most k and does not contain any (k + 2)-vertex connected set of size 2(O(k)). In particular, G(star) excludes a clique of size 2(O(k)) as a topological minor. Put together, our new tools yield new randomized fixed parameter tractable (FPT) algorithms for Stable s-t Separator, StableOdd Cycle Transversal, and Stable Multicut on general graphs, and for Stable Directed Feedback Vertex Set on d-degenerate graphs, resolving two problems left open byMarx et al. [ACMTransactions on algorithms, 2013]. All of our algorithms can be derandomized at the cost of a small overhead in the running time.

关键词： Independece covering family stable multicut stable s-t separator stable OCT parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved parameterized algorithms for Mixed Domination 13th

Improved Parameterized Algorithms for Mixed Domination

引用

13th International Conference on Algorithmic Aspects in Information and Management (AAIM)

作者： Xiao, Mingyu Sheng, Zimo Univ Elect Sci & Technol China Chengdu Peoples R China

ISBN: (纸本)9783030271954;9783030271947

A mixed domination of a graph G = (V, E) is a mixed set D of vertices and edges such that for every edge or vertex, if it is not in D, then it is adjacent or incident to at least one vertex or edge in D. The Mixed Domination problem is to check whether there is a mixed domination of size at most k in a graph. Mixed domination is a mixture concept of vertex domination and edge domination, and the mixed domination problem has been studied from the view of approximation algorithms, parameterized algorithms, and so on. In this paper, we give a branch-and-search algorithm with running time bound of O* (4.172(k)), which improves the previous bound of O* (7.465(k)). For kernelization, it is known that the problem parameterized by k in general graphs is unlikely to have a polynomial kernel. We show the problem in planar graphs allows linear kernels by giving a kernel of 11k vertices.

关键词： parameterized algorithms Mixed Domination Graph algorithms Kernelization Branch-and-search

来源：评论

学校读者我要写书评

暂无评论

On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs 59

On subexponential parameterized algorithms for Steiner Tree ...

引用

59th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Marx, Daniel Pilipczuk, Marcin Pilipczuk, Michal Hungarian Acad Sci MTA SZTAKI Inst Comp Sci & Control Budapest Hungary Univ Warsaw Inst Informat Warsaw Poland

ISBN: (纸本)9781538642306

There are numerous examples of the so-called "square root phenomenon" in the field of parameterized algorithms: many of the most fundamental graph problems, parameterized by some natural parameter k, become significantly simpler when restricted to planar graphs and in particular the best possible running time is exponential in O(root k) instead of O(k) (modulo standard complexity assumptions). We consider two classic optimization problems parameterized by the number of terminals. The STEINER TREE problem asks for a minimum-weight tree connecting a given set of terminals T in an edge-weighted graph. In the SUBSET TRAVELING SALESMAN problem we are asked to visit all the terminals T by a minimum-weight closed walk. We investigate the parameterized complexity of these problems in planar graphs, where the number k - vertical bar T vertical bar of terminals is regarded as the parameter. Our results are the following: SUBSET TSP can be solved in time 2(O(root k log k)).n(O(1)) even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [SODA 2014] with the same running time that worked only on undirected planar graphs with polynomially large integer weights. Assuming the Exponential-Time Hypothesis, STEINER TREE on undirected planar graphs cannot be solved in time 2(o(k)).n(O(1)), even in the unit-weight setting. This lower bound makes STEINER TREE the first "genuinely planar" problem (i.e., where the input is only planar graph with a set of distinguished terminals) for which we can show that the square root phenomenon does not appear. STEINER TREE can be solved in time n(O(root k)).W on undirected planar graphs with maximum edge weight W. Note that this result is incomparable to the fact that the problem is known to be solvable in time 2(k).n(O(1)) even in general graphs. A direct corollary of the combination of our results for STEINER TREE is that this problem does not admit a parameter-preserving polynomial kernel on planar graphs un

关键词： Steiner tree subexponential algorithms parameterized algorithms planar graphs

来源：评论

学校读者我要写书评

暂无评论

parameterized and Approximation algorithms for the Load Coloring Problem

引用

ALGORITHMICA 2017年第1期79卷 211-229页

作者： Barbero, F. Gutin, G. Jones, M. Sheng, B. Royal Holloway Univ London Egham TW20 0EX Surrey England

Let c, k be two positive integers. Given a graph , the c-Load Coloring problem asks whether there is a c-coloring such that for every , there are at least k edges with both endvertices colored i. Gutin and Jones (Inf Process Lett 114:446-449, 2014) studied this problem with . They showed 2-Load Coloring to be fixed-parameter tractable (FPT) with parameter k by obtaining a kernel with at most 7k vertices. In this paper, we extend the study to any fixed c by giving both a linear-vertex and a linear-edge kernel. In the particular case of , we obtain a kernel with less than 4k vertices and less than edges. These results imply that for any fixed , c-Load Coloring is FPT and the optimization version of c-Load Coloring (where k is to be maximized) has an approximation algorithm with a constant ratio.

关键词： parameterized algorithms Kernels FPT Approximation algorithms Load coloring

来源：评论

学校读者我要写书评

暂无评论

Almost Induced Matching: Linear Kernels and parameterized algorithms 1

引用

42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Xiao, Mingyu Kou, Shaowei UESTC Sch Comp Sci & Engn Chengdu 611731 Peoples R China UESTC Med Informat Ctr Chengdu 611731 Peoples R China

ISBN: (数字)9783662535363

ISBN: (纸本)9783662535363;9783662535356

The Almost Induced Matching problem asks whether we can delete at most k vertices from a graph such that the remaining graph is an induced matching, i.e., a graph with each vertex of degree 1. This paper studies parameterized algorithms for this problem by taking the size of deletion set k as the parameter. By using the techniques of finding maximal 3-path packings and an extended crown decomposition, we obtain the first linear vertex kernel for this problem, improving the previous quadratic kernel. We also present an O*(1.7485(k))-time and polynomial-space algorithm, which is the best known parameterized algorithm for this problem.

关键词： Maximum induced matching Linear kernel parameterized algorithms Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Computation of Representative Families with Applications in parameterized and Exact algorithms

引用

JOURNAL OF THE ACM 2016年第4期63卷 1–60页

作者： Fomin, Fedor V. Lokshtanov, Daniel Panolan, Fahad Saurabh, Saket Univ Bergen Dept Informat Postboks 7803 N-5020 Bergen Norway Inst Math Sci Theoret Comp Sci Madras Tamil Nadu India Univ Bergen N-5020 Bergen Norway

Let M = (E, I) be a matroid and let S = {S-1,..., S-t} be a family of subsets of E of size p. A subfamily (S) over cap subset of S is q-representative for S if for every set Y subset of E of size at most q, if there is a set X is an element of S disjoint from Y with X boolean OR Y is an element of I, then there is a set (X) over cap is an element of(S) over cap disjoint from Y with (X) over cap boolean OR Y is an element of I. By the classic result of Bollobas, in a uniform matroid, every family of sets of size p has a q-representative family with at most ((p+q) (p)) sets. In his famous "two families theorem" from 1977, Lovasz proved that the same bound also holds for any matroid representable over a field F. We give an efficient construction of a q-representative family of size at most ((p+q) (p)) in time bounded by a polynomial in ((p+q) (p)), t, and the time required for field operations. We demonstrate how the efficient construction of representative families can be a powerful tool for designing single-exponential parameterized and exact exponential time algorithms. The applications of our approach include the following: -In the LONG DIRECTED CYCLE problem, the input is a directed n-vertex graph G and the positive integer k. The task is to find a directed cycle of length at least k in G, if such a cycle exists. As a consequence of our 6.75(k+o(k))n(O(1)) time algorithm, we have that a directed cycle of length at least log n, if such a cycle exists, can be found in polynomial time. -In the MINIMUM EQUIVALENT GRAPH (MEG) problem, we are seeking a spanning subdigraph D' of a given n-vertex digraph D with as few arcs as possible in which the reachability relation is the same as in the original digraph D. -We provide an alternative proof of the recent results for algorithms on graphs of bounded treewidth showing that many "connectivity" problems such as HAMILTONIAN CYCLE or STEINER TREE can be solved in time 2(O(t)) n on n-vertex graphs of treewidth at most t. For th

关键词： algorithms Design Theory Matroids representative families linear independence hash functions parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster parameterized algorithms Using Linear Programming

引用

ACM TRANSACTIONS ON algorithms 2014年第2期11卷 1–31页

作者： Lokshtanov, Daniel Narayanaswamy, N. S. Raman, Venkatesh Ramanujan, M. S. Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway Indian Inst Technol Dept Comp Sci & Engn Madras 600036 Tamil Nadu India Inst Math Sci Chennai 600113 Tamil Nadu India

We investigate the parameterized complexity of VERTEX COVER parameterized by the difference between the size of the optimal solution and the value of the linear programming (LP) relaxation of the problem. By carefully analyzing the change in the LP value in the branching steps, we argue that combining previously known preprocessing rules with the most straightforward branching algorithm yields an O*(2.618(k)) algorithm for the problem. Here, k is the excess of the vertex cover size over the LP optimum, and we write O*(f(k)) for a time complexity of the form O(f(k)n(O(1))). We proceed to show that a more sophisticated branching algorithm achieves a running time of O*(2.3146(k)). Following this, using previously known as well as new reductions, we give O*(2.3146k) algorithms for the parameterized versions of ABOVE GUARANTEE VERTEX COVER, ODD CYCLE TRANSVERSAL, SPLIT VERTEX DELETION, and ALMOST 2-SAT, and O*(1.5214(k)) algorithms for KONIG VERTEX DELETION and VERTEX COVER parameterized by the size of the smallest odd cycle transversal and Konig vertex deletion set. These algorithms significantly improve the best known bounds for these problems. The most notable improvement among these is the new bound for ODD CYCLE TRANSVERSAL-this is the first algorithm that improves on the dependence on k of the seminal O*(3(k)) algorithm of Reed, Smith, and Vetta. Finally, using our algorithm, we obtain a kernel for the standard parameterization of VERTEX COVER with at most 2k - c log k vertices. Our kernel is simpler than previously known kernels achieving the same size bound.

关键词： parameterized algorithms vertex cover

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：