Given a set N with n elements and family $\mathcal{F}$ of subsets, we show how to partition into k such subsets in $2^n n^{O(1)}$ time. We also consider variations this problem where the may overlap or are weighted, solve decision, counting, summation, optimization versions these problems. Our algorithms based on principle inclusion-exclusion zeta transform. In effect get exact time for several well-studied problems including domatic number, chromatic maximum k-cut, bin packing, list...

We present a fast algorithm for the subset convolution problem:given functions f and g defined on lattice of subsets ann-element set n, compute their f*g, S⊆ N by [ (f * g)(S) = [T ⊆ S] f(T) g(S/T),,]where addition multiplication is carried out in an arbitrary ring. Via Möbius transform inversion, our evaluates O(n2 2n) additions multiplications, substanti y improving upon straightforward O(3n) algorithm. Specifically, if input have aninteger range [-M,-M+1,...,M], over ordinary sum--product...

We present a Monte Carlo algorithm for Hamiltonicity detection in an n-vertex undirected graph running O* (1.657 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> ) time. To the best of our knowledge, this is first superpolynomial improvement on worst case runtime problem since O*(2 bound established TSP almost fifty years ago (Bellman 1962, Held and Karp 1962). It answers part open Woeginger's 2003 survey exact algorithms NP-hard...

We present a Monte Carlo algorithm for Hamiltonicity detection in an $n$-vertex undirected graph running $O(1.657^{n})$ time. To the best of our knowledge, this is first superpolynomial improvement on worst case runtime problem since $O^*(2^n)$ bound established traveling salesman (TSP) over 50 years ago [R. Bellman, J. Assoc. Comput. Mach., 9 (1962), pp. 61--63], [M. Held and R. M. Karp, Soc. Indust. Appl. Math., 10 196--210]. ($O^*(f(n))$ suppresses polylogarithmic functions $f(n)$). It...

We introduce new and simple algorithms for the calculation of number perfect matchings complex weighted, undirected graphs with without loops. Our compact formulas hafnian loop n × matrices run in O ( 3 2 /2 ) time, are embarrassingly parallelizable and, to best our knowledge, fastest exact compute these quantities. Despite highly optimized algorithm, numerical benchmarks on Titan supercomputer up size 56 indicate that one would require 288,000 CPUs this machine about 6 weeks a 100 matrix.

The deletion–contraction algorithm is perhapsthe most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in theory, Jones polynomial an alternating link knot partition functions models Ising, Potts, Fortuin–Kasteleyn statistical physics. Prior to this work, was also fastest known general-purpose these invariants, running time roughly proportional number spanning trees input graph.Here, we give substantially faster that...

We show that the traveling salesman problem in bounded-degree graphs can be solved time O ((2-ϵ) n ), where ϵ &gt; 0 depends only on degree bound but not number of cities, . The algorithm is a variant classical dynamic programming solution due to Bellman, and, independently, Held and Karp. In case bounded integer weights edges, we also give polynomial-space with running ) graphs. addition, present an analogous analysis Ryser's for permanent matrices nonzero entries each column.

Given a set U with n elements and family of subsets S sube 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</sup> we show how to count the number k-partitions <sub xmlns:xlink="http://www.w3.org/1999/xlink">1 </sub> cup ... xmlns:xlink="http://www.w3.org/1999/xlink">k</sub> = into xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> isin in time xmlns:xlink="http://www.w3.org/1999/xlink">n</sup>...

We introduce a new algebraic sieving technique to detect constrained multilinear monomials in multivariate polynomial generating functions given by an evaluation oracle. The polynomials are assumed have coefficients from field of characteristic two. As applications the technique, we show $$O^*(2^k)$$ -time space algorithm for $$k$$ -sized Graph Motif problem. also optimization variant problem, called Closest and solve it within same time bound. problem encompasses several previously studied...

We show that there is a polynomial space algorithm counts the number of perfect matchings in an n-vertex graph O*(2n/2) ⊂ O(1.415n) time. (O*(f(n)) suppresses functions polylogarithmic f(n)). The previously fastest algorithms for problem was exponential O*(((1 + √5)/2)n) O(1.619n) time by Koivisto, and space, O(1.942n) Nederlof. Our new algorithm's runtime matches up to factors Ryser's 1963 bipartite graphs. present our more general setting computing hafnian over arbitrary ring, analogously...

We show an O^*(2^k)-time polynomial space algorithm for the k-sized Graph Motif problem. also introduce a new optimization variant of problem, called Closest and solve it within same time bound. The problem encompasses several previously studied variants, like Maximum Motif, Min-Substitute, Min-Add. Moreover, we provide piece evidence that our result might be essentially tight: existence O^*((2-epsilon)^k)-time implies ((2-epsilon')^n)-time Set Cover.

We consider the problem of finding a long, simple path in an undirected graph. present polynomial-time algorithm that finds length $\Omega\bigl((\log L/\log\log L)^2\bigr)$, where L denotes longest This establishes performance ratio O(n(log log n/log n)2) for problem, n number vertices

We give a randomized algorithm that finds shortest simple cycle through given set of k vertices or edges in an n-vertex undirected graph time 2knO(1).

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