| 21. |
- Björklund, Andreas, et al.
(författare)
-
Fourier meets Möbius: fast subset convolution
- 2007
-
Ingår i: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. - New York, NY, USA : ACM. - 9781595936318 ; , s. 67-74
-
Konferensbidrag (refereegranskat)abstract
- We present a fast algorithm for the subset convolution problem:given functions f and g defined on the lattice of subsets of ann-element set n, compute their subset convolution f*g, defined for S⊆ N by [ (f * g)(S) = [T ⊆ S] f(T) g(S/T),,]where addition and multiplication is carried out in an arbitrary ring. Via Möbius transform and inversion, our algorithm evaluates the subset convolution in O(n2 2n) additions and multiplications, substanti y improving upon the straightforward O(3n) algorithm. Specifically, if the input functions have aninteger range [-M,-M+1,...,M], their subset convolution over the ordinary sum--product ring can be computed in Õ(2n log M) time; the notation Õ suppresses polylogarithmic factors.Furthermore, using a standard embedding technique we can compute the subset convolution over the max--sum or min--sum semiring in Õ(2n M) time. To demonstrate the applicability of fast subset convolution, wepresent the first Õ(2k n2 + n m) algorithm for the Steiner tree problem in graphs with n vertices, k terminals, and m edges with bounded integer weights, improving upon the Õ(3kn + 2k n2 + n m) time bound of the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent Õ(2n)-time algorithms for covering and partitioning problems (Björklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006).
|
|
| 22. |
- Björklund, Andreas, et al.
(författare)
-
Inclusion-exclusion algorithms for counting set partitions
- 2006
-
Ingår i: 2006 47th Annual IEEE Conference on Foundations of Computer Science. - 0769527205 ; , s. 575-582
-
Konferensbidrag (refereegranskat)abstract
- Given a set U with n elements and a family of subsets S ⊆ 2U we show how to count the number of k-partitions S1 ∪ ... ∪ Sk = U into subsets Si ∈ S in time 2nnO(1). The only assumption on S is that it can be enumerated in time 2nnO(1). In effect we get exact algorithms in time 2nnO(1) for several well-studied partition problems including domatic number, chromatic number, bounded component spanning forest, partition into Hamiltonian subgraphs, and bin packing. If only polynomial space is available, our algorithms run in time 3nnO(1) if membership in S can be decided in polynomial time. For chromatic number, we present a version that runs in time O(2.2461n) and polynomial space. For domatic number, we present a version that runs in time O(2.8718n). Finally, we present a family of polynomial space approximation algorithms that find a number between χ(G) and [(1 + ϵ)χ(G)] in time O(1.2209n + 2.2461e-ϵn)
|
|
| 23. |
- Björklund, Andreas, et al.
(författare)
-
Listing Triangles
- 2014
-
Ingår i: Automata, Languages, and Programming (Lecture notes in computer science). - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783662439487 ; 8572, s. 223-234
-
Konferensbidrag (refereegranskat)abstract
- We present new algorithms for listing triangles in dense and sparse graphs. The running time of our algorithm for dense graphs is O~(n^ω+n^3(ω−1)/(5−ω)t^2(3−ω)/(5−ω)), and the running time of the algorithm for sparse graphs is O~(m^2ω/(ω+1)+m^3(ω−1)/(ω+1)t^(3−ω)/(ω+1)), where n is the number of vertices, m is the number of edges, t is the number of triangles to be listed, and ω < 2.373 is the exponent of fast matrix multiplication. With the current bound on ω, the running times of our algorithms are O~(n^2.373+n^1.568t^0.478) and O~(m^1.408+m^1.222t^0.186), respectively. We first obtain randomized algorithms with the desired running times and then derandomize them using sparse recovery techniques. If ω = 2, the running times of the algorithms become O~(n^2+nt^2/3) and O~(m^4/3+mt^1/3), respectively. In particular, if ω = 2, our algorithm lists m triangles in O~(m4/3) time. Pǎtraşcu (STOC 2010) showed that Ω(m^(4/3 − o(1))) time is required for listing m triangles, unless there exist subquadratic algorithms for 3SUM. We show that unless one can solve quadratic equation systems over a finite field significantly faster than the brute force algorithm, our triangle listing runtime bounds are tight assuming ω = 2, also for graphs with more triangles.
|
|
| 24. |
- Björklund, Andreas, et al.
(författare)
-
Narrow sieves for parameterized paths and packings
- 2017
-
Ingår i: Journal of Computer and System Sciences. - : Elsevier BV. - 0022-0000. ; 87, s. 119-139
-
Tidskriftsartikel (refereegranskat)abstract
- We present parameterized algorithms for the k-path problem, the p-packing of q-sets problem, and the q-dimensional p-matching problem. Our algorithms solve these problems with high probability in time exponential only in the parameter (k, p, q) and using polynomial space. The constant bases of the exponentials are significantly smaller than in previous works; for example, for the k-path problem the improvement is from 2 to 1.66. We also show how to detect if a d-regular graph admits an edge coloring with d colors in time within a polynomial factor of 2(d-1)n/2. Our techniques generalize an algebraic approach studied in various recent works.
|
|
| 25. |
- Björklund, Andreas, et al.
(författare)
-
Set partitioning via inclusion-exclusion
- 2009
-
Ingår i: SIAM Journal on Computing. - : Society for Industrial & Applied Mathematics (SIAM). - 0097-5397 .- 1095-7111. ; 39:2, s. 546-563
-
Tidskriftsartikel (refereegranskat)abstract
- Given a set N with n elements and a family F of subsets, we show how to partition N into k such subsets in 2(n) n(O)(1) time. We also consider variations of this problem where the subsets may overlap or are weighted, and we solve the decision, counting, summation, and optimization versions of these problems. Our algorithms are based on the principle of inclusion-exclusion and the zeta transform. In effect we get exact algorithms in 2(n) n(O)(1) time for several well-studied partition problems including domatic number, chromatic number, maximum k-cut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to model-based data clustering. If only polynomial space is available, our algorithms run in time 3(n) n(O)(1) if membership in F can be decided in polynomial time. We solve chromatic number in O(2.2461(n)) time and domatic number in O(2.8718(n)) time. Finally, we present a family of polynomial space approximation algorithms that find a number between chi(G) and inverted right perpendicular(1 + epsilon)chi(G)inverted left perpendicular in time O(1.2209(n) + 2.2461(e-epsilon n)).
|
|
| 26. |
- Björklund, Andreas, et al.
(författare)
-
Shortest cycle through specified elements
- 2012
-
Ingår i: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. ; , s. 1747-1747
-
Konferensbidrag (refereegranskat)
|
|
| 27. |
- Björklund, Andreas, et al.
(författare)
-
Shortest two disjoint paths in polynomial time
- 2019
-
Ingår i: SIAM Journal on Computing. - 0097-5397. ; 48:6, s. 1698-1710
-
Tidskriftsartikel (refereegranskat)abstract
- Given an undirected graph and two pairs of vertices (si, ti) for i ϵ{ 1, 2} we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining si and ti for i ϵ{1, 2}, respectively, or concludes that there most likely are no such paths at all. Our algorithm applies to both the vertex- and edge-disjoint versions of the problem. Our algorithm is algebraic and uses permanents over the polynomial ring Z4[X] in combination with the isolation lemma of Mulmuley, Vazirani, and Vazirani to detect a solution. To this end, we develop a fast algorithm for permanents over the ring Zt[X], where t is a power of 2, by modifying Valiant's 1979 algorithm for the permanent over Zt
|
|
| 28. |
- Björklund, Andreas, et al.
(författare)
-
The Parity of Directed Hamiltonian Cycles
- 2013
-
Ingår i: Annual IEEE Symposium on Foundations of Computer Science. - 0272-5428. ; , s. 727-735
-
Konferensbidrag (refereegranskat)abstract
- We present a deterministic algorithm that given any directed graph on n vertices computes the parity of its number of Hamiltonian cycles in O(1.619n) time and polynomial space. For bipartite graphs, we give a 1.5npoly(n) expected time algorithm. Our algorithms are based on a new combinatorial formula for the number of Hamiltonian cycles modulo a positive integer.
|
|
| 29. |
|
|
| 30. |
- Björklund, Andreas, et al.
(författare)
-
The shortest even cycle problem is tractable
- 2022
-
Ingår i: STOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. - New York, NY, USA : ACM. - 0737-8017. - 9781450392648 ; , s. 117-130
-
Konferensbidrag (refereegranskat)abstract
- Given a directed graph as input, we show how to efficiently find a shortest (directed, simple) cycle on an even number of vertices. As far as we know, no polynomial-time algorithm was previously known for this problem. In fact, finding any even cycle in a directed graph in polynomial time was open for more than two decades until Robertson, Seymour, and Thomas (Ann. of Math. (2) 1999) and, independently, McCuaig (Electron. J. Combin. 2004; announced jointly at STOC 1997) gave an efficiently testable structural characterisation of even-cycle-free directed graphs. Methodologically, our algorithm relies on the standard framework of algebraic fingerprinting and randomized polynomial identity testing over a finite field, and in fact relies on a generating polynomial implicit in a paper of Vazirani and Yannakakis (Discrete Appl. Math. 1989) that enumerates weighted cycle covers by the parity of their number of cycles as a difference of a permanent and a determinant polynomial. The need to work with the permanent-known to be #P-hard apart from a very restricted choice of coefficient rings (Valiant, Theoret. Comput. Sci. 1979)-is where our main technical contribution occurs. We design a family of finite commutative rings of characteristic 4 that simultaneously (i) give a nondegenerate representation for the generating polynomial identity via the permanent and the determinant, (ii) support efficient permanent computations by extension of Valiant's techniques, and (iii) enable emulation of finite-field arithmetic in characteristic 2. Here our work is foreshadowed by that of Björklund and Husfeldt (SIAM J. Comput. 2019), who used a considerably less efficient commutative ring design-in particular, one lacking finite-field emulation-to obtain a polynomial-time algorithm for the shortest two disjoint paths problem in undirected graphs. Building on work of Gilbert and Tarjan (Numer. Math. 1978) as well as Alon and Yuster (J. ACM 2013), we also show how ideas from the nested dissection technique for solving linear equation systems-introduced by George (SIAM J. Numer. Anal. 1973) for symmetric positive definite real matrices-leads to faster algorithm designs in our present finite-ring randomized context when we have control on the separator structure of the input graph; for example, this happens when the input has bounded genus.
|
|
