A Linear-Time Parameterized Algorithm for Node Unique Label Cover
From MaRDI portal
Publication:5111746
DOI10.4230/LIPICS.ESA.2017.57zbMATH Open1442.68288arXiv1604.08764OpenAlexW2963262002MaRDI QIDQ5111746FDOQ5111746
Saket Saurabh, Daniel Lokshtanov, M. S. Ramanujan
Publication date: 27 May 2020
Abstract: The optimization version of the Unique Label Cover problem is at the heart of the Unique Games Conjecture which has played an important role in the proof of several tight inapproximability results. In recent years, this problem has been also studied extensively from the point of view of parameterized complexity. Cygan et al. [FOCS 2012] proved that this problem is fixed-parameter tractable (FPT) and Wahlstr"om [SODA 2014] gave an FPT algorithm with an improved parameter dependence. Subsequently, Iwata, Wahlstr"om and Yoshida [2014] proved that the edge version of Unique Label Cover can be solved in linear FPT-time. That is, there is an FPT algorithm whose dependence on the input-size is linear. However, such an algorithm for the node version of the problem was left as an open problem. In this paper, we resolve this question by presenting the first linear-time FPT algorithm for Node Unique Label Cover.
Full work available at URL: https://arxiv.org/abs/1604.08764
Recommendations
- The parameterized complexity of unique coverage and its variants
- The Parameterized Complexity of the Unique Coverage Problem
- Improved Approximation Algorithms for Label Cover Problems
- Improved approximation algorithms for label cover problems
- Parameterized algorithms for linear layouts of graphs with respect to the vertex cover number
- Nearly optimal NP-hardness of unique coverage
- Nearly optimal NP-hardness of unique coverage
- Approximation algorithms for label cover and the log-density threshold
- scientific article; zbMATH DE number 2043351
- A novel labeling algorithm on several classes of graphs
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Graph minors. XX: Wagner's conjecture
- Which problems have strongly exponential complexity?
- Graph minors. XIII: The disjoint paths problem
- Half-integrality, LP-branching, and FPT algorithms
- On Multiway Cut Parameterized above Lower Bounds
- A Faster Parameterized Algorithm for Group Feedback Edge Set
- Nonconstructive tools for proving polynomial-time decidability
- FPT algorithms for path-transversal and cycle-transversal problems
- Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts
- Linear-Time FPT Algorithms via Network Flow
- Half-integrality, LP-branching and FPT Algorithms
- Parameterized graph separation problems
- The disjoint paths problem in quadratic time
- A linear time algorithm for finding tree-decompositions of small treewidth
- On the power of unique 2-prover 1-round games
- Computing crossing numbers in quadratic time
- An improved parameterized algorithm for the minimum node multiway cut problem
- Faster Parameterized Algorithms Using Linear Programming
- Planar Subgraph Isomorphism Revisited
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Computing crossing numbers in quadratic time
- A \(c^k n\) 5-approximation algorithm for treewidth
- Designing FPT Algorithms for Cut Problems Using Randomized Contractions
- Title not available (Why is that?)
- Graph minors. XVIII: Tree-decompositions and well-quasi-ordering
- Linear Time Parameterized Algorithms for Subset Feedback Vertex Set
- Solving d-SAT via Backdoors to Small Treewidth
- A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
- A Near-Optimal Planarization Algorithm
- Planarity Allowing Few Error Vertices in Linear Time
This page was built for publication: A Linear-Time Parameterized Algorithm for Node Unique Label Cover
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111746)
