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

Faster parameterized algorithms Using Linear Programming

ACM TRANSACTIONS ON algorithms 2014年第2期11卷 15-15页

作者： 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

来源：评论

学校读者我要写书评

暂无评论

Beyond bidimensionality: parameterized subexponential algorithms on directed graphs

引用

INFORMATION AND COMPUTATION 2013年 233卷 60-70页

作者： Dorn, Frederic Fomin, Fedor V. Lokshtanov, Daniel Raman, Venkatesh Saurabh, Saket SINTEF Energy Res Trondheim Norway Univ Bergen Dept Informat N-5020 Bergen Norway Inst Math Sci Chennai 600113 Tamil Nadu India

In this paper we make the first step beyond bidimensionality by obtaining subexponential time algorithms for problems on directed graphs. We develop two different methods to achieve subexponential time parameterized algorithms for problems on sparse directed graphs. We exemplify our approaches with two well studied problems. For the first problem, k-LEAF OUT-BRANCHING, which is to find an oriented spanning tree with at least k leaves, we obtain an algorithm solving the problem in time 2(O(root k log k))n + n(O(1)) on directed graphs whose underlying undirected graph excludes some fixed graph H as a minor. For the special case when the input directed graph is planar, the running time can be improved to 2(O(root k))n + n(O(1)). The second example is a generalization of the DIRECTED HAMILTONIAN PATH problem, namely k-INTERNAL OUT-BRANCHING, which is to find all oriented spanning tree with at least k internal vertices. We obtain an algorithm solving the problem in time 2(O(root k log k)) + n(O(1)) on directed graphs whose underlying undirected graph excludes some fixed apex graph H as a minor. Finally, we observe that on these classes of graphs, the k-DIRECTED PATH problem is solvable in time O((1 + epsilon)(k)n(f(epsilon))), for any epsilon > 0, where f is some function of epsilon. Our methods are based on non-trivial combinations of obstruction theorems for undirected graphs, kernelization, problem-specific combinatorial structures, and a layering technique similar to the one employed by Baker to obtain PTAS for planar graphs. (C) 2013 Elsevier Inc. All rights reserved.

关键词： parameterized algorithms Subexponential running time Directed graph Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

k-apices of Minor-closed Graph Classes. II. parameterized algorithms

引用

ACM TRANSACTIONS ON algorithms 2022年第3期18卷 21-21页

作者： Sau, Ignasi Stamoulis, Giannos Thilikos, Dimitrios M. Univ Montpellier LIRMM CNRS Montpellier France

Let G be a minor-closed graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G\S belongs to G. We denote by A(k)(G) the set of all graphs that are k-apices of G. In the first paper of this series, we obtained upper bounds on the size of the graphs in the minor-obstruction set of A(k) (G), i.e., the minor-minimal set of graphs not belonging to A(k)(G). In this article, we provide an algorithm that, given a graph G on n vertices, runs in time 2(poly(k)) . n(3) and either returns a set S certifying that G is an element of A(k) (G), or reports that G is not an element of A(k) (G). Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G. In the special case where G excludes some apex graph as a minor, we give an alternative algorithm running in 2(poly(k)) . n(2)-time.

关键词： Graph minors parameterized algorithms graph modification problems irrelevant vertex technique flat wall theorem

来源：评论

学校读者我要写书评

暂无评论

parameterized Approximation algorithms and Lower Bounds for k-Center Clustering and Variants

引用

ALGORITHMICA 2024年第8期86卷 2557-2574页

作者： Bandyapadhyay, Sayan Friggstad, Zachary Mousavi, Ramin Portland State Univ Dept Comp Sci Portland OR USA Univ Alberta Dept Comp Sci Edmonton AB Canada

k-center is one of the most popular clustering models. While it admits a simple 2-approximation in polynomial time in general metrics, the Euclidean version is NP-hard to approximate within a factor of 1.82, even in the plane, if one insists the dependence on k in the running time be polynomial. Without this restriction, a classic algorithm by Agarwal and Procopiuc [Algorithmica 2002] yields an O(n log k)+(1/epsilon)(O(2d) (k1-1/d) log k-time (1+epsilon)-approximation for Euclidean k-center, where d is the dimension. We show for a closely related problem, k-supplier, the double-exponential dependence on dimension is unavoidable if one hopes to have a sub-linear dependence on k in the exponent. We also derive similar algorithmic results to the ones by Agarwal and Procopiuc for both k-center and k-supplier. We use a relatively new tool, called Voronoi separator, which makes our algorithms and analyses substantially simpler. Furthermore we consider a well-studied generalization of k-center, called Non-uniform k-center (NUkC), where we allow different radii clusters. NUkC is NP-hard to approximate within any factor, even in the Euclidean case. We design a 2(O(k) (log) (k))n(2) time 3-approximation for NUkC in general metrics, and a 2(O((k) (log) (k)/epsilon))dn time (1+epsilon)-approximation for Euclidean NUkC. The latter time bound matches the bound for k-center.

关键词： parameterized algorithms Hardness Euclidean k-center Non-uniform k-center

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Covering Small Independent Sets and Separators with Applications to parameterized algorithms

引用

ACM TRANSACTIONS ON algorithms 2020年第3期16卷 32-32页

作者： 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

来源：评论

学校读者我要写书评

暂无评论

Paths of bounded length and their cuts: parameterized complexity and algorithms

引用

DISCRETE OPTIMIZATION 2011年第1期8卷 72-86页

作者： Golovach, Petr A. Thilikos, Dimitrios M. Univ Athens Dept Math GR-15784 Athens Greece Univ Durham Sch Engn & Comp Sci Durham DH1 3LE England

We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem and the bounded length cut problem. From Menger's theorem both problems are equivalent (and computationally easy) in the unbounded case for single source, single target paths. However, in the bounded case, they are combinatorially distinct and are both NP-hard, even to approximate. Our results indicate that a more refined landscape appears when we study these problems with respect to their parameterized complexity. For this, we consider several parameterizations (with respect to the maximum length I of paths, the number k of paths or the size of a cut, and the treewidth of the input graph) of all variants of both problems (edge/vertex-disjoint paths or cuts, directed/undirected). We provide FPT-algorithms (for all variants) when parameterized by both k and I and hardness results when the parameter is only one of k and I. Our results indicate that the bounded length disjoint-path variants are structurally harder than their bounded length cut counterparts. Also, it appears that the edge variants are harder than their vertex-disjoint counterparts when parameterized by the treewidth of the input graph. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Bounded length disjoint paths Bounded length cuts parameterized complexity parameterized 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

来源：评论

学校读者我要写书评

暂无评论

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

引用

JOURNAL OF THE ACM 2016年第4期63卷 29-29页

作者： 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

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：