License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.57
URN: urn:nbn:de:0030-drops-78152
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7815/
Go to the corresponding LIPIcs Volume Portal

Lokshtanov, Daniel ; Ramanujan, M. S. ; Saurabh, Saket

A Linear-Time Parameterized Algorithm for Node Unique Label Cover

pdf-format:
LIPIcs-ESA-2017-57.pdf (0.5 MB)

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.
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI