A Linear-Time Parameterized Algorithm for Node Unique Label Cover
From MaRDI portal
Publication:5111746
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)
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.
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
Cites work
- scientific article; zbMATH DE number 5485473 (Why is no real title available?)
- scientific article; zbMATH DE number 5485559 (Why is no real title available?)
- scientific article; zbMATH DE number 5764892 (Why is no real title available?)
- scientific article; zbMATH DE number 6297714 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
- A \(c^k n\) 5-approximation algorithm for treewidth
- A faster parameterized algorithm for Group Feedback Edge Set
- A linear time algorithm for finding tree-decompositions of small treewidth
- A near-optimal planarization algorithm
- An improved parameterized algorithm for the minimum node multiway cut problem
- Computing crossing numbers in quadratic time
- Computing crossing numbers in quadratic time
- Designing FPT algorithms for cut problems using randomized contractions
- FPT algorithms for path-transversal and cycle-transversal problems
- Faster parameterized algorithms using linear programming
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XVIII: Tree-decompositions and well-quasi-ordering
- Graph minors. XX: Wagner's conjecture
- Half-integrality, LP-branching and FPT algorithms
- Half-integrality, LP-branching, and FPT algorithms
- Linear time parameterized algorithms for subset feedback vertex set
- Linear time parameterized algorithms via skew-symmetric multicuts
- Linear-time FPT algorithms via network flow
- Nonconstructive tools for proving polynomial-time decidability
- On the power of unique 2-prover 1-round games
- Parameterized graph separation problems
- Planar subgraph isomorphism revisited
- Planarity Allowing Few Error Vertices in Linear Time
- Solving d-SAT via Backdoors to Small Treewidth
- The disjoint paths problem in quadratic time
- Which problems have strongly exponential complexity?
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)
