Search

Attempts to prove the intractability of the Minimum Circuit Size Problem (\sansM \sansC \sansS \sansP) date as far back as the 1950s and are well motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing \sansM \sansC \sansS \sansP is intractable under worst-case assumptions. While Masek showed in the late 1970s that the version of \sansM \sansC \sansS \sansP for \sansD \sansN \sansF formulas is \sansN \sansP -hard, extending this result to the case of depth-3 AND/OR formulas was open. We show that determining the minimum size of a depth-d formula computing a given Boolean function is \sansN \sansP -hard under quasipolynomial-time randomized reductions for all constant d \geq 2. Our approach is based on a method to "lift"" depth-d formula lower bounds to depth-(d + 1). This method also implies the existence of a function with a 2\Omega d(n) additive gap between its depth-d and depth-(d + 1) formula complexity. We also make progress in the case of general, unrestricted circuits. We show that the version of \sansM \sansC \sansS \sansP where the input is a partial function (represented by a string in \{ 0, 1, \} \ast) is not in \sansP under the Exponential Time Hypothesis (ETH). Intriguingly, we formulate a notion of lower bound statements being (\sansP/\sansp \sanso \sansl \sansy)-recognizable that is closely related to Razborov and Rudich's definition of being (\sansP/\sansp \sanso \sansl \sansy)-constructive. We show that unless there are subexponential-sized circuits computing \sansS \sansA \sansT, the collection of lower bound statements used to prove the correctness of our reductions cannot be (\sansP/\sansp \sanso \sansl \sansy)-recognizable. [ABSTRACT FROM AUTHOR]

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 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]

In the Vertex Planarization problem one asks to delete the minimum possible number of vertices from an input graph to obtain a planar graph. The parameterized complexity of this problem, parameterized by the solution size (the number of deleted vertices) has recently attracted significant attention. The state-of-the-art algorithm of Jansen et al. (2014) runs in time 2 O ( k log k ) ⋅ n on an n -vertex graph with a solution of size k . It remains open if one can obtain a single-exponential dependency on k in the running time bound. One of the core technical contributions of the work of Jansen, Lokshtanov, and Saurabh is an algorithm that solves a weighted variant of Vertex Planarization in time 2 O ( w log w ) ⋅ n on graphs of treewidth w . In this short note we prove that the running time of this routine is tight under the Exponential Time Hypothesis, even in unweighted graphs and when parameterizing by treedepth. Consequently, it is unlikely that a potential single-exponential algorithm for Vertex Planarization parameterized by the solution size can be obtained by merely improving upon the aforementioned bounded treewidth subroutine. [ABSTRACT FROM AUTHOR]

In a jumping finite automaton, the input head can jump to an arbitrary position within the remaining input after reading and consuming a symbol. We characterize the corresponding class of languages in terms of special shuffle expressions and survey other equivalent notions from the existing literature. Moreover, we present several results concerning computational hardness and algorithms for parsing and other basic tasks concerning jumping finite automata. [ABSTRACT FROM AUTHOR]

The strong metric dimension of a graph was first introduced by Sebö and Tannier (2004) as an alternative to the (weak) metric dimension of graphs previously introduced independently by Slater (1975) and by Harary and Melter (1976), and has since been investigated in several research papers. However, the exact worst-case computational complexity of computing the strong metric dimension has remained open beyond being NP -complete. In this communication, we show that the problem of computing the strong metric dimension of a graph of n nodes admits a polynomial-time 2 -approximation, admits a O ∗ ( 2 0 . 287 n ) -time exact computation algorithm, admits a O ( 1 . 273 8 k + n k ) -time exact computation algorithm if the strong metric dimension is at most k , does not admit a polynomial time ( 2 − ε ) -approximation algorithm assuming the unique games conjecture is true, does not admit a polynomial time ( 10 5 − 21 − ε ) -approximation algorithm assuming P ≠ NP , does not admit a O ∗ ( 2 o ( n ) ) -time exact computation algorithm assuming the exponential time hypothesis is true, and does not admit a O ∗ ( n o ( k ) ) -time exact computation algorithm if the strong metric dimension is at most k assuming the exponential time hypothesis is true. [ABSTRACT FROM AUTHOR]

We study several classical decision problems on finite automata under the (Strong) Exponential Time Hypothesis. We focus on three types of problems: universality, equivalence, and emptiness of intersection. All these problems are known to be CoNP-hard for nondeterministic finite automata, even when restricted to unary input alphabets. A different type of problems on finite automata relates to aperiodicity and to synchronizing words. We also consider finite automata that work on commutative alphabets and those working on two-dimensional words. [ABSTRACT FROM AUTHOR]

The use of computational complexity in planning, and in AI in general, has always been a disputed topic. A major problem with ordinary worst-case analyses is that they do not provide any quantitative information: they do not tell us much about the running time of concrete algorithms, nor do they tell us much about the running time of optimal algorithms. We address problems like this by presenting results based on the exponential time hypothesis (ETH), which is a widely accepted hypothesis concerning the time complexity of 3- SAT. By using this approach, we provide, for instance, almost matching upper and lower bounds onthe time complexity of propositional planning. [ABSTRACT FROM AUTHOR]

Given a source string u and a target string w, to decide whether w can be obtained by applying a string morphism on u (i. e., uniformly replacing the symbols in u by strings) constitutes an $\mathcal {NP}$-complete problem. We present a multivariate analysis of this problem (and its many variants) from the viewpoint of parameterised complexity theory, thereby pinning down the sources of its computational hardness. Our results show that most parameterised variants of the string morphism problem are fixed-parameter intractable and, apart from some very special cases, tractable variants can only be obtained by considering a large part of the input as parameters, namely the length of w and the number of different symbols in u. [ABSTRACT FROM AUTHOR]

We study the complexity of the Channel Assignment problem. By applying the meet-in-the-middle approach we get an algorithm for the $$\ell $$ -bounded Channel Assignment (when the edge weights are bounded by $$\ell $$ ) running in time $$O^*((2\sqrt{\ell +1})^n)$$ . This is the first algorithm which breaks the $$(O(\ell ))^n$$ barrier. We extend this algorithm to the counting variant, at the cost of slightly higher polynomial factor. Very recently the second author showed that Channel Assignment does not admit a $$O(c^n)$$ -time algorithm, for a constant c independent of $$\ell $$ . We consider a similar question for Generalized $$T$$ - Coloring, a CSP problem that generalizes Channel Assignment. We show that Generalized $$T$$ - Coloring does not admit a $$2^{2^{o\left( \sqrt{n}\right) }} \mathrm{poly}(r)$$ -time algorithm, where r is the size of the instance. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a novel algorithm to solve projected model counting (PMC). PMC asks to count solutions of a Boolean formula with respect to a given set of projection variables , where multiple solutions that are identical when restricted to the projection variables count as only one solution. Inspired by the observation that the so-called "treewidth" is one of the most prominent structural parameters, our algorithm utilizes small treewidth of the primal graph of the input instance. More precisely, it runs in time O (2 2 k + 4 n 2) where k is the treewidth and n is the input size of the instance. In other words, we obtain that the problem PMC is fixed-parameter tractable when parameterized by treewidth. Further, we take the exponential time hypothesis (ETH) into consideration and establish lower bounds of bounded treewidth algorithms for PMC , yielding asymptotically tight runtime bounds of our algorithm. While the algorithm above serves as a first theoretical upper bound and although it might be quite appealing for small values of k , unsurprisingly a naive implementation adhering to this runtime bound suffers already from instances of relatively small width. Therefore, we turn our attention to several measures in order to resolve this issue towards exploiting treewidth in practice: We present a technique called nested dynamic programming, where different levels of abstractions of the primal graph are used to (recursively) compute and refine tree decompositions of a given instance. Further, we integrate the concept of hybrid solving, where subproblems hidden by the abstraction are solved by classical search-based solvers, which leads to an interleaving of parameterized and classical solving. Finally, we provide a nested dynamic programming algorithm and an implementation that relies on database technology for PMC and a prominent special case of PMC, namely model counting (#Sat). Experiments indicate that the advancements are promising, allowing us to solve instances of treewidth upper bounds beyond 200. [ABSTRACT FROM AUTHOR]

Our goal is to show tight bounds on the running time of algorithms for scheduling and packing problems. To prove lower bounds, we investigate implications of the exponential time hypothesis on such algorithms. For exact algorithms we consider the dependence of the running time on the number n of items (for packing) or jobs (for scheduling). We prove a lower bound of 2o(n) x ∥I∥O(n), where ∥I∥ denotes the encoding length of the instance, for several of these problems, including SUBSETSUM, KNAPSACK, BINPACKING, , and . We also develop an algorithmic framework that is able to solve a large number of scheduling and packing problems in time 2o(n) x ∑I∑O(n). Finally, we consider approximation schemes. We show that there is no polynomial time approximation scheme for MULTIPLEKNAPSACK (MKS) and 2D-KNAPSACK with running time 2o(1/ε) x ∑I∑O(n) and no(1/ε) x ∑I∑O(n), respectively. [ABSTRACT FROM AUTHOR]

In the Edge Clique Cover (ECC) problem, given an undirected graph G and an integer k, we ask whether one can choose k cliques in G such that each edge of G is contained in at least one of the chosen cliques. Gramm et al. [ACM J. Exp. Algorithmics, 13 (2008)] have shown a set of simple rules that reduce the number of vertices of G to 2k while preserving the answer to the instance at hand, that is, they have shown a kernel for the problem with at most 2k vertices. No algorithm is known with significantly better running time bound than a brute-force search on this kernel. In this paper, we show that the approach of Gramm et al. is essentially optimal: we present a polynomial-time algorithm that reduces an arbitrary instance of 3-CNF-SAT with n variables and m clauses to an equivalent ECC instance (G, k) with k = O(log n) and |V (G)| = O(n + m). Consequently, there is no 22o(k) poly(n) time algorithm for the ECC problem, unless the Exponential Time Hypothesis fails. Moreover, our reduction also implies that, unless P = NP, the ECC problem does not admit a subexponential kernel, i.e., a kernel of size 2o(k). [ABSTRACT FROM AUTHOR]

The $$3$$ -coloring problem is well known to be NP-complete. It is also well known that it remains NP-complete when the input is restricted to graphs with diameter $$4$$ . Moreover, assuming the Exponential Time Hypothesis (ETH), $$3$$ -coloring cannot be solved in time $$2^{o(n)}$$ on graphs with $$n$$ vertices and diameter at most $$4$$ . In spite of extensive studies of the $$3$$ -coloring problem with respect to several basic parameters, the complexity status of this problem on graphs with small diameter, i.e. with diameter at most $$2$$ , or at most $$3$$ , has been an open problem. In this paper we investigate graphs with small diameter. For graphs with diameter at most $$2$$ , we provide the first subexponential algorithm for $$3$$ -coloring, with complexity $$2^{O(\sqrt{n\log n})}$$ . Furthermore we extend the notion of an articulation vertex to that of an articulation neighborhood, and we provide a polynomial algorithm for $$3$$ -coloring on graphs with diameter $$2$$ that have at least one articulation neighborhood. For graphs with diameter at most $$3$$ , we establish the complexity of $$3$$ -coloring by proving for every $${\varepsilon \in [0,1)}$$ that $$3$$ -coloring is NP-complete on triangle-free graphs of diameter $$3$$ and radius $$2$$ with $$n$$ vertices and minimum degree $$\delta =\varTheta (n^{\varepsilon })$$ . Moreover, assuming ETH, we use three different amplification techniques of our hardness results, in order to obtain for every $${\varepsilon \in [0,1)}$$ subexponential asymptotic lower bounds for the complexity of $$3$$ -coloring on triangle-free graphs with diameter $$3$$ and minimum degree $${\delta =\varTheta (n^{\varepsilon })}$$ . Finally, we provide a $$3$$ -coloring algorithm with running time $${ 2^{O\left( \min \{\delta \varDelta ,\ \frac{n}{\delta }\log \delta \}\right) }}$$ for arbitrary graphs with diameter $$3$$ , where $$n$$ is the number of vertices and $$ \delta $$ (resp. $$\varDelta $$ ) is the minimum (resp. maximum) degree of the input graph. To the best of our knowledge, this is the first subexponential algorithm for graphs with $${\delta =\omega (1)}$$ and for graphs with $${\delta =O(1)}$$ and $$\varDelta =o(n)$$ . Due to the above lower bounds of the complexity of $$3$$ -coloring, the running time of this algorithm is asymptotically almost tight when the minimum degree of the input graph is $$\delta =\varTheta (n^{\varepsilon })$$ , where $${\varepsilon \in [\frac{1}{2},1)}$$ , as its time complexity is $${2^{O\left( \frac{n}{\delta } \log \delta \right) } = 2^{O\left( n^{1-\varepsilon } \log n\right) }}$$ and the corresponding lower bound states that there is no $$2^{o\left( n^{1-\varepsilon }\right) }$$ -time algorithm. [ABSTRACT FROM AUTHOR]