Search

The study of the complexity of the equation satisfiability problem in finite groups had been initiated by Goldmann and Russell in (Inf. Comput. 178(1), 253–262, 2002) where they showed that this problem is in P for nilpotent groups while it is NP-complete for non-solvable groups. Since then, several results have appeared showing that the problem can be solved in polynomial time in certain solvable groups G having a nilpotent normal subgroup H with nilpotent factor G/H. This paper shows that such a normal subgroup must exist in each finite group with equation satisfiability solvable in polynomial time, unless the Exponential Time Hypothesis fails. [ABSTRACT FROM AUTHOR]

We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cut graph of a graph G embedded on a surface S is a subgraph of G whose removal from S leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus has a cut graph of length at most a given value. We prove a time lower bound for this problem of nO(/log) conditionally to the ETH. In other words, the first nO(1)-time algorithm by Erickson and Har-Peled [SoCG 2002, Discr. Comput. Geom. 2004] is essentially optimal. We also prove that the problem is W[1]-hard when parameterized by the genus, answering a 17-year-old question of these authors. A multiway cut of an undirected graph G with t distinguished vertices, called terminals, is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph G has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of nO(v t+2+t / log(+t)), conditionally to the ETH, for any choice of the genus = 0 of the graph and the number of terminals t = 4. In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case). Reductions to planar problems usually involve a gridlike structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value of the genus. [ABSTRACT FROM AUTHOR]

Given a graph G and a set T = {(si, ti): 1 = i = k} of k pairs, the VERTEX-DISJOINT PATHS (resp. EDGE-DISJOINT PATHS) problems asks to determine whether there exist pairwise vertex-disjoint (resp. edge-disjoint) paths P1,P2,...,Pk in G such that Pi connects si to ti for each 1 = i = k. Unlike their undirected counterparts which are FPT (parameterized by k) from Graph Minor theory, both the edge-disjoint and vertex-disjoint versions in directed graphs were shown by Fortune et al. (TCS '80) to be NP-hard for k = 2. This strong hardness for DISJOINT PATHS on general directed graphs led to the study of parameterized complexity on special graph classes, e.g., when the underlying undirected graph is planar. For VERTEX-DISJOINT PATHS on planar directed graphs, Schrijver (SICOMP '94) designed an nO(k) time algorithm which was later improved upon by Cygan et al. (FOCS '13) who designed an FPT algorithm running in 22O(k2) ·nO(1) time. To the best of our knowledge, the parameterized complexity of EDGE-DISJOINT PATHS on planar1 directed graphs is unknown. We resolve this gap by showing that EDGE-DISJOINT PATHS is W[1]-hard parameterized by the number k of terminal pairs, even when the input graph is a planar directed acyclic graph (DAG). This answers a question of Slivkins (ESA '03, SIDMA '10). Moreover, under the Exponential Time Hypothesis (ETH), we show that there is no f(k)· no(k) algorithm for EDGE-DISJOINT PATHS on planar DAGs, where k is the number of terminal pairs, n is the number of vertices and f is any computable function. Our hardness holds even if both the maximum in-degree and maximum out-degree of the graph are at most 2. [ABSTRACT FROM AUTHOR]

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min { c T x ∣ A x = b , ℓ ≤ x ≤ u , x ∈ Z r + n s } where the constraint matrix A ∈ Z n t × r + n s consists of n matrices A i ∈ Z t × r on the vertical line and n matrices B i ∈ Z t × s on the diagonal line aside. We show a stronger hardness result for a number theoretic problem called Quadratic Congruences where the objective is to compute a number z ≤ γ satisfying z 2 ≡ α mod β for given α , β , γ ∈ Z . This problem was proven to be NP-hard already in 1978 by Manders and Adleman. However, this hardness only applies for instances where the prime factorization of β admits large multiplicities of each prime number. We circumvent this necessity proving that the problem remains NP-hard, even if each prime number only occurs constantly often. Using this new hardness result for the Q U A D R A T I C C O N G R U E N C E S problem, we prove a lower bound of 2 2 δ (s + t) | I | O (1) for some δ > 0 for the running time of any algorithm solving 2-stage stochastic ILPs assuming the Exponential Time Hypothesis (ETH). Here, |I| is the encoding length of the instance. This result even holds if r, | | b | | ∞ , | | c | | ∞ , | | ℓ | | ∞ and the largest absolute value Δ in the constraint matrix A are constant. This shows that the state-of-the-art algorithms are nearly tight. Further, it proves the suspicion that these ILPs are indeed harder to solve than the closely related n -fold ILPs where the constraint matrix is the transpose of A . [ABSTRACT FROM AUTHOR]

Given a graph G and an integer k, the k-Biclique problem asks whether G contains a complete bipartite subgraph with k vertices on each side. Whether there is an f(k) ċ |G|O(1)-time algorithm, solving k-Biclique for some computable function f has been a longstanding open problem. We show that k-Biclique is W[1]-hard, which implies that such an f(k) ċ |G|O(1)-time algorithm does not exist under the hypothesis W[1] ≠ FPT from parameterized complexity theory. To prove this result, we give a reduction which, for every n-vertex graph G and small integer k, constructs a bipartite graph H = (L⊍ R,E) in time polynomial in n such that if G contains a clique with k vertices, then there are k(k − 1)/2 vertices in L with nθ(1/k) common neighbors; otherwise, any k(k − 1)/2 vertices in L have at most (k+1)! common neighbors. An additional feature of this reduction is that it creates a gap on the right side of the biclique. Such a gap might have further applications in proving hardness of approximation results. Assuming a randomized version of Exponential Time Hypothesis, we establish an f(k) ċ |G|o(&sqrt;k)-time lower bound for k-Biclique for any computable function f. Combining our result with the work of Bulatov and Marx [2014], we obtain a dichotomy classification of the parameterized complexity of cardinality constraint satisfaction problems. [ABSTRACT FROM AUTHOR]

Conflict-free q -colouring of a graph G refers to the colouring of a subset of vertices of G using q colours such that every vertex has a neighbour of unique colour. In this paper, we study the Minimum Conflict-free q-Colouring problem. Given a graph G and a fixed constant q , Minimum Conflict-free q-Colouring is to find a conflict-free q -colouring of G that minimizes the number of coloured vertices. We study the parameterized complexity of the Minimum Conflict-free q-Colouring problem when parameterized by structural parameters like treewidth and vertex cover of G. We give an FPT algorithm for Minimum Conflict-free q-Colouring parameterized by treewidth and also prove running time lower bounds under Exponential Time Hypothesis (ETH) and Strong Exponential Time Hypothesis (SETH). Using standard kernelization lower bound techniques, it is easy to see that Minimum Conflict-free q-Colouring parameterized by treewidth does not admit polynomial kernels. We extend this result for a larger parameter namely the vertex cover of G , when q > 1. [ABSTRACT FROM AUTHOR]

We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph G to graph H cannot be done in time ∣V(H)∣o(∣V(H)∣). We also show an exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of ∣V(H)∣o(∣V(H)∣)-time algorithm deciding if graph G is a subgraph of H. For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems. Moreover, as a consequence of our reductions, conditional lower bounds follow for other related problems such as Locally Injective Homomorphism, Graph Minors, Topological Graph Minors, Minimum Distortion Embedding and Quadratic Assignment Problem. [ABSTRACT FROM AUTHOR]

We show that tree-like resolution is not automatable in time n o (log n) unless ETH is false. This implies that, under ETH, the algorithm given by Beame and Pitassi (FOCS 1996) that automates tree-like resolution in time n o (log n) is optimal. We also provide a simpler proof of the result of Alekhnovich and Razborov (FOCS 2001) that unless the fixed parameter hierarchy collapses, tree-like resolution is not automatable in polynomial time. The proof of our results builds on a joint work with Göös, Nordström, Pitassi, Robere and Sokolov (STOC 2021), which presents a simplification of the recent breakthrough of Atserias and Müller (FOCS 2019). [ABSTRACT FROM AUTHOR]

Given an undirected graph G = (V , E) the NP-hard Strong Triadic Closure (STC) problem asks for a labeling of the edges as weak and strong such that at most k edges are weak and for each induced P 3 in G at least one edge is weak. We study the following generalizations of STC with c different strong edge colors. In Multi-STC an induced P 3 may receive two strong labels as long as they are different. In Edge-List Multi-STC and Vertex-List Multi-STC we may restrict the set of permitted colors for each edge of G. We show that, under the Exponential Time Hypothesis (ETH), Edge-List Multi-STC and Vertex-List Multi-STC cannot be solved in time 2 o (| V | 2). We proceed with a parameterized complexity analysis in which we extend previous algorithms and kernelizations for STC [11,14] to the three variants or outline the limits of such an extension. [ABSTRACT FROM AUTHOR]

We study the complexity of the problems of finding, given a graph G, a largest induced subgraph of G with all degrees odd (called an odd subgraph), and the smallest number of odd subgraphs that partition V(G). We call these parameters mos (G) and χ odd (G) , respectively. We prove that deciding whether χ odd (G) ≤ q is polynomial-time solvable if q ≤ 2 , and NP-complete otherwise. We provide algorithms in time 2 O (rw) · n O (1) and 2 O (q · rw) · n O (1) to compute mos (G) and to decide whether χ odd (G) ≤ q on n-vertex graphs of rank-width at most rw , respectively, and we prove that the dependency on rank-width is asymptotically optimal under the ETH. Finally, we give some tight bounds for these parameters on restricted graph classes or in relation to other parameters. [ABSTRACT FROM AUTHOR]

We introduce and study a new model of interactive proofs: AM(κ), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close analogies between it and the quantum complexity class QMA(kappa;), but the AM(kappa;) model is also natural in its own right. We illustrate the power of multiple Merlins by giving an AM(2) protocol for 3SAT, in which the Merlins' challenges and responses consist of only n 1/2+o(1) bits each. Our protocol has the consequence that, assuming the Exponential Time Hypothesis (ETH), any algorithm for approximating a dense CSP with a polynomial-size alphabet must take n(log n)1-o(1) time. Algorithms nearly matching this lower bound are known, but their running times had never been previously explained. Brandao and Harrow have also recently used our 3SAT protocol to show quasipolynomial hardness for approximating the values of certain entangled games. In the other direction, we give a simple quasipolynomial-time approximation algorithm for free games, and use it to prove that, assuming the ETH, our 3SAT protocol is essentially optimal. More generally, we show that multiple Merlins never provide more than a polynomial advantage over one: that is, AM(kappa;) = AM for all kappa;=poly(n). The key to this result is a sub sampling theorem for free games, which follows from powerful results by Alon et al. And Barak et al. On sub sampling dense CSPs, and which says that the value of any free game can be closely approximated by the value of a logarithmic-sized random sub game. © 2014 IEEE.

We show that the problem of deciding whether a collection of polyominoes, each fitting in a 2 × O (log ⁡ n) rectangle, can be packed into a 3 × n box does not admit a 2 o (n / log ⁡ n) -time algorithm, unless the Exponential Time Hypothesis fails. We also give an algorithm that attains this lower bound, solving any instance of polyomino packing with total area n in 2 O (n / log ⁡ n) time. This establishes a tight bound on the complexity of Polyomino Packing , even in a very restricted case. In contrast, for a 2 × n box, we show that the problem can be solved in strongly subexponential time. [ABSTRACT FROM AUTHOR]

In this paper, we study the Maximum Happy Vertices and the Maximum Happy Edges problems (MHV and MHE for short). Very recently, the problems attracted a lot of attention and were studied in Agrawal '18, Aravind et al. '16, Choudhari and Reddy '18, Misra and Reddy '18. Main focus of our work is lower bounds on the computational complexity of these problems. Established lower bounds can be divided into the following groups: NP-hardness of the above guarantee parameterization, kernelization lower bounds (answering questions of Misra and Reddy '18), exponential lower bounds under the Set Cover Conjecture and the Exponential Time Hypothesis , and inapproximability results. Moreover, we present an O ⁎ (ℓ k) randomized algorithm for MHV and an O ⁎ (2 k) algorithm for MHE, where ℓ is the number of colors used and k is the number of required happy vertices or edges. These algorithms cannot be improved to subexponential taking proved lower bounds into account. [ABSTRACT FROM AUTHOR]

Consensus problems for strings and sequences appear in numerous application contexts, ranging from bioinformatics to data mining to machine learning. Closing some gaps in the literature, we show that several fundamental problems in this context are NP- and W[1]-hard and that the known (including some brute-force) algorithms are close to optimality assuming the Exponential Time Hypothesis. Among our main contributions is to settle the complexity status of computing a mean in dynamic time warping spaces which, as pointed out by Brill et al. [Data Min. Knowl. Discov., 33 (2019), pp. 252--291], suffered from many unproven or false assumptions in the literature. We prove this problem to be NP-hard and additionally show that a recent dynamic programming algorithm is essentially optimal. In this context, we study a broad family of circular string alignment problems. This family also serves as a key for our hardness reductions, and it is of independent (practical) interest in molecular biology. In particular, we show tight hardness and running time lower bounds for Circular Consensus String; notably, the corresponding noncircular version is easily linear-time solvable. [ABSTRACT FROM AUTHOR]

For a finite collection of graphs F, the F-M-DELETION problem consists in, given a graph G and an integer k, deciding whether there exists S ⊆ V (G) with |S| ≤ k such that G\S does not contain any of the graphs in F as a minor. We are interested in the parameterized complexity of F-M-Deletion when the parameter is the treewidth of G, denoted by tw. Our objective is to determine, for a fixed F, the smallest function fF such that F-M-DELETION can be solved in time fF(tw) . nO(1) on n-vertex graphs. We prove that fF(tw) = 2²O(tw.logtw) for every collection F, that fF(tw) = 2O(tw.log tw) if F contains a planar graph, and that fF(tw) = 2O(tw) if in addition the input graph G is planar or embedded in a surface. We also consider the version of the problem where the graphs in F are forbidden as topological minors, called F-TM-Deletion. We prove similar results for this problem, except that in the last two algorithms, instead of requiring F to contain a planar graph, we need it to contain a subcubic planar graph. This is the first of a series of articles on this topic. [ABSTRACT FROM AUTHOR]

For a finite fixed collection of graphs F , the F -M-Deletion problem consists in, given a graph G and an integer k , decide whether there exists S ⊆ V (G) with | S | ≤ k such that G ∖ S does not contain any of the graphs in F as a minor. We provide lower bounds under the ETH on the smallest function f F such that F -M-Deletion can be solved in time f F (tw) ⋅ n O (1) on n -vertex graphs, where tw denotes the treewidth of G. We first prove that for any F containing connected graphs of size at least two, f F (tw) = 2 Ω (tw) , even if G is planar. Our main result is that if F contains a single connected graph H that is either P 5 or is not a minor of the b a n n e r , then f F (tw) = 2 Ω (tw ⋅ log ⁡ tw). [ABSTRACT FROM AUTHOR]

The Steiner Tree problem is one of the most fundamental NP-complete problems, as it models many network design problems. Recall that an instance of this problem consists of a graph with edge weights and a subset of vertices (often called terminals); the goal is to find a subtree of the graph of minimum total weight that connects all terminals. A seminal paper by Erickson et al. [Math. Oper. Res., 1987] considers instances where the underlying graph is planar and all terminals can be covered by the boundary of k faces. Erickson et al. show that the problem can be solved by an algorithm using nO(k) time and nO(k) space, where n denotes the number of vertices of the input graph. In the past 30 years there has been no significant improvement of this algorithm, despite several efforts. In this work, we give an algorithm for Planar Steiner Tree with running time 2O(k)nO(v k) with the above parameterization, using only polynomial space. Furthermore, we show that the running time of our algorithm is almost tight: We prove that there is no f (k)no(v k) algorithm for Planar Steiner Tree for any computable function f, unless the Exponential Time Hypothesis fails. [ABSTRACT FROM AUTHOR]

For a finite collection of graphs F , the F -M-Deletion (resp. F -TM-Deletion) problem consists in, given a graph G and an integer k , decide whether there exists S ⊆ V (G) with | S | ≤ k such that G ∖ S does not contain any of the graphs in F as a minor (resp. topological minor). We are interested in the parameterized complexity of both problems when the parameter is the treewidth of G , denoted by tw , and specifically in the cases where F contains a single connected planar graph H. We present algorithms running in time 2 O (tw) ⋅ n O (1) , called single-exponential , when H is either P 3 , P 4 , C 4 , the paw , the chair , and the banner for both { H } -M-Deletion and { H } -TM-Deletion , and when H = K 1 , i , with i ≥ 1 , for { H } -TM-Deletion. Some of these algorithms use the rank-based approach introduced by Bodlaender et al. (2015) [7]. This is the second of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of { H } -M-Deletion in terms of H. [ABSTRACT FROM AUTHOR]

Given a vertex-weighted directed graph G = (V,E) and a set T = { t1, t2, . . ., tk} of k terminals, the objective of the Strongly Connected Steiner Subgraph (SCSS) problem is to find a vertex set H ⊆ V of minimum weight such that G[H] contains a ti → tj path for each i ≠ j. The problem is NP-hard, but Feldman and Ruhl [SIAM J. Comput., 36 (2006), pp. 543--561] gave a novel nO(k) algorithm for the SCSS problem, where n is the number of vertices in the graph and k is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a 2O(k)·nO(√k) algorithm for planar SCSS, which is an improvement of a factor of O(√k) in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an f(k)·no(√k) algorithm for any computable function f, unless the exponential time hypothesis (ETH) fails. To obtain our algorithm, we first show combinatorially that there is a minimal solution whose treewidth is O(√k), and then use the dynamic-programming based algorithm for finding bounded-treewidth solutions due to Feldmann and Marx [The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems, preprint, https://arxiv.org/abs/1707.06808]. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a gridlike fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: our 2O(k)·nO(√k) algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. Additionally, we can obtain this running time for the problem of finding an optimal planar solution even if the input graph is not planar. In general graphs, we cannot hope for such a dramatic improvement over the nO(k) algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an f(k)·no(k/ log k) algorithm for any computable function f. Feldman and Ruhl generalized their nO(k) algorithm to the more general Directed Steiner Network (DSN) problem; here the task is to find a subgraph of minimum weight such that for every source si there is a path to the corresponding terminal ti. We show that, assuming ETH, there is no f(k)·no(k) time algorithm for DSN on acyclic planar graphs. All our lower bounds hold for the integer weighted edge version, while the algorithm works for the more general unweighted vertex version. [ABSTRACT FROM AUTHOR]

Kernelization – a mathematical key concept for provably effective polynomial-time preprocessing of NP-hard problems – plays a central role in parameterized complexity and has triggered an extensive line of research. This is in part due to a lower bounds framework that allows to exclude polynomial-size kernels under the assumption of NP ⊈ coNP / poly. In this paper we consider a restricted yet natural variant of kernelization, namely strict kernelization, where one is not allowed to increase the parameter of the reduced instance (the kernel) by more than an additive constant. Building on earlier work of Chen, Flum, and Müller [CiE 2009, Theory Comput. Syst. 2011], we underline the applicability of their framework by showing that a variety of fixed-parameter tractable problems, including graph problems and Turing machine computation problems, does not admit strict polynomial kernels under the assumption of P ≠ NP , an assumption being weaker than the assumption of NP ⊈ coNP / poly. Finally, we study an adaption of the framework to a relaxation of the notion of strict kernels, where in the latter one is not allowed to increase the parameter of the reduced instance by more than a constant times the input parameter. [ABSTRACT FROM AUTHOR]

We investigate the relationship between several enumeration complexity classes and focus in particular on problems having enumeration algorithms with incremental and polynomial delay (IncP and DelayP respectively). We show that, for some algorithms, we can turn an average delay into a worst case delay without increasing the space complexity, suggesting that IncP 1 = DelayP even with polynomially bounded space. We use the Exponential Time Hypothesis to exhibit a strict hierarchy inside IncP which gives the first separation of DelayP and IncP. Finally we relate the uniform generation of solutions to probabilistic enumeration algorithms with polynomial delay and polynomial space. [ABSTRACT FROM AUTHOR]

Let G be an undirected simple graph having n vertices and let f : V (G) → { 0 , ⋯ , n - 1 } be a function. An f-factor of G is a spanning subgraph H such that d H (v) = f (v) for every vertex v ∈ V (G) . The subgraph H is called a connected f-factor if, in addition, H is connected. A classical result of Tutte (Can J Math 6(1954):347–352, 1954) is the polynomial time algorithm to check whether a given graph has a specified f-factor. However, checking for the presence of a connectedf-factor is easily seen to generalize Hamiltonian Cycle and hence is NP -complete. In fact, the Connected f-Factor problem remains NP -complete even when we restrict f(v) to be at least n ϵ for each vertex v and constant 0 ≤ ϵ < 1 ; on the other side of the spectrum of nontrivial lower bounds on f, the problem is known to be polynomial time solvable when f(v) is at least n 3 for every vertex v. In this paper, we extend this line of work and obtain new complexity results based on restrictions on the function f. In particular, we show that when f(v) is restricted to be at least n (log n) c , the problem can be solved in quasi-polynomial time in general and in randomized polynomial time if c ≤ 1 . Furthermore, we show that when c > 1 , the problem is NP -intermediate. [ABSTRACT FROM AUTHOR]

Ramsey quantifiers are a natural object of study not only for logic and computer science but also for the formal semantics of natural language. Restricting attention to finite models leads to the natural question whether all Ramsey quantifiers are either polynomial-time computable or NP-hard, and whether we can give a natural characterization of the polynomial-time computable quantifiers. In this paper, we first show that there exist intermediate Ramsey quantifiers and then we prove a dichotomy result for a large and natural class of Ramsey quantifiers, based on a reasonable and widely believed complexity assumption. We show that the polynomial-time computable quantifiers in this class are exactly the constant-log-bounded Ramsey quantifiers. [ABSTRACT FROM AUTHOR]

A set. D of vertices of a graph G is a dominating set if every vertex of G is contained in D or adjacent to some vertex of D. The number of vertices in a smallest, dominating set. of G is denoted by λ(G). We prove that., under the assumption FPT = W[l] from parameterized complexity, for any constant, c G N+ and computable function ƒ : N → N there is no algorithm which on every input, graph G finds a dominating set. of size at. most, c • λ(G) in ƒ (λ(G)) • |G|0W time. In other words, any constant, approximation of the parameterized dominating set. problem is W[l]-hard. Furthermore, assuming the exponential time hypothesis (ETH) [R. Impagliazzo and R. Pat.uri, J. Comƒput. System, Sei., 62 (2001), pp. 367--375], we can even rule out. the existence of a ƒ (λ(G)) • |G|'log λ(G)) ƒ -time algorithm which on every input, graph G outputs a dominating set. of size at. most. 3+c √log(λ(G)) • λ(G) for every 0 < ∊ < 1. Our hardness reduction is built, on the second author's recent. W[l]-hardness proof of the biclique problem [B. Lin, The parameterized complexity of κ-BLCLIQUE, in Proceedings of the 26t.h Annual AGM--SIAM Symposium on Discrete Algorithms, SODA 2015 (San Diego, GA), AGM, New York, SIAM, Philadelphia, 2015, pp. 605-615], This yields, among other things, a proof without, the probabilistically checkable proof (PGP) machinery that, the classic dominating set. problem has no polynomial time constant, approximation under ETH. [ABSTRACT FROM AUTHOR]

MAX-CUT, EDGE DOMINATING SET, GRAPH COLORING, and HAMILTONIAN CYCLE on graphs of bounded clique-width have received significant attention as they can be formulated in MSO2 (and, therefore, have linear-time algorithms on bounded treewidth graphs by the celebrated Courcelle's theorem), but cannot be formulated in MSO1 (which would have yielded linear-time algorithms on bounded clique-width graphs by a well-known theorem of Courcelle, Makowsky, and Rotics). Each of these problems can be solved in time g(k)nf(k) on graphs of clique-width k. Fomin et al. (2010) showed that the running times cannot be improved to g(k)nO(1) assuming W[1]≠FPT. However, this does not rule out non-trivial improvements to the exponent f(k) in the running times. In a follow-up paper, Fomin et al. (2014) improved the running times for EDGE DOMINATING SET and MAX-CUT to nO(k), and proved that these problems cannot be solved in time g(k)no(k) unless ETH fails. Thus, prior to this work, EDGE DOMINATING SET and MAX-CUT were known to have tight nΘ (k) algorithmic upper and lower bounds. In this article, we provide lower bounds for HAMILTONIAN CYCLE and GRAPH COLORING. For HAMILTONIAN CYCLE, our lower bound g(k)no(k) matches asymptotically the recent upper bound nO(k) due to Bergougnoux, Kanté, and Kwon (2017). As opposed to the asymptotically tight nΘ(k) bounds for EDGE DOMINATING SET, MAX-CUT, and HAMILTONIAN CYCLE, the GRAPH COLORING problem has an upper bound of n O(2k) and a lower bound of merely no(&sqrt; [4]k) (implicit from the W[1]-hardness proof). In this article, we close the gap for GRAPH COLORING by proving a lower bound of n 2o(k). This shows that GRAPH COLORING behaves qualitatively different from the other three problems. To the best of our knowledge, GRAPH COLORING is the first natural problem known to require exponential dependence on the parameter in the exponent of n. [ABSTRACT FROM AUTHOR]

Abstract We study the problem of finding approximate Nash equilibria that satisfy certain conditions, such as providing good social welfare. In particular, we study the problem ϵ -NE δ -SW: find an ϵ -approximate Nash equilibrium (ϵ -NE) that is within δ of the best social welfare achievable by an ϵ -NE. Our main result is that, if the exponential-time hypothesis (ETH) is true, then solving (1 8 − O (δ)) -NE O (δ) -SW for an n × n bimatrix game requires n Ω ˜ (log ⁡ n) time. Building on this result, we show similar conditional running time lower bounds for a number of other decision problems for ϵ -NE, where, for example, the payoffs or supports of players are constrained. We show quasi-polynomial lower bounds for these problems assuming ETH, where these lower bounds apply to ϵ -Nash equilibria for all ϵ < 1 8. The hardness of these other decision problems has so far only been studied in the context of exact equilibria. [ABSTRACT FROM AUTHOR]

We consider the classical scheduling problem on parallel identical machines to minimize the makespan. There is a long history of study on this problem, focusing on exact and approximation algorithms. It is thus natural to consider whether these algorithms can be further improved in terms of running times. We provide strong lower bounds on the running times of exact and approximation schemes for the classical scheduling problem based on Exponential Time Hypothesis, showing that the best known approximation and exact algorithms are almost the best possible in terms of the running time. [ABSTRACT FROM AUTHOR]

A central problem in parameterized algorithms is to obtain algorithms with running time f(k) · nO(1) such that f is as slow growing a function of the parameter k as possible. In particular, a large number of basic parameterized problems admit parameterized algorithms where f(k) is single-exponential, that is, ck for some constant c, which makes aiming for such a running time a natural goal for other problems as well. However, there are still plenty of problems where the f(k) appearing in the best-known running time is worse than single-exponential and it remained "slightly superexponential" even after serious attempts to bring it down. A natural question to ask is whether the f(k) appearing in the running time of the best-known algorithms is optimal for any of these problems. In this paper, we examine parameterized problems where f(k) is kO(k) = 2O(k log k) in the best-known running time, and for a number of such problems we show that the dependence on k in the running time cannot be improved to single-exponential. More precisely we prove the following tight lower bounds, for four natural problems, arising from three different domains: (1) In the Closest String problem, given strings s1, ..., st over an alphabet Σ of length L each, and an integer d, the question is whether there exists a string s over Σ of length L, such that its hamming distance from each of the strings si, 1 ≤ i ≤ t, is at most d. The pattern matching problem Closest String is known to be solvable in times 2O(d log d) · nO(1) and 2O(d log |Σ|) · nO(1). We show that there are no 2o(d log d) · nO(1) or 2o(d log |Σ|) · nO(1) time algorithms, unless the Exponential Time Hypothesis (ETH) fails. (2) The graph embedding problem Distortion, that is, deciding whether a graph G has a metric embedding into the integers with distortion at most d can be solved in time 2O(d log d) · nO(1). We show that there is no 2o(d log d) · nO(1) time algorithm, unless the ETH fails. (3) The Disjoint Paths problem can be solved in time 2O(w log w) · nO(1) on graphs of treewidth at most w. We show that there is no 2o(w log w) · nO(1) time algorithm, unless the ETH fails. (4) The Chromatic Number problem can be solved in time 2O(w log w) ·nO(1) on graphs of treewidth at most w. We show that there is no 2o(w log w) · nO(1) time algorithm, unless the ETH fails. To obtain our results, we first prove the lower bound for variants of basic problems: finding cliques, independent sets, and hitting sets. These artificially constrained variants form a good starting point for proving lower bounds on natural problems without any technical restrictions and could be of independent interest. Several follow-up works have already obtained tight lower bounds by using our framework, and we believe it will prove useful in obtaining even more lower bounds in the future. [ABSTRACT FROM AUTHOR]