We show that sufficiently low tensor rank for the balanced tripartitioning tensor P_d(x,y,z) = ∑_{A,B,C ∈ binom([3d],d):A∪ B∪ C = [3d]} x_A y_B z_C for a large enough constant d implies uniform arithmetic circuits for the matrix permanent that are exponentially smaller than circuits obtainable from Ryser’s formula. Under the same low-rank assumption, we obtain exponential-time improvements over the state of the art for a wide variety of related counting and decision problems. Our main methodological contribution is that the tensors P_n have a desirable Kronecker scaling property: They can be decomposed efficiently into a small sum of restrictions of Kronecker powers of P_d for constant d. We prove this with a new technique relying on Steinitz’s lemma, which we hence call Steinitz balancing. As a consequence of our methods, we show that the mentioned low-rank assumption (and hence the improved algorithms) is implied by Strassen’s asymptotic rank conjecture [Progr. Math. 120 (1994)], a bold conjecture that has recently seen intriguing progress.

We give unconditional parameterized complexity lower bounds on pure dynamic programming algorithms - as modeled by tropical circuits - for connectivity problems such as the Traveling Salesperson Problem. Our lower bounds are higher than the currently fastest algorithms that rely on algebra and give evidence that these algebraic aspects are unavoidable for competitive worst case running times. Specifically, we study input graphs with a small width parameter such as treewidth and pathwidth and show that for any k there exists a graph G of pathwidth at most k and k^𝒪(1) vertices such that any tropical circuit calculating the optimal value of a Traveling Salesperson round tour uses at least 2^Ω(k log log k) gates. We establish this result by linking tropical circuit complexity to the nondeterministic communication complexity of specific compatibility matrices. These matrices encode whether two partial solutions combine into a full solution, and Raz and Spieker [Combinatorica 1995] previously proved a lower bound for this complexity measure.

We present a data structure that we call a Dynamic Representative Set. In its most basic form, it is given two parameters $0\lt k\lt n$ and allows us to maintain a representation of a family $\mathcal{F}$ of subsets of $\{1, \ldots, n\}$. It supports basic update operations (unioning of two families, element convolution) and a query operation that determines for a set $B \subseteq\{1, \ldots, n\}$ whether there is a set $A \in \mathcal{F}$ of size at most $k-|B|$ such that A and B are disjoint. After $2^{k+O\left(\sqrt{k} \log ^{2} k\right)} n \log n$ preprocessing time, all operations use $2^{k+O\left(\sqrt{k} \log ^{2} k\right)} \log n$ time. Our data structure has many algorithmic consequences that improve over previous works. One application is a deterministic algorithm for the Weighted Directed k-Path problem, one of the central problems in parameterized complexity. Our algorithm takes as input an n-vertex directed graph $G=(V, E)$ with edge lengths and an integer k, and it outputs the minimum edge length of a path on k vertices in $2^{k+O\left(\sqrt{k} \log ^{2} k\right)}(n+m) \log n$ time (in the word RAM model where weights fit into a single word). Modulo the lower order term $2^{O\left(\sqrt{k} \log ^{2} k\right)}$, this answers a question that has been repeatedly posed as a major open problem in the field. Index Terms-Algorithms, Analysis of Algorithms and Problem Complexity

In a classical scheduling problem, we are given a set of n jobs of unit length with precedence constraints, and the goal is to find a schedule of these jobs on m identical machines that minimizes the makespan. In standard 3-field notation, it is denoted as Pm|prec,pj = 1 |Cmax.

Abstract In the Choosability problem (or list chromatic number problem), for a given graph G, we need to find the smallest k such that G admits a list coloring for any list assignment where all lists contain at least k colors. The problem is tightly connected with the well-studied Coloring and List Coloring problems. However, the knowledge of the complexity landscape for the Choosability problem is pretty scarce. Moreover, most of the known results only provide lower bounds for its computational complexity and do not provide ways to cope with the intractability. The main objective of our paper is to construct the first non-trivial exact exponential algorithms for the Choosability problem, and complete the picture with parameterized results. Specifically, we present the first single-exponential algorithm for the decision version of the problem with fixed k. This result answers an implicit question from Eppstein on a stackexchange thread discussing upper bounds on the union of lists assigned to vertices. We also present a $$2^{n^2} poly(n)$$ time algorithm for the general Choosability problem. In the parameterized setting, we give a polynomial kernel for the problem parameterized by vertex cover, and algorithms that run in FPT time when parameterized by a size of a clique-modulator and by the dual parameterization $$n-k$$ . Additionally, we show that Choosability admits a significant running time improvement if it is parameterized by cutwidth in comparison with the parameterization by treewidth studied by Marx and Mitsou [ICALP’16]. On the negative side, we provide a lower bound parameterized by a size of a modulator to split graphs under assumption of the Exponential Time Hypothesis.

We revisit the classic task of finding the shortest tour of n points in d -dimensional Euclidean space, for any fixed constant d ⩾ 2. We determine the optimal dependence on ɛ in the running time of an algorithm that computes a (1 + ɛ)-approximate tour, under a plausible assumption. Specifically, we give an algorithm that runs in \(2^{\mathcal {O}(1/\varepsilon ^{d-1})} n\log n\) time. This improves the previously smallest dependence on ɛ in the running time \((1/\varepsilon)^{\mathcal {O}(1/\varepsilon ^{d-1})}n \log n\) of the algorithm by Rao and Smith (STOC 1998). We also show that a \(2^{o(1/\varepsilon ^{d-1})}\mathrm{poly}(n)\) algorithm would violate the Gap-Exponential Time Hypothesis (Gap-ETH). Our new algorithm builds upon the celebrated quadtree-based methods initially proposed by Arora (J. ACM 1998), but it adds a new idea that we call sparsity-sensitive patching . On a high level this lets the granularity with which we simplify the tour depend on how sparse it is locally. We demonstrate that our technique extends to other problems, by showing that for Steiner Tree and Rectilinear Steiner Tree it yields the same running time. We complement our results with a matching Gap-ETH lower bound for Rectilinear Steiner Tree.

A homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H). In the graph homomorphism problem, denoted by Hom(H), the graph H is fixed and we need to determine if there exists a homomorphism from an instance graph G to H. We study the complexity of the problem parameterized by the cutwidth of G, i.e., we assume that G is given along with a linear ordering v_1,…,v_n of V(G) such that, for each i ∈ {1,…,n-1}, the number of edges with one endpoint in {v_1,…,v_i} and the other in {v_{i+1},…,v_n} is at most k. We aim, for each H, for algorithms for Hom(H) running in time c_H^k n^𝒪(1) and matching lower bounds that exclude c_H^{k⋅o(1)} n^𝒪(1) or c_H^{k(1-Ω(1))} n^𝒪(1) time algorithms under the (Strong) Exponential Time Hypothesis. In the paper we introduce a new parameter that we call mimsup(H). Our main contribution is strong evidence of a close connection between c_H and mimsup(H): - an information-theoretic argument that the number of states needed in a natural dynamic programming algorithm is at most mimsup(H)^k, - lower bounds that show that for almost all graphs H indeed we have c_H ≥ mimsup(H), assuming the (Strong) Exponential-Time Hypothesis, and - an algorithm with running time exp(𝒪(mimsup(H)⋅k log k)) n^𝒪(1). In the last result we do not need to assume that H is a fixed graph. Thus, as a consequence, we obtain that the problem of deciding whether G admits a homomorphism to H is fixed-parameter tractable, when parameterized by cutwidth of G and mimsup(H). The parameter mimsup(H) can be thought of as the p-th root of the maximum induced matching number in the graph obtained by multiplying p copies of H via a certain graph product, where p tends to infinity. It can also be defined as an asymptotic rank parameter of the adjacency matrix of H. Such parameters play a central role in, among others, algebraic complexity theory and additive combinatorics. Our results tightly link the parameterized complexity of a problem to such an asymptotic matrix parameter for the first time.

We study a special case of the Steiner Tree problem in which the input graph does not have a minor model of a complete graph on 4 vertices for which all branch sets contain a terminal. We show that this problem can be solved in $O(n^4)$ time, where $n$ denotes the number of vertices in the input graph. This generalizes a seminal paper by Erickson et al. [Math. Oper. Res., 1987] that solves Steiner tree on planar graphs with all terminals on one face in polynomial time.

Let XNLP be the class of parameterized problems such that an instance of size n with parameter k can be solved nondeterministically in time f(k)nO(1) and space f(k)log⁡(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as List Coloring and Precoloring Extension with pathwidth as parameter, Scheduling of Jobs with Precedence Constraints, with both number of machines and partial order width as parameter, Bandwidth and variants of Weighted CNF-Satisfiability. In particular, this implies that all these problems are W[t]-hard for all t.

We give a fine-grained classification of evaluating the Tutte polynomial $T(G;x,y)$ on all integer points on graphs with small treewidth and cutwidth. Specifically, we show for any point $(x,y) \in \mathbb{Z}^2$ that either - can be computed in polynomial time, - can be computed in $2^{O(tw)}n^{O(1)}$ time, but not in $2^{o(ctw)}n^{O(1)}$ time assuming the Exponential Time Hypothesis (ETH), - can be computed in $2^{O(tw \log tw)}n^{O(1)}$ time, but not in $2^{o(ctw \log ctw)}n^{O(1)}$ time assuming the ETH, where we assume tree decompositions of treewidth $tw$ and cutwidth decompositions of cutwidth $ctw$ are given as input along with the input graph on $n$ vertices and point $(x,y)$. To obtain these results, we refine the existing reductions that were instrumental for the seminal dichotomy by Jaeger, Welsh and Vertigan~[Math. Proc. Cambridge Philos. Soc'90]. One of our technical contributions is a new rank bound of a matrix that indicates whether the union of two forests is a forest itself, which we use to show that the number of forests of a graph can be counted in $2^{O(tw)}n^{O(1)}$ time.

We show that there is no $2^{o(k^2)} n^{O(1)}$ time algorithm for Independent Set on $n$-vertex graphs with rank-width $k$, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches the $2^{O(k^2)} n^{O(1)}$ time algorithm given by Bui-Xuan, Telle, and Vatshelle [Discret. Appl. Math., 2010] and it answers the open question of Bergougnoux and Kanté [SIAM J. Discret. Math., 2021]. We also show that the known $2^{O(k^2)} n^{O(1)}$ time algorithms for Weighted Dominating Set, Maximum Induced Matching and Feedback Vertex Set parameterized by rank-width $k$ are optimal assuming ETH. Our results are the first tight ETH lower bounds parameterized by rank-width that do not follow directly from lower bounds for $n$-vertex graphs.

Abstract. In the Bin Packing problem one is given [Formula: see text] items with weights [Formula: see text] and [Formula: see text] bins with capacities [Formula: see text]. The goal is to partition the items into sets [Formula: see text] such that [Formula: see text] for every bin [Formula: see text], where [Formula: see text] denotes [Formula: see text]. Björklund, Husfeldt, and Koivisto [ SIAM J. Comput., 39 (2009), pp. 546–563] presented an [Formula: see text] time algorithm for Bin Packing (the [Formula: see text] notation omits factors polynomial in the input size). In this paper, we show that for every [Formula: see text] there exists a constant [Formula: see text] such that an instance of Bin Packing with [Formula: see text] bins can be solved in [Formula: see text] randomized time. Before our work, such improved algorithms were not known even for [Formula: see text]. A key step in our approach is the following new result in Littlewood–Offord theory on the additive combinatorics of subset sums: For every [Formula: see text] there exists an [Formula: see text] such that if [Formula: see text] for some [Formula: see text], then [Formula: see text].

Abstract. For many algorithmic problems on graphs of treewidth [Formula: see text], a standard dynamic programming approach gives algorithms with time and space complexity [Formula: see text]. It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the space complexity to polynomial, while retaining time complexity of the form [Formula: see text], where [Formula: see text] is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with time and space complexity [Formula: see text] on graphs of treewidth [Formula: see text], but it is not clear how to convert them into time-efficient polynomial space algorithms for graphs of low treedepth. Cygan et al. [ ACM Trans. Algorithms, 18 (2022), 17] introduced the Cut&Count technique and showed that a certain class of problems with connectivity constraints can be solved in time and space complexity [Formula: see text]. Recently, Hegerfeld and Kratsch (STACS’20) showed that, for some of those problems, the Cut&Count technique can be also applied in the setting of treedepth, and it gives algorithms with running time [Formula: see text] and polynomial space usage. However, several important problems eluded such a treatment, with the most prominent examples being Hamiltonian Cycle and Longest Path. In this paper, we clarify the situation by showing that Hamiltonian cycle, Hamiltonian Path, Long Cycle, Long Path, and Min Cycle Cover all admit [Formula: see text]-time and polynomial space algorithms on graphs of treedepth [Formula: see text]. The algorithms are randomized Monte Carlo with only false negatives.

The generalized k -server problem is a far-reaching extension of the k -server problem with several applications. Here, each server s i lies in its own metric space M i . A request is a k -tuple r = ( r 1 , r 2 ,… , r k , which is served by moving some server s i to the point r i ∈ M i , and the goal is to minimize the total distance traveled by the servers. Despite much work, no f ( k )-competitive algorithm is known for the problem for k > 2 servers, even for special cases such as uniform metrics and lines. Here, we consider the problem in uniform metrics and give the first f ( k )-competitive algorithms for general k . In particular, we obtain deterministic and randomized algorithms with competitive ratio k · 2 k and O ( k 3 log k ), respectively. Our deterministic bound is based on a novel application of the polynomial method to online algorithms, and essentially matches the long-known lower bound of 2 k -1. We also give a 2 2 O(k) -competitive deterministic algorithm for weighted uniform metrics, which also essentially matches the recent doubly exponential lower bound for the problem.

We study the fine-grained complexity of counting the number of colorings and connected spanning edge sets parameterized by the cutwidth and treewidth of the graph. While decompositions of small treewidth decompose the graph with small vertex separators, decompositions with small cutwidth decompose the graph with small \emph{edge} separators. Let $p,q \in \mathbb{N}$ such that $p$ is a prime and $q \geq 3$. - If $p$ divides $q-1$, there is a $(q-1)^{\text{ctw}}n^{O(1)}$ time algorithm for counting list $q$-colorings modulo $p$ of $n$-vertex graphs of cutwidth $\text{ctw}$ and for all $\varepsilon>0$ there is no algorithm running in time $(q-1-\varepsilon)^{\text{ctw}} n^{O(1)}$, assuming the Strong Exponential Time Hypothesis (SETH). - If $p$ does not divide $q-1$, there is a (folklore) $q^{\text{ctw}}n^{O(1)}$ time algorithm for counting list $q$-colorings modulo $p$ of $n$-vertex graphs of cutwidth $\text{ctw}$ and for all $\varepsilon>0$ there is no algorithm running in time $(q-\varepsilon)^{\text{ctw}} n^{O(1)}$, assuming SETH. The lower bounds are in stark contrast with the existing $2^{\text{ctw}}n^{O(1)}$ time algorithm to compute the chromatic number of a graph by Jansen and Nederlof~[Theor. Comput. Sci.'18]. Both our algorithms and lower bounds employ use of the matrix rank method, by relating the complexity of the problem to the rank of a certain `compatibility matrix' in a non-trivial way. We extend our lower bounds to counting connected spanning edge sets modulo $p$ and give an algorithm with matching running time for both treewidth and cutwidth.

The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87] provides a self-reduction scheme that allows one to assume that a given instance of a problem has a unique solution, provided a solution exists at all. Since its introduction, much effort has been dedicated towards derandomization of the Isolation Lemma for specific classes of problems. So far, the focus was mainly on problems solvable in polynomial time. In this paper, we study a setting that is more typical for $\mathsf{NP}$-complete problems, and obtain partial derandomizations in the form of significantly decreasing the number of required random bits. In particular, motivated by the advances in parameterized algorithms, we focus on problems on decomposable graphs. For example, for the problem of detecting a Hamiltonian cycle, we build upon the rank-based approach from [Bodlaender et al., Inf. Comput.'15] and design isolation schemes that use - $O(t\log n + \log^2{n})$ random bits on graphs of treewidth at most $t$; - $O(\sqrt{n})$ random bits on planar or $H$-minor free graphs; and - $O(n)$-random bits on general graphs. In all these schemes, the weights are bounded exponentially in the number of random bits used. As a corollary, for every fixed $H$ we obtain an algorithm for detecting a Hamiltonian cycle in an $H$-minor-free graph that runs in deterministic time $2^{O(\sqrt{n})}$ and uses polynomial space; this is the first algorithm to achieve such complexity guarantees. For problems of more local nature, such as finding an independent set of maximum size, we obtain isolation schemes on graphs of treedepth at most $d$ that use $O(d)$ random bits and assign polynomially-bounded weights. We also complement our findings with several unconditional and conditional lower bounds, which show that many of the results cannot be significantly improved.

Abstract We study a natural variant of scheduling that we call partial scheduling: in this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but only k jobs, have to be processed. Specifically, we aim to determine the fine-grained parameterized complexity of partial scheduling problems parameterized by k for all variants of scheduling problems that minimize the makespan and involve unit/arbitrary processing times, identical/unrelated parallel machines, release/due dates, and precedence constraints. That is, we investigate whether algorithms with runtimes of the type $$f(k)n^{{\mathcal {O}}(1)}$$ f ( k ) n O ( 1 ) or $$n^{{\mathcal {O}}(f(k))}$$ n O ( f ( k ) ) exist for a function f that is as small as possible. Our contribution is two-fold: First, we categorize each variant to be either in $${\mathsf {P}}$$ P , $${{\mathsf {N}}}{{\mathsf {P}}}$$ N P -complete and fixed-parameter tractable by k, or $${\mathsf {W}}[1]$$ W [ 1 ] -hard parameterized by k. Second, for many interesting cases we further investigate the runtime on a finer scale and obtain run times that are (almost) optimal assuming the Exponential Time Hypothesis. As one of our main technical contributions, we give an $${\mathcal {O}}(8^kk(|V|+|E|))$$ O ( 8 k k ( | V | + | E | ) ) time algorithm to solve instances of partial scheduling problems minimizing the makespan with unit length jobs, precedence constraints and release dates, where $$G=(V,E)$$ G = ( V , E ) is the graph with precedence constraints.

For the vast majority of local problems on graphs of small treewidth (where, by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give c tw | V | O(1) time algorithms, where tw is the treewidth of the input graph G = ( V,E ) and c is a constant. On the other hand, for problems with a global requirement (usually connectivity) the best–known algorithms were naive dynamic programming schemes running in at least tw tw time. We bridge this gap by introducing a technique we named Cut&Count that allows to produce c tw | V | O(1) time Monte-Carlo algorithms for most connectivity-type problems, including Hamiltonian Path , Steiner Tree , Feedback Vertex Set and Connected Dominating Set . These results have numerous consequences in various fields, like parameterized complexity, exact and approximate algorithms on planar and H -minor-free graphs and exact algorithms on graphs of bounded degree. The constant c in our algorithms is in all cases small, and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. In all these fields we are able to improve the best-known results for some problems. Also, looking from a more theoretical perspective, our results are surprising since the equivalence relation that partitions all partial solutions with respect to extendability to global solutions seems to consist of at least tw tw equivalence classes for all these problems. Our results answer an open problem raised by Lokshtanov, Marx and Saurabh [SODA’11]. In contrast to the problems aimed at minimizing the number of connected components that we solve using Cut&Count as mentioned above, we show that, assuming the Exponential Time Hypothesis, the aforementioned gap cannot be bridged for some problems that aim to maximize the number of connected components like Cycle Packing .

In the Feedback Vertex Set (FVS) problem, one is given an undirected graph G and an integer k , and one needs to determine whether there exists a set of k vertices that intersects all cycles of G (a so-called feedback vertex set). Feedback Vertex Set is one of the most central problems in parameterized complexity: It served as an excellent testbed for many important algorithmic techniques in the field such as Iterative Compression [Guo et al. (JCSS’06)], Randomized Branching [Becker et al. (J. Artif. Intell. Res’00)] and Cut&Count [Cygan et al. (FOCS’11)]. In particular, there has been a long race for the smallest dependence f(k) in run times of the type O ⋆ (f(k)) , where the O ⋆ notation omits factors polynomial in n . This race seemed to have reached a conclusion in 2011, when a randomized O ⋆ (3 k ) time algorithm based on Cut&Count was introduced. In this work, we show the contrary and give a O ⋆ (2.7 k ) time randomized algorithm. Our algorithm combines all mentioned techniques with substantial new ideas: First, we show that, given a feedback vertex set of size k of bounded average degree, a tree decomposition of width (1-Ω (1))k can be found in polynomial time. Second, we give a randomized branching strategy inspired by the one from [Becker et al. (J. Artif. Intell. Res’00)] to reduce to the aforementioned bounded average degree setting. Third, we obtain significant run time improvements by employing fast matrix multiplication.

Let XNLP be the class of parameterized prob-lems such that an instance of size$n$with parameter$k$can be solved nondeterministically in time$f$($k$) nO(1)and space f (k) log(n) (for some computable function f). We give a wide variety of XNLP-complete problems, such as List Coloringand Precoloring Extensionwith pathwidth as parameter, Scheduling Of Jobs With Precedence Constraints, with both number of machines and partial order width as parameter, Bandwidthand variants of Weighted Cnf-satisfiability and reconfiguration problems. In particular, this implies that all these problems are W[$t$]-hard for all t. This also answers a long standing question on the parameterized complexity of the Bandwidth problem.

We revisit the classic task of finding the shortest tour of$n$, points in d-dimensional Euclidean space, for any fixed constant$d\geqslant 2$. We determine the optimal dependence on$\varepsilon$in the running time of an algorithm that computes a$(1+\varepsilon){-}$approximate tour, under a plausible assumption, Specifically, we give an algorithm that runs in$2^{\mathcal{O}(1/\varepsilon^{d-1})}n\log n$time. This improves the previously smallest dependence on$\varepsilon$in the running time$(1/\varepsilon)^{\mathcal{O}(1/\varepsilon^{d-1})}n\log n$of the algorithm by Rao and Smith (STOC 1998). We also show that a$2^{o(1/\varepsilon^{d-1})}\text{poly}(n)$algorithm would violate the Gap-Exponential Time Hypothesis (Gap-ETH). Our new algorithm builds upon the celebrated quadtree-based methods initially proposed by Arora (J. ACM 1998), but it adds a new idea that we call sparsity-sensitive patching. On a high level this lets the granularity with which we simplify the tour depend on how sparse it is locally. We demonstrate that our technique extends to other problems, by showing that for Steiner Tree and Rectilinear Steiner Tree it yields the same running time. We complement our results with a matching Gap-Ethlower bound for Rectilinear Steiner Tree.

In the Bin Packing problem one is given n items with weights w1, …, wn and m bins with capacities c1, …, cm. The goal is to find a partition of the items into sets S1, …, Sm such that w(Sj) ≤ cj for every bin j, where w(X) denotes Σi∊xwi. Björklund, Husfeldt and Koivisto (SICOMP 2009) presented an time algorithm for Bin Packing. In this paper, we show that for every m ∊ ℕ there exists a constant σm > 0 such that an instance of Bin Packing with m bins can be solved in randomized time. Before our work, such improved algorithms were not known even for m equals 4. A key step in our approach is the following new result in Littlewood-Offord theory on the additive combinatorics of subset sums: For every δ > 0 there exists an ∊ > 0 such that if |{X ⊆ {1, …, n} : w(X) = v}| ≥ 2(1–∊)n for some v then |{w(X) : X ⊆ {1, …, n}}| ≤ 2δn.

We present an O∗(20.5n) time and O∗(20.249999n) space randomized algorithm for solving worst-case Subset Sum instances with n integers. This is the first improvement over the long-standing O∗(2n/2) time and O∗(2n/4) space algorithm due to Schroeppel and Shamir (FOCS 1979).

In the Feedback Vertex Set problem, one is given an undirected graph G and an integer k, and one needs to determine whether there exists a set of k vertices that intersects all cycles of G (a so-called feedback vertex set). Feedback Vertex Set is one of the most central problems in parameterized complexity: It served as an excellent test bed for many important algorithmic techniques in the field such as Iterative Compression [Guo et al. (JCSS'06)], Randomized Branching [Becker et al. (J. Artif. Intell. Res'00)] and Cut&Count [Cygan et al. (FOCS'11)]. In particular, there has been a long race for the smallest dependence f (k) in run times of the type O*(f (k)), where the O* notation omits factors polynomial in n. This race seemed to be run in 2011, when a randomized O*(3k) time algorithm based on Cut&Count was introduced. In this work, we show the contrary and give a O*(2.7k) time randomized algorithm. Our algorithm combines all mentioned techniques with substantial new ideas: First, we show that, given a feedback vertex set of size k of bounded average degree, a tree decomposition of width (1 – Ω(1))k can be found in polynomial time. Second, we give a randomized branching strategy inspired by the one from [Becker et al. (J. Artif. Intell. Res’00)] to reduce to the aforementioned bounded average degree setting. Third, we obtain significant run time improvements by employing fast matrix multiplication.

The symmetric traveling salesman problem (TSP) is the problem of finding the shortest Hamiltonian cycle in an edge-weighted undirected graph. In 1962 Bellman, and independently Held and Karp, showed that TSP instances with n cities can be solved in O(n 22 n ) time. Since then it has been a notorious problem to improve the runtime to O((2−є) n ) for some constant є>0. In this work we establish the following progress: If (s× s)-matrices can be multiplied in s 2+o(1) time, than all instances of TSP in bipartite graphs can be solved in O(1.9999 n ) time by a randomized algorithm with constant error probability. We also indicate how our methods may be useful to solve TSP in non-bipartite graphs.

We resolve the fine-grained parameterized complexity of detecting and counting small patterns in planar graphs, assuming the Exponential Time Hypothesis. Given an n-vertex planar graph G and a k-vertex pattern graph P, we compute the number of (induced) copies of P in G in time

The S TEINER T REE 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 n O(k) time and n O(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 P LANAR S TEINER T REE with running time 2 O(k) n O(√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 ) n o(√k) algorithm for P LANAR S TEINER T REE for any computable function f , unless the Exponential Time Hypothesis fails.

In the Equal-Subset-Sum problem, we are given a set $S$ of $n$ integers and the problem is to decide if there exist two disjoint nonempty subsets $A,B \subseteq S$, whose elements sum up to the same value. The problem is NP-complete. The state-of-the-art algorithm runs in $O^{*}(3^{n/2}) \le O^{*}(1.7321^n)$ time and is based on the meet-in-the-middle technique. In this paper, we improve upon this algorithm and give $O^{*}(1.7088^n)$ worst case Monte Carlo algorithm. This answers the open problem from Woeginger's inspirational survey. Additionally, we analyse the polynomial space algorithm for Equal-Subset-Sum. A naive polynomial space algorithm for Equal-Subset-Sum runs in $O^{*}(3^n)$ time. With read-only access to the exponentially many random bits, we show a randomized algorithm running in $O^{*}(2.6817^n)$ time and polynomial space.

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 using only polynomial space. Furthermore, we show the running time of our algorithm is almost tight: we prove that there is no algorithm for Planar Steiner Tree for any computable function f, unless the Exponential Time Hypothesis fails.

In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and an integer $$r>1$$ , and the goal is to design an approximation algorithm with the fastest possible running time. We give randomized algorithms that establish an approximation ratio of (Throughout, $${\tilde{O}}$$ and $$O^*$$ omit $$\hbox {polyloglog} (r)$$ and factors polynomial in the input size, respectively.) The best known time bounds for all problems were $$O^*(2^{n/r})$$ (Bourgeois et al. in Discret Appl Math 159(17):1954–1970, 2011; Cygan et al. in Exponential-time approximation of hard problems, 2008). For maximum independent set and chromatic number, these bounds were complemented by $$\exp (n^{1-o(1)}/r^{1+o(1)})$$ lower bounds (under the Exponential Time Hypothesis (ETH)) (Chalermsook et al. in Foundations of computer science, FOCS, pp. 370–379, 2013; Laekhanukit in Inapproximability of combinatorial problems in subexponential-time. Ph.D. thesis, 2014). Our results show that the naturally-looking $$O^*(2^{n/r})$$ bounds are not tight for all these problems. The key to these results is a sparsification procedure that reduces a problem to a bounded-degree variant, allowing the use of approximation algorithms for bounded-degree graphs. To obtain the first two results, we introduce a new randomized branching rule. Finally, we show a connection between PCP parameters and exponential-time approximation algorithms. This connection together with our independent set algorithm refute the possibility to overly reduce the size of Chan’s PCP (Chan in J. ACM 63(3):27:1–27:32, 2016). It also implies that a (significant) improvement over our result will refute the gap-ETH conjecture (Dinur in Electron Colloq Comput Complex (ECCC) 23:128, 2016; Manurangsi and Raghavendra in A birthday repetition theorem and complexity of approximating dense CSPs, 2016).

Computing the smallest number q such that the vertices of a given graph can be properly q-colored, known as the chromatic number, is one of the oldest and most fundamental problems in combinatorial optimization. The q-Coloring problem has been studied intensively using the framework of parameterized algorithmics, resulting in a very good understanding of the best-possible algorithms for several parameterizations based on the structure of the graph. For example, algorithms are known to solve the problem on graphs of treewidth tw in time O⁎(qtw), while a running time of O⁎((q−ε)tw) is impossible assuming the Strong Exponential Time Hypothesis (SETH). While there is an abundance of work for parameterizations based on decompositions of the graph by vertex separators, almost nothing is known about parameterizations based on edge separators. We fill this gap by studying q-Coloring parameterized by cutwidth, and parameterized by pathwidth in bounded-degree graphs. Our research uncovers interesting new ways to exploit small edge separators. We present two algorithms for q-Coloring parameterized by cutwidth ctw: a deterministic one that runs in time O⁎(2ω⋅ctw), where ω is the square matrix multiplication exponent, and a randomized one with runtime O⁎(2ctw). In sharp contrast to earlier work, the running time is independent of q. The dependence on cutwidth is optimal: we prove that even 3-Coloring cannot be solved in O⁎((2−ε)ctw) time assuming SETH. Our algorithms rely on a new rank bound for a matrix that describes compatible colorings. Combined with a simple communication protocol for evaluating a product of two polynomials, this also yields an O⁎((⌊d/2⌋+1)pw) time randomized algorithm for q-Coloring on graphs of pathwidth pw and maximum degree d. Such a runtime was first obtained by Björklund, but only for graphs with few proper colorings. We also prove that this result is optimal in the sense that no O⁎((⌊d/2⌋+1−ε)pw)-time algorithm exists assuming SETH.

The generalized k-server problem is a far-reaching extension of the k-server problem with several applications. Here, each server si lies in its own metric space Mi. A request is a k-tuple r = (r1, r2, …, rk) and to serve it, we need to move some server si to the point ri ∊ Mi, and the goal is to minimize the total distance traveled by the servers. Despite much work, no f(k)-competitive algorithm is known for the problem for k > 2 servers, even for special cases such as uniform metrics and lines. Here, we consider the problem in uniform metrics and give the first f(k)-competitive algorithms for general k. In particular, we obtain deterministic and randomized algorithms with competitive ratio k · 2k and O(k3 log k) respectively. Our deterministic bound is based on a novel application of the polynomial method to online algorithms, and essentially matches the long-known lower bound of 2k – 1. We also give a 22O(k)-competitive deterministic algorithm for weighted uniform metrics, which also essentially matches the recent doubly exponential lower bound for the problem.

For even k ∊ ℕ, the matchings connectivity matrix Mk is a binary matrix indexed by perfect matchings on k vertices; the entry at (M, M‘) is 1 iff M ∪ M‘ forms a single cycle. Cygan et al. (STOC 2013) showed that the rank of Mk over ℤ is and used this to give an time algorithm for counting Hamiltonian cycles modulo 2 on graphs of pathwidth pw, carrying over to the decision problem via witness isolation. The same authors complemented their algorithm by an essentially tight lower bound under the Strong Exponential Time Hypothesis (SETH). This bound crucially relied on a large permutation submatrix within Mk, which enabled a “pattern propagation” commonly used in previous related lower bounds, as initiated by Lokshtanov et al. (SODA 2011). We present a new technique for a similar “pattern propagation” when only a black-box lower bound on the asymptotic rank of Mk is given; no stronger structural insights such as the existence of large permutation submatrices in Mk are needed. Given appropriate rank bounds, our technique yields lower bounds for counting Hamiltonian cycles (also modulo fixed primes p) parameterized by pathwidth. To apply this technique, we prove that the rank of Mk over the rationals is 4k/poly(k), using the representation theory of the symmetric group and various insights from algebraic combinatorics. We also show that the rank of Mk over ℤp is Ω(1.57k) for any prime p ≠ 2. Combining our rank bounds with the new pattern propagation technique, we show that Hamiltonian cycles cannot be counted in time O*((6 – ε)pw) for any ε > 0 unless SETH fails. This bound is tight due to a O*(6pw) time algorithm by Bodlaender et al. (ICALP 2013). Under SETH, we also obtain that Hamiltonian cycles cannot be counted modulo primes p ≠ 2 in time O*(3.57pw), indicating that the modulus can affect the complexity in intricate ways.

The Strong Exponential Time Hypothesis and the OV-conjecture are two popular hardness assumptions used to prove a plethora of lower bounds, especially in the realm of polynomial-time algorithms. The OV-conjecture in moderate dimension states there is no ε>0 for which an O(N2−ε) poly(D) time algorithm can decide whether there is a pair of orthogonal vectors in a given set of size N that contains D-dimensional binary vectors.

For an even integer t ≥ 2, the Matching Connectivity matrix H t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph on t vertices; an entry H t [ M 1 , M 2 ] is 1 if M 1 and M 2 form a Hamiltonian cycle and 0 otherwise. Motivated by applications for the Hamiltonicity problem, we show that H t has rank exactly 2 t /2−1 over GF(2). The upper bound is established by an explicit factorization of H t as the product of two submatrices; the matchings labeling columns and rows, respectively, of the submatrices therefore form a basis X t of H t . The lower bound follows because the 2 t /2−1 × 2 t /2−1 submatrix with rows and columns labeled by X t can be seen to have full rank. We obtain several algorithmic results based on the rank of H t and the particular structure of the matchings in X t . First, we present a 1.888 n n O (1) time Monte Carlo algorithm that solves the Hamiltonicity problem in directed bipartite graphs. Second, we give a Monte Carlo algorithm that solves the problem in (2 + √ 2) pw n O (1) time when provided with a path decomposition of width pw for the input graph. Moreover, we show that this algorithm is best possible under the Strong Exponential Time Hypothesis, in the sense that an algorithm with running time (2 + √2 − ϵ) pw n O (1) , for any ϵ > 0, would imply the breakthrough result of a (2 − ϵ ′ ) n -time algorithm for CNF-Sat for some ϵ ′ > 0.

We present randomized algorithms that solve subset sum and knapsack instances with $n$ items in $O^*(2^{0.86n})$ time, where the $O^*(\cdot)$ notation suppresses factors polynomial in the input size, and polynomial space, assuming random read-only access to exponentially many random bits. These results can be extended to solve binary integer programming on $n$ variables with few constraints in a similar running time. We also show that for any constant $k\geq 2$, random instances of $k$-sum can be solved using $O(n^{k-0.5}\mathrm{polylog}(n))$ time and $O(\log n)$ space, without the assumption of random access to random bits. Underlying these results is an algorithm that determines whether two given lists of length $n$ with integers bounded by a polynomial in $n$ share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using $O(\log n)$ space significantly faster than the trivial $O(n^2)$ time algorithm if no value occurs too often in the same list.

Two sets of 0–1 vectors of fixed length form a uniquely decodeable code pair if their Cartesian product is of the same size as their sumset, where the addition is pointwise over integers. For the size of the sumset of such a pair, van Tilborg has given an upper bound in the general case. Urbanke and Li, and later Ordentlich and Shayevitz, have given better bounds in the unbalanced case, that is, when either of the two sets is sufficiently large. Improvements to the latter bounds are presented.

We present randomized algorithms that solve Subset Sum and Knapsack instances with n items in O*(20.86n) time, where the O*(·) notation suppresses factors polynomial in the input size, and polynomial space, assuming random read-only access to exponentially many random bits. These results can be extended to solve Binary Linear Programming on n variables with few constraints in a similar running time. We also show that for any constant k≥ 2, random instances of k-Sum can be solved using O(nk-0.5(n)) time and O(logn) space, without the assumption of random access to random bits.

We propose a general approach to modelling algorithmic paradigms for the exact solution of NP-hard problems. Our approach is based on polynomial time reductions to succinct versions of problems solvable in polynomial time. We use this viewpoint to explore and compare the power of paradigms such as branching and dynamic programming, and to shed light on the true complexity of various problems. As one instantiation, we model branching using the notion of witness compression, i.e., reducibility to the circuit satisfiability problem parameterized by the number of variables of the circuit. We show this is equivalent to the previously studied notion of `OPP-algorithms', and provide a technique for proving conditional lower bounds for witness compressions via a constructive variant of AND-composition, which is a notion previously studied in theory of preprocessing. In the context of parameterized complexity we use this to show that problems such as Pathwidth and Treewidth and Independent Set parameterized by pathwidth do not have witness compression, assuming NP subseteq coNP/poly. Since these problems admit fast fixed parameter tractable algorithms via dynamic programming, this shows that dynamic programming can be stronger than branching, under a standard complexity hypothesis. Our approach has applications outside parameterized complexity as well: for example, we show if a polynomial time algorithm outputs a maximum independent set of a given planar graph on n vertices with probability exp(-n^{1-epsilon}) for some epsilon>0, then NP subseteq coNP/poly. This negative result dims the prospects for one very natural approach to sub-exponential time algorithms for problems on planar graphs. As two other illustrations (more exploratory) of our approach, we model algorithms based on inclusion-exclusion or group algebras via the notion of "parity compression", and we model a subclass of dynamic programming algorithms with the notion of "disjunctive dynamic programming". These models give us a way to naturally classify various parameterized problems with FPT algorithms. In the case of the dynamic programming model, we show that Independent Set parameterized by pathwidth is complete for this model.

The worst-case fastest known algorithm for the Set Cover problem on universes with $n$ elements still essentially is the simple $O^*(2^n)$-time dynamic programming algorithm, and no non-trivial consequences of an $O^*(1.01^n)$-time algorithm are known. Motivated by this chasm, we study the following natural question: Which instances of Set Cover can we solve faster than the simple dynamic programming algorithm? Specifically, we give a Monte Carlo algorithm that determines the existence of a set cover of size $σn$ in $O^*(2^{(1-Ω(σ^4))n})$ time. Our approach is also applicable to Set Cover instances with exponentially many sets: By reducing the task of finding the chromatic number $χ(G)$ of a given $n$-vertex graph $G$ to Set Cover in the natural way, we show there is an $O^*(2^{(1-Ω(σ^4))n})$-time randomized algorithm that given integer $s=σn$, outputs NO if $χ(G) > s$ and YES with constant probability if $χ(G)\leq s-1$. On a high level, our results are inspired by the `representation method' of Howgrave-Graham and Joux~[EUROCRYPT'10] and obtained by only evaluating a randomly sampled subset of the table entries of a dynamic programming algorithm.

We establish the complexity of several graph embedding problems: Subgraph Isomorphism, Graph Minor, Induced Subgraph and Induced Minor, when restricted to H-minor free graphs. In each of these problems, we are given a pattern graph P and a host graph G, and want to determine whether P is a subgraph (minor, induced subgraph or induced minor) of G. We show that, for any fixed graph H and epsilon > 0, if P is H-Minor Free and G has treewidth tw, (induced) subgraph can be solved 2^{O(k^{epsilon}*tw+k/log(k))}*n^{O(1)} time and (induced) minor can be solved in 2^{O(k^{epsilon}*tw+tw*log(tw)+k/log(k))}*n^{O(1)} time, where k = |V(P)|. We also show that this is optimal, in the sense that the existence of an algorithm for one of these problems running in 2^{o(n/log(n))} time would contradict the Exponential Time Hypothesis. This solves an open problem on the complexity of Subgraph Isomorphism for planar graphs. The key algorithmic insight is that dynamic programming approaches can be sped up by identifying isomorphic connected components in the pattern graph. This technique seems widely applicable, and it appears that there is a relatively unexplored class of problems that share a similar upper and lower bound.

Two sets A, B ⊆ {0, 1}nform a Uniquely Decodable Code Pair (UDCP) if every pair a ∈ A, b ∈ B yields a distinct sum a+b, where the addition is over ℤn. We show that every UDCP A, B, with |A| = 2(1−ε)nand |B| = 2βn, satisfies equation. For sufficiently small ε, this bound significantly improves previous bounds by Urbanke and Li [Information Theory Workshop ′98] and Ordentlich and Shayevitz [2014, arXiv:1412.8415], which upper bound β by 0.4921 and 0.4798, respectively, as ε approaches 0.

The SUBSET SUM problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O^*(2^{n/2})-time algorithm for SUBSET SUM by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", O^*(2^{(0.5-delta)*n})-time algorithm, with some constant delta > 0. Continuing an earlier work [STACS 2015], we study SUBSET SUM parameterized by the maximum bin size beta, defined as the largest number of subsets of the n input integers that yield the same sum. For every epsilon > 0 we give a truly faster algorithm for instances with beta <= 2^{(0.5-epsilon)*n}, as well as instances with beta >= 2^{0.661n}. Consequently, we also obtain a characterization in terms of the popular density parameter n/log_2(t): if all instances of density at least 1.003 admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from a novel combinatorial analysis of mixings of earlier algorithms for SUBSET SUM and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.

We investigate fast algorithms for changing between the standard basis and an orthogonal basis of idempotents for Möbius algebras of finite lattices. We show that every lattice with v elements, n of which are nonzero and join-irreducible (or, by a dual result, nonzero and meet-irreducible), has arithmetic circuits of size O ( vn ) for computing the zeta transform and its inverse, thus enabling fast multiplication in the Möbius algebra. Furthermore, the circuit construction in fact gives optimal (up to constants) monotone circuits for several lattices of combinatorial and algebraic relevance, such as the lattice of subsets of a finite set, the lattice of set partitions of a finite set, the lattice of vector subspaces of a finite vector space, and the lattice of positive divisors of a positive integer.

The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems has thrived since the mid-2000s. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, non-trivial exponential time algorithms have been found for a myriad of problems, including G raph C oloring , H amiltonian P ath , D ominating S et , and 3-CNF-S at . In some instances, improving these algorithms further seems to be out of reach. The CNF-S at problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O (2 n ), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-S at that run in time o (2 n ), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every ϵ < 1, there is a (large) integer k such that k -CNF-S at cannot be computed in time 2 ϵ n . In this article, we show that, for every ϵ < 1, the problems H itting S et , S et S plitting , and NAE-S at cannot be computed in time O (2 ϵ n ) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for S et C over and prove that, under this assumption, the fastest known algorithms for S teiner T ree , C onnected V ertex C over , S et P artitioning , and the pseudo-polynomial time algorithm for S ubset S um cannot be significantly improved. Finally, we justify our assumption about the hardness of S et C over by showing that the parity of the number of solutions to S et C over cannot be computed in time O (2 ϵ n ) for any ϵ < 1 unless SETH fails.

We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly concentrated on any particular integer value. We present a randomized algorithm that runs in O(2^0.3399nB^4) time on instances with the property that no value can arise as a sum of more than B different subsets of the n given integers.

For an even integer t ≥ 2, the Matching Connectivity matrix Ht is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph Kt on t vertices; an entry Ht[M1,M2] is 1 if M1∪ M2 is a Hamiltonian cycle and 0 otherwise. Motivated by the computational study of the Hamiltonicity problem, we present three results on the structure of Ht: We first show that Ht has rank exactly 2t/2-1 over GF(2) via an appropriate factorization that explicitly provides families of matchings Xt forming bases for Ht. Second, we show how to quickly change representation between such bases. Third, we notice that the sets of matchings Xt induce permutation matrices within Ht. We use the factorization to derive an 1.888n nO(1) time Monte Carlo algorithm that solves the Hamiltonicity problem in directed bipartite graphs. Our algorithm as well counts the number of Hamiltonian cycles modulo two in directed bipartite or undirected graphs in the same time bound. Moreover, we use the fast basis change algorithm from the second result to present a Monte Carlo algorithm that given an undirected graph on n vertices along with a path decomposition of width at most pw decides Hamiltonicity in (2+√2)pw nO(1) time. Finally, we use the third result to show that for every ε >0 this cannot be improved to (2+√2-ε)pwnO(1) time unless the Strong Exponential Time Hypothesis fails, i.e., a faster algorithm for this problem would imply the breakthrough result of an O((2-ε')n) time algorithm for CNF-Sat.

Given a graph with n vertices, k terminals and positive integer weights not larger than c, we compute a minimum Steiner Tree in $\mathcal{O}^{\star}(2^{k}c)$ time and $\mathcal{O}^{\star}(c)$ space, where the $\mathcal{O}^{\star}$ notation omits terms bounded by a polynomial in the input-size. We obtain the result by defining a generalization of walks, called branching walks, and combining it with the Inclusion-Exclusion technique. Using this combination we also give $\mathcal{O}^{\star}(2^{n})$ -time polynomial space algorithms for Degree Constrained Spanning Tree, Maximum Internal Spanning Tree and #Spanning Forest with a given number of components. Furthermore, using related techniques, we also present new polynomial space algorithms for computing the Cover Polynomial of a graph, Convex Tree Coloring and counting the number of perfect matchings of a graph.

The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, difficult and non-trivial exponential time algorithms have been found for a myriad of problems, including GRAPH COLORING, HAMILTONIAN PATH, DOMINATING SET and 3-CNF-SAT. In some instances, improving these algorithms further seems to be out of reach. The CNF-SAT problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O(2n), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-SAT that run in time o(2n), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every ϵϵn. In this paper, we show that, for every ϵϵn) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for SET COVER, and prove that, under this assumption, the fastest known algorithms for STEINTER TREE, CONNECTED VERTEX COVER, SET PARTITIONING, and the pseudo-polynomial time algorithm for SUBSET SUM cannot be significantly improved. Finally, we justify our assumption about the hardness of SET COVER by showing that the parity of the number of set covers.

We investigate fast algorithms for changing between the standard basis and an orthogonal basis of idempotents for Möbius algebras of finite lattices. We show that every lattice with v elements, n of which are nonzero and join-irreducible (or, by a dual result, nonzero and meet-irreducible), has arithmetic circuits of size O(vn) for computing the zeta transform and its inverse, thus enabling fast multiplication in the Möbius algebra. Furthermore, the circuit construction in fact gives optimal (up to constants) circuits for a number of lattices of combinatorial and algebraic relevance, such as the lattice of subsets of a finite set, the lattice of set partitions of a finite set, the lattice of vector subspaces of a finite vector space, and the lattice of positive divisors of a positive integer.

The problem of determining the cutwidth of a graph is a notoriously hard problem which remains NP-complete under severe restrictions on input graphs. Until recently, nontrivial polynomial-time cutwidth algorithms were known only for subclasses of graphs of bounded treewidth. Very recently, Heggernes et al. (SIAM J. Discrete Math., 25 (2011), pp. 1418--1437) initiated the study of cutwidth on graph classes containing graphs of unbounded treewidth and showed that a greedy algorithm computes the cutwidth of threshold graphs. We continue this line of research and present the first polynomial-time algorithm for computing the cutwidth of bipartite permutation graphs. Our algorithm runs in linear time. We stress that the cutwidth problem is NP-complete on bipartite graphs and its computational complexity is open even on small subclasses of permutation graphs, such as trivially perfect graphs.

For the vast majority of local problems on graphs of small tree width (where by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give c^tw |V|^O(1) time algorithms, where tw is the tree width of the input graph G = (V, E) and c is a constant. On the other hand, for problems with a global requirement (usually connectivity) the best -- known algorithms were naive dynamic programming schemes running in at least tw^tw time. We breach this gap by introducing a technique we named Cut&Count that allows to produce c^tw |V|^O(1) time Monte Carlo algorithms for most connectivity-type problems, including Hamiltonian Path, Steiner Tree, Feedback Vertex Set and Connected Dominating Set. These results have numerous consequences in various fields, like parameterized complexity, exact and approximate algorithms on planar and H-minor-free graphs and exact algorithms on graphs of bounded degree. The constant c in our algorithms is in all cases small, and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. In contrast to the problems aiming to minimize the number of connected components that we solve using Cut&Count as mentioned above, we show that, assuming the Exponential Time Hypothesis, the aforementioned gap cannot be breached for some problems that aim to maximize the number of connected components like Cycle Packing.

The Subset Sum and Knapsack problems are fundamental NP-complete problems and the pseudo-polynomial time dynamic programming algorithms for them appear in every algorithms textbook. The algorithms require pseudo-polynomial time and space. Since we do not expect polynomial time algorithms for Subset Sum and Knapsack to exist, a very natural question is whether they can be solved in pseudo-polynomial time and polynomial space. In this paper we answer this question affirmatively, and give the first pseudo-polynomial time, polynomial space algorithms for these problems.