Lokshtanov, Daniel
[VerfasserIn];
Ramanujan, M. S.
[VerfasserIn];
Saurabh, Saket
[VerfasserIn]
;
Daniel Lokshtanov and M. S. Ramanujan and Saket Saurabh
[MitwirkendeR]
A Linear-Time Parameterized Algorithm for Node Unique Label Cover
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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.