Bhattacharyya, Arnab ;
Ghoshal, Suprovat ;
C. S., Karthik ;
Manurangsi, Pasin
Parameterized Intractability of Even Set and Shortest Vector Problem from GapETH
Abstract
The kEven Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over F_2, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k. Here, k is the parameter of the problem. The question of whether kEven Set is fixed parameter tractable (FPT) has been repeatedly raised in literature and has earned its place in Downey and Fellows' book (2013) as one of the "most infamous" open problems in the field of Parameterized Complexity.
In this work, we show that kEven Set does not admit FPT algorithms under the (randomized) Gap Exponential Time Hypothesis (GapETH) [Dinur'16, ManurangsiRaghavendra'16]. In fact, our result rules out not only exact FPT algorithms, but also any constant factor FPT approximation algorithms for the problem. Furthermore, our result holds even under the following weaker assumption, which is also known as the Parameterized Inapproximability Hypothesis (PIH) [Lokshtanov et al.'17]: no (randomized) FPT algorithm can distinguish a satisfiable 2CSP instance from one which is only 0.99satisfiable (where the parameter is the number of variables).
We also consider the parameterized kShortest Vector Problem (SVP), in which we are given a lattice whose basis vectors are integral and an integer k, and the goal is to determine whether the norm of the shortest vector (in the l_p norm for some fixed p) is at most k. Similar to kEven Set, this problem is also a longstanding open problem in the field of Parameterized Complexity. We show that, for any p > 1, kSVP is hard to approximate (in FPT time) to some constant factor, assuming PIH. Furthermore, for the case of p = 2, the inapproximability factor can be amplified to any constant.
BibTeX  Entry
@InProceedings{bhattacharyya_et_al:LIPIcs:2018:9021,
author = {Arnab Bhattacharyya and Suprovat Ghoshal and Karthik C. S. and Pasin Manurangsi},
title = {{Parameterized Intractability of Even Set and Shortest Vector Problem from GapETH}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {17:117:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9021},
URN = {urn:nbn:de:0030drops90214},
doi = {10.4230/LIPIcs.ICALP.2018.17},
annote = {Keywords: Parameterized Complexity, Inapproximability, Even Set, Minimum Distance Problem, Shortest Vector Problem, GapETH}
}
04.07.2018
Keywords: 

Parameterized Complexity, Inapproximability, Even Set, Minimum Distance Problem, Shortest Vector Problem, GapETH 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

04.07.2018 