Lokshtanov, Daniel ;
Ramanujan, M. S. ;
Saurabh, Saket
A Linear-Time Parameterized Algorithm for Node Unique Label Cover
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. Chitnis et al. [FOCS 2012, SICOMP 2016] proved that this problem is fixed-parameter tractable (FPT) and Wahlström [SODA 2014] gave an FPT algorithm with an improved parameter dependence. Subsequently, Iwata, Wahlström and Yoshida [SICOMP 2016] proved that the edge version of Unique Label Cover can be solved in linear FPT-time, and they left open the existence of such an algorithm for the node version of the problem. In this paper, we resolve this question by presenting the first linear-time FPT algorithm for Node Unique Label Cover.
BibTeX - Entry
@InProceedings{lokshtanov_et_al:LIPIcs:2017:7815,
author = {Daniel Lokshtanov and M. S. Ramanujan and Saket Saurabh},
title = {{A Linear-Time Parameterized Algorithm for Node Unique Label Cover}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {57:1--57:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-049-1},
ISSN = {1868-8969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7815},
URN = {urn:nbn:de:0030-drops-78152},
doi = {10.4230/LIPIcs.ESA.2017.57},
annote = {Keywords: Algorithms and data structures, Fixed Parameter Tractability, Unique Label Cover, Linear Time FPT Algorithms.}
}
|
Keywords: |
|
Algorithms and data structures, Fixed Parameter Tractability, Unique Label Cover, Linear Time FPT Algorithms. |
|
Seminar: |
|
25th Annual European Symposium on Algorithms (ESA 2017)
|
|
Issue date: |
|
2017 |
|
Date of publication: |
|
2017 |
2017
