## View/hide extracted text (may have errors)

Known algorithms for Edge Clique Cover are probably optimal* Marek Cygan † Marcin Pilipczuk‡ Micha l Pilipczuk § Abstract (e.g., intended solution size or structural graph param- In the Edge Clique Cover (ECC) problem, given a eters), the parameterized complexity paradigm allows graph G and an integer k, we ask whether the edges of much deeper insight into the hardness of NP-hard prob- G can be covered with k complete subgraphs of G or, lems than the classical instance-size measure. equivalently, whether G admits an intersection model on k- Although the definition of a fixed-parameter algo- element universe. Gramm et al. [JEA 2008] have shown rithm allows an arbitrarily fast growing function f, if f a set of simple rules that reduce the number of vertices turns out to be relatively small (say, single-exponential), of G to 2k, and no algorithm is known with significantly a fixed-parameter algorithm becomes practical for a rea- better running time bound than a brute-force search on sonable range of values of the parameter. Therefore, this reduced instance. In this paper we show that the since the dawn of parameterized complexity, researchers approach of Gramm et al. is essentially optimal: we present try to bound, as much as possible, the explosion of the a polynomial time algorithm that reduces an arbitrary 3- CNF-SAT formula with n variables and m clauses to an running time hidden in the function f. In particular the equivalent ECC instance (G,k) with k = O(log n) and goal of the part of parameterized complexity called by |V (G)| = O(n + m). Consequently, there is no 22o(k) poly(n) Marx [36] the optimality program, is to quantitatively time algorithm for the ECC problem, unless the Exponential understand what is the best possible f function in the Time Hypothesis fails. To the best of our knowledge, these running time. are the first results for a natural, fixed-parameter tractable In the last few years, this trend has been comple- problem, and proving that a doubly-exponential dependency mented by a research of lower bounds, usually condi- on the parameter is essentially necessary. tional on the Exponential Time Hypothesis by Impagli- azzo et al. [27]. Let ck be the infimum over all posi- 1 Introduction tive reals c such that there exists an algorithm resolv- Recently, there has been an increasing interest in not ing satisfiability of n-variable k-CNF-SAT formulae in only improving the running times of exact algorithms for O(2cn) time. The Exponential Time Hypothesis (ETH) various NP-hard problems, but also in finding the lim- asserts that c3 > 0 (that is, 3-CNF-SAT formulae can- its of such improvements. Parameterized complexity is a not be resolved in subexponential time in the number very useful framework for such study: in this approach, of variables), whereas its stronger variant, Strong Ex- an instance x of a parameterized problem comes with ponential Time Hypothesis (SETH) [6, 26], asserts that an integer parameter k. We say that a problem is fixed limk→∞ ck = 1 (in particular, an exhaustive search is parameter tractable (FPT) if there exists an algorithm the best possible solution for an arbitrary CNF for- solving any instance (x,k) in time f(k)|x|O(1) for some mula). computable function f. In other words, the exponential Since the seminal paper of Impagliazzo et al. [27], explosion of the running time, probably unavoidable for many ETH-based lower bounds were developed (e.g., NP-hard problems, is encapsulated in a function of a [16, 35, 34]), with the prominent example of tight parameter. With a wide range of possible parameters bounds for W[1]-hard problems [9, 10]. The most stan- dard usage of ETH is to refute an existence of a subex- ponential algorithm for some problem by showing a lin- *The first author is partially supported by the ERC Starting ear (in the number of variables and clauses) reduction Grant NEWNET 279352. Moreover the first two authors are from an arbitrary 3-CNF-SAT formula and using to the partially supported by NCN grant N206567140 and Foundation so-called Sparsification Lemma [27]. In order to prove for Polish Science. The third author is partially supported by the European Research Council (ERC) grant “Rigorous Theory lower bounds for different complexities (different func- of Preprocessing”, reference 267959. tions f, say f(k) = 2O(k log k)), the allowed dependency †IDSIA, University of Lugano, Switzerland, marek@idsia.ch of k on n and m is more involved. Moreover, note that ‡Institute of Informatics, University of Warsaw, Poland, an ETH-based lower bound may exclude a subexponen- malcin@mimuw.edu.pl tial algorithm, but says nothing about the possible base §Department of Informatics, University of Bergen, Norway, michal.pilipczuk@ii.uib.no of the exponent in an O(ck|x|O(1)) fixed-parameter al- 1044 Copyright © SIAM. Unauthorized reproduction of this article is prohibited.