### Abstract

In the Gap-clique(k; k/2 ) problem, the input is an n-vertex graph G, and the goal is to decide whether G contains a clique of size k or contains no clique of size k/2 . It is an open question in the study of fixed parameterized tractability whether the Gap-clique(k; k/2 ) problem is fixed parameter tractable, i.e., whether it has an algorithm that runs in time f(k) n, where f(k) is an arbitrary function of the parameter k and the exponent is a constant independent of k. In this paper, we give some evidence that the problem Gap-clique(k; k/2 ) is not fixed parameter tractable. Speciff-cally, we define a constraint satisfaction problem, which we call Deg-2-sat, where the input is a system of k0 quadratic equations in k0 variables over a finite field F of size n0, and the goal is to decide whether there is a solution in F that satisfies all the equations simultaneously. The main result in this paper is an "FPT-reduction" from Deg-2-sat to the Gap-clique(k; k/2 ) problem. If one were to hypothesize that the Deg-2-sat problem is not fixed parameter tractable, then our reduction would imply that the Gap-clique(k; k/2 ) problem is not fixed parameter tractable either. The reduction relies on the algebraic techniques used in proof of the PCP theorem.

Original language | English (US) |
---|---|

Title of host publication | ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science |

Publisher | Association for Computing Machinery, Inc |

Pages | 37-45 |

Number of pages | 9 |

ISBN (Electronic) | 9781450340571 |

DOIs | |

State | Published - Jan 14 2016 |

Event | 7th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2016 - Cambridge, United States Duration: Jan 14 2016 → Jan 16 2016 |

### Publication series

Name | ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science |
---|

### Other

Other | 7th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2016 |
---|---|

Country | United States |

City | Cambridge |

Period | 1/14/16 → 1/16/16 |

### Keywords

- Clique
- Fixed parameter tractability
- Hardness of approximation
- Parameterized complexity

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'On hardness of approximating the parameterized clique problem'. Together they form a unique fingerprint.

## Cite this

*ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science*(pp. 37-45). (ITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science). Association for Computing Machinery, Inc. https://doi.org/10.1145/2840728.2840733