• We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the input graph. We prove that unless the Exponential Time Hypothesis fails, the problem cannot be solved in time $2^{o(t\log t)}\cdot n^{\mathcal{O}(1)}$ on general directed graphs, where $t$ is the treewidth of the underlying undirected graph. This is matched by a dynamic programming algorithm with running time $2^{\mathcal{O}(t\log t)}\cdot n^{\mathcal{O}(1)}$. On the other hand, we show that if the input digraph is planar, then the running time can be improved to $2^{\mathcal{O}(t)}\cdot n^{\mathcal{O}(1)}$.
  • For even $k$, the matchings connectivity matrix $M_k$ is a binary matrix indexed by perfect matchings of the complete $k$-vertex graph; the entry at a pair of matchings is $1$ iff their union forms a single cycle. Previous work has found connections between the asymptotic rank of $M_k$ and the complexity of the Hamiltonian Cycle problem: Cygan et al. (STOC 2013) showed that the rank of $M_k$ over $\mathbb Z_2$ is $\Theta(\sqrt 2^k)$ and used this to give an $O^*((2+\sqrt{2})^{\mathsf{pw}})$ time algorithm for counting Hamiltonian cycles modulo $2$ on graphs of pathwidth $\mathsf{pw}$. The same authors complemented their algorithm by an essentially tight lower bound under SETH. This bound crucially relied on a large permutation submatrix within $M_k$, which enabled a "pattern propagation" technique. We present a new technique to simulate a similar "pattern propagation" when only a black-box lower bound on the asymptotic rank of $M_k$ is given. 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 $M_k$ over $\mathbb Q$ is $4^k / \mathrm{poly}(k)$, using the representation theory of the symmetric group and insights from algebraic combinatorics. We also show that the rank of $M_k$ over $\mathbb Z_p$ is $\Omega(1.56^k)$ for any prime $p\neq 2$. As a consequence, we obtain that Hamiltonian cycles cannot be counted in time $O^*((6-\epsilon)^{\mathsf{pw}})$ for any $\epsilon>0$ unless SETH fails, which is tight due to an algorithm by Bodlaender et al. (ICALP 2013). We also obtain that Hamiltonian cycles cannot be counted modulo primes $p\neq 2$ in time $O^*(3.56^\mathsf{pw})$, in contrast to the $O^*((2+\sqrt{2})^{\mathsf{pw}})=O^*(3.42^{\mathsf{pw}})$ time algorithm for counting mod $2$ by Cygan et al. (STOC 2013).
  • In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and a parameter $\alpha>1$, and the goal is to design an $\alpha$-approximation algorithm with the fastest possible running time. We show the following results: - An $r$-approximation for maximum independent set in $O^*(\exp(\tilde O(n/r \log^2 r+r\log^2r)))$ time, - An $r$-approximation for chromatic number in $O^*(\exp(\tilde{O}(n/r \log r+r\log^2r)))$ time, - A $(2-1/r)$-approximation for minimum vertex cover in $O^*(\exp(n/r^{\Omega(r)}))$ time, and - A $(k-1/r)$-approximation for minimum $k$-hypergraph vertex cover in $O^*(\exp(n/(kr)^{\Omega(kr)}))$ time. (Throughout, $\tilde O$ and $O^*$ omit $\mathrm{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. 2009, 2011 & Cygan et al. 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., 2013 & Laekhanukit, 2014 (Ph.D. Thesis)]. Our results show that the naturally-looking $O^*(2^{n/r})$ bounds are not tight for all these problems. The key to these algorithmic results is a sparsification procedure, allowing the use of better approximation algorithms for bounded degree graphs. For obtaining 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, 2016]. It also implies that a (significant) improvement over our result will refute the gap-ETH conjecture [Dinur 2016 & Manurangsi and Raghavendra, 2016].
  • 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,\dotsc,r_k)$ and to serve it, we need to move some server $s_i$ to the point $r_i \in 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 $O(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 present space efficient Monte Carlo algorithms that solve Subset Sum and Knapsack instances with $n$ items using $O^*(2^{0.86n})$ time and polynomial space, where the $O^*(\cdot)$ notation suppresses factors polynomial in the input size. Both algorithms assume random read-only access to random bits. Modulo this mild assumption, this resolves a long-standing open problem in exact algorithms for NP-hard problems. 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\geq 2$, random instances of $k$-Sum can be solved using $O(n^{k-0.5}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.
  • 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 $\sigma n$ in $O^*(2^{(1-\Omega(\sigma^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 $\chi(G)$ of a given $n$-vertex graph $G$ to Set Cover in the natural way, we show there is an $O^*(2^{(1-\Omega(\sigma^4))n})$-time randomized algorithm that given integer $s=\sigma n$, outputs NO if $\chi(G) > s$ and YES with constant probability if $\chi(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.
  • The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path Decomposition (MSPD) problems ask for a given n-vertex graph G and integer k, what is the minimum number of bags of a tree decomposition (respectively, path decomposition) of G of width at most k. The problems are known to be NP-complete for each fixed $k\geq 4$. We present algorithms that solve both problems for fixed k in $2^{O(n/ \log n)}$ time and show that they cannot be solved in $2^{o(n / \log n)}$ time, assuming the Exponential Time Hypothesis.
  • Two sets $A, B \subseteq \{0, 1\}^n$ form a Uniquely Decodable Code Pair (UDCP) if every pair $a \in A$, $b \in B$ yields a distinct sum $a+b$, where the addition is over $\mathbb{Z}^n$. We show that every UDCP $A, B$, with $|A| = 2^{(1-\epsilon)n}$ and $|B| = 2^{\beta n}$, satisfies $\beta \leq 0.4228 +\sqrt{\epsilon}$. For sufficiently small $\epsilon$, 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 $\beta$ by $0.4921$ and $0.4798$, respectively, as $\epsilon$ approaches $0$.
  • In the subset sum problem we are given n positive integers along with a target integer t. A solution is a subset of these integers summing to t. In this short note we show that for a given subset sum instance there is a proof of size $O^*(\sqrt{t})$ of what the number of solutions is that can be constructed in $O^*(t)$ time and can be probabilistically verified in time $O^*(\sqrt{t})$ with at most constant error probability. Here, the $O^*()$ notation omits factors polynomial in the input size $n\log(t)$.
  • 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 \leq 2^{(0.5-\epsilon)n}$, as well as instances with $\beta \geq 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 novel combinations 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.
  • 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(2^n), 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(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 epsilon<1, there is a (large) integer k such that that k-CNF-Sat cannot be computed in time 2^{epsilon n}. In this paper, we show that, for every epsilon < 1, the problems Hitting Set, Set Splitting, and NAE-Sat cannot be computed in time O(2^{epsilon 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 cannot be computed in time O(2^{epsilon n}) for any epsilon<1 unless SETH fails.
  • A multicast game is a network design game modelling how selfish non-cooperative agents build and maintain one-to-many network communication. There is a special source node and a collection of agents located at corresponding terminals. Each agent is interested in selecting a route from the special source to its terminal minimizing the cost. The mutual influence of the agents is determined by a cost sharing mechanism, which evenly splits the cost of an edge among all the agents using it for routing. In this paper we provide several algorithmic and complexity results on finding a Nash equilibrium minimizing the value of Rosenthal potential. Let n be the number of agents and G be the communication network. We show that - For a given strategy profile s and integer k>=1, there is a local search algorithm which in time n^{O(k)}|G|^{O(1)} finds a better strategy profile, if there is any, in a k-exchange neighbourhood of s. In other words, the algorithm decides if Rosenthal potential can be decreased by changing strategies of at most k agents; - The running time of our local search algorithm is essentially tight: unless FPT= W[1], for any function f(k), searching of the k-neighbourhood cannot be done in time f(k)|G|^{O(1)}. The key ingredient of our algorithmic result is a subroutine that finds an equilibrium with minimum potential in 3^n|G|^{O(1)} time. In other words, finding an equilibrium with minimum potential is fixed-parameter tractable when parameterized by the number of agents.
  • Dynamic programming on tree decompositions is a frequently used approach to solve otherwise intractable problems on instances of small treewidth. In recent work by Bodlaender et al., it was shown that for many connectivity problems, there exist algorithms that use time, linear in the number of vertices, and single exponential in the width of the tree decomposition that is used. The central idea is that it suffices to compute representative sets, and these can be computed efficiently with help of Gaussian elimination. In this paper, we give an experimental evaluation of this technique for the Steiner Tree problem. A comparison of the classic dynamic programming algorithm and the improved dynamic programming algorithm that employs the table reduction shows that the new approach gives significant improvements on the running time of the algorithm and the size of the tables computed by the dynamic programming algorithm, and thus that the rank based approach from Bodlaender et al. does not only give significant theoretical improvements but also is a viable approach in a practical setting, and showcases the potential of exploiting the idea of representative sets for speeding up dynamic programming algorithms.
  • It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in 2^{O(tw)}|V|^{O(1)} time for graphs G=(V,E) with a given tree decomposition of width tw. However, for nonlocal problems, like the fundamental class of connectivity problems, for a long time we did not know how to do this faster than tw^{O(tw)}|V|^{O(1)}. Recently, Cygan et al. (FOCS 2011) presented Monte Carlo algorithms for a wide range of connectivity problems running in time $c^{tw}|V|^{O(1)} for a small constant c, e.g., for Hamiltonian Cycle and Steiner tree. Naturally, this raises the question whether randomization is necessary to achieve this runtime; furthermore, it is desirable to also solve counting and weighted versions (the latter without incurring a pseudo-polynomial cost in terms of the weights). We present two new approaches rooted in linear algebra, based on matrix rank and determinants, which provide deterministic c^{tw}|V|^{O(1)} time algorithms, also for weighted and counting versions. For example, in this time we can solve the traveling salesman problem or count the number of Hamiltonian cycles. The rank-based ideas provide a rather general approach for speeding up even straightforward dynamic programming formulations by identifying "small" sets of representative partial solutions; we focus on the case of expressing connectivity via sets of partitions, but the essential ideas should have further applications. The determinant-based approach uses the matrix tree theorem for deriving closed formulas for counting versions of connectivity problems; we show how to evaluate those formulas via dynamic programming.
  • For an even integer t \geq 2, the Matchings Connecivity matrix H_t is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph K_t on t vertices; an entry H_t[M_1,M_2] is 1 if M_1\cup M_2 is a Hamiltonian cycle and 0 otherwise. Motivated by the computational study of the Hamiltonicity problem, we present three results on the structure of H_t: We first show that H_t has rank at most 2^{t/2-1} over GF(2) via an appropriate factorization that explicitly provides families of matchings X_t forming bases for H_t. Second, we show how to quickly change representation between such bases. Third, we notice that the sets of matchings X_t induce permutation matrices within H_t. Subsequently, we use the factorization to obtain an 1.888^n n^{O(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+\sqrt{2})^{pw}n^{O(1)} time. Finally, we use the third result to show that for every \epsilon >0 this cannot be improved to (2+\sqrt{2}-\epsilon)^{pw}n^{O(1)} time unless the Strong Exponential Time Hypothesis fails, i.e., a faster algorithm for this problem would imply the breakthrough result of a (2-\epsilon)^n time algorithm for CNF-Sat.
  • Many combinatorial problems involving weights can be formulated as a so-called ranged problem. That is, their input consists of a universe $U$, a (succinctly-represented) set family $\mathcal{F} \subseteq 2^{U}$, a weight function $\omega:U \rightarrow \{1,...,N\}$, and integers $0 \leq l \leq u \leq \infty$. Then the problem is to decide whether there is an $X \in \mathcal{F}$ such that $l \leq \sum_{e \in X}\omega(e) \leq u$. Well-known examples of such problems include Knapsack, Subset Sum, Maximum Matching, and Traveling Salesman. In this paper, we develop a generic method to transform a ranged problem into an exact problem (i.e. a ranged problem for which $l=u$). We show that our method has several intriguing applications in exact exponential algorithms and parameterized complexity, namely: - In exact exponential algorithms, we present new insight into whether Subset Sum and Knapsack have efficient algorithms in both time and space. In particular, we show that the time and space complexity of Subset Sum and Knapsack are equivalent up to a small polynomial factor in the input size. We also give an algorithm that solves sparse instances of Knapsack efficiently in terms of space and time. - In parameterized complexity, we present the first kernelization results on weighted variants of several well-known problems. In particular, we show that weighted variants of Vertex Cover, Dominating Set, Traveling Salesman and Knapsack all admit polynomial randomized Turing kernels when parameterized by $|U|$. Curiously, our method relies on a technique more commonly found in approximation algorithms.
  • We study classes of Dynamic Programming (DP) algorithms which, due to their algebraic definitions, are closely related to coefficient extraction methods. DP algorithms can easily be modified to exploit sparseness in the DP table through memorization. Coefficient extraction techniques on the other hand are both space-efficient and parallelisable, but no tools have been available to exploit sparseness. We investigate the systematic use of homomorphic hash functions to combine the best of these methods and obtain improved space-efficient algorithms for problems including LINEAR SAT, SET PARTITION, and SUBSET SUM. Our algorithms run in time proportional to the number of nonzero entries of the last segment of the DP table, which presents a strict improvement over sparse DP. The last property also gives an improved algorithm for CNF SAT with sparse projections.
  • For the vast majority of local graph problems standard dynamic programming techniques give c^tw V^O(1) algorithms, where tw is the treewidth of the input graph. On the other hand, for problems with a global requirement (usually connectivity) the best-known algorithms were naive dynamic programming schemes running in tw^O(tw) V^O(1) time. We breach this gap by introducing a technique we dubbed Cut&Count that allows to produce c^tw V^O(1) Monte Carlo algorithms for most connectivity-type problems, including Hamiltonian Path, Feedback Vertex Set and Connected Dominating Set, consequently answering the question raised by Lokshtanov, Marx and Saurabh [SODA'11] in a surprising way. We also show that (under reasonable complexity assumptions) the gap cannot be breached for some problems for which Cut&Count does not work, like CYCLE PACKING. The constant c we obtain is in all cases small (at most 4 for undirected problems and at most 6 for directed ones), and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. Our results have numerous consequences in various fields, like FPT algorithms, exact and approximate algorithms on planar and H-minor-free graphs and algorithms on graphs of bounded degree. In all these fields we are able to improve the best-known results for some problems.