| 1. |
- Bjorklund, Andreas, et al.
(författare)
-
Fast Zeta Transforms for Lattices with Few Irreducibles
- 2016
-
Ingår i: ACM Transactions on Algorithms. - : Association for Computing Machinery (ACM). - 1549-6325 .- 1549-6333. ; 12:1
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate fast algorithms for changing between the standard basis and an orthogonal basis of idempotents for Mobius 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 Mobius 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.
|
|
| 2. |
- Björklund, Andreas, et al.
(författare)
-
Computing the permanent modulo a prime power
- 2017
-
Ingår i: Information Processing Letters. - : Elsevier BV. - 0020-0190. ; 125, s. 20-25
-
Tidskriftsartikel (refereegranskat)abstract
- We sPRThow how to compute the permanent of an n×n integer matrix modulo pk in time nk+O(1) if p=2 and in time 2n/exp{Ω(γ2n/plogp)} if p is an odd prime with kp0 we can compute the permanent of an n×n integer matrix in time 2n/exp{Ω(δ2n/β1/(1−δ)logβ)}, provided there exists a real number β such that |perA|≤βn and β≤(144δn)1−δ.
|
|
| 3. |
- Björklund, Andreas, et al.
(författare)
-
Counting Connected Subgraphs with Maximum-Degree-Aware Sieving
- 2018
-
Ingår i: 29th International Symposium on Algorithms and Computation (ISAAC 2018). - 9783959770941 ; , s. 1-17
-
Konferensbidrag (refereegranskat)abstract
- We study the problem of counting the isomorphic occurrences of a k-vertex pattern graph P as a subgraph in an n-vertex host graph G. Our specific interest is on algorithms for subgraph counting that are sensitive to the maximum degree Delta of the host graph. Assuming that the pattern graph P is connected and admits a vertex balancer of size b, we present an algorithm that counts the occurrences of P in G in O ((2 Delta-2)^{(k+b)/2} 2^{-b} n/(Delta) k^2 log n) time. We define a balancer as a vertex separator of P that can be represented as an intersection of two equal-size vertex subsets, the union of which is the vertex set of P, and both of which induce connected subgraphs of P. A corollary of our main result is that we can count the number of k-vertex paths in an n-vertex graph in O((2 Delta-2)^{floor[k/2]} n k^2 log n) time, which for all moderately dense graphs with Delta <= n^{1/3} improves on the recent breakthrough work of Curticapean, Dell, and Marx [STOC 2017], who show how to count the isomorphic occurrences of a q-edge pattern graph as a subgraph in an n-vertex host graph in time O(q^q n^{0.17q}) for all large enough q. Another recent result of Brand, Dell, and Husfeldt [STOC 2018] shows that k-vertex paths in a bounded-degree graph can be approximately counted in O(4^kn) time. Our result shows that the exact count can be recovered at least as fast for Delta<10. Our algorithm is based on the principle of inclusion and exclusion, and can be viewed as a sparsity-sensitive version of the "counting in halves"-approach explored by Björklund, Husfeldt, Kaski, and Koivisto [ESA 2009].
|
|
| 4. |
- Björklund, Andreas, et al.
(författare)
-
Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm
- 2018
-
Ingår i: 29th International Symposium on Algorithms and Computation (ISAAC 2018). - 9783959770941 ; , s. 1-19
-
Konferensbidrag (refereegranskat)abstract
- Given an undirected graph and two disjoint vertex pairs s_1,t_1 and s_2,t_2, the Shortest two disjoint paths problem (S2DP) asks for the minimum total length of two vertex disjoint paths connecting s_1 with t_1, and s_2 with t_2, respectively. We show that for cubic planar graphs there are NC algorithms, uniform circuits of polynomial size and polylogarithmic depth, that compute the S2DP and moreover also output the number of such minimum length path pairs. Previously, to the best of our knowledge, no deterministic polynomial time algorithm was known for S2DP in cubic planar graphs with arbitrary placement of the terminals. In contrast, the randomized polynomial time algorithm by Björklund and Husfeldt, ICALP 2014, for general graphs is much slower, is serial in nature, and cannot count the solutions. Our results are built on an approach by Hirai and Namba, Algorithmica 2017, for a generalisation of S2DP, and fast algorithms for counting perfect matchings in planar graphs.
|
|
| 5. |
- 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.
|
|
| 6. |
- 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
|
|
| 7. |
|
|
| 8. |
- Brand, Cornelius, et al.
(författare)
-
Extensor-Coding
- 2018
-
Ingår i: STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. - New York, NY, USA : ACM. - 9781450355599 ; , s. 535-544
-
Konferensbidrag (refereegranskat)abstract
- We devise an algorithm that approximately computes the number of paths of length k in a given directed graph with n vertices up to a multiplicative error of 1 ± . Our algorithm runs in time −24k(n + m) poly(k). The algorithm is based on associating with each vertex an element in the exterior (or, Grassmann) algebra, called an extensor, and then performing computations in this algebra. This connection to exterior algebra generalizes a number of previous approaches for the longest path problem and is of independent conceptual interest. Using this approach, we also obtain a deterministic 2k · poly(n) time algorithm to find a k-path in a given directed graph that is promised to have few of them. Our results and techniques generalize to the subgraph isomorphism problem when the subgraphs we are looking for have bounded pathwidth. Finally, we also obtain a randomized algorithm to detect k-multilinear terms in a multivariate polynomial given as a general algebraic circuit. To the best of our knowledge, this was previously only known for algebraic circuits not involving negative constants.
|
|
| 9. |
- Bringmann, Karl, et al.
(författare)
-
Multivariate Analysis of Orthogonal Range Searching and Graph Distances
- 2019
-
Ingår i: 13th International Symposium on Parameterized and Exact Computation, IPEC 2018 : August 20-24, 2018, Helsinki, Finland - August 20-24, 2018, Helsinki, Finland. - 9783959770842 ; 115, s. 1-13
-
Konferensbidrag (refereegranskat)abstract
- We show that the eccentricities, diameter, radius, and Wiener index of an undirected n-vertex graph with nonnegative edge lengths can be computed in time O(n * binom{k+ceil[log n]}{k} * 2^k k^2 log n), where k is the treewidth of the graph. For every epsilon>0, this bound is n^{1+epsilon}exp O(k), which matches a hardness result of Abboud, Vassilevska Williams, and Wang (SODA 2015) and closes an open problem in the multivariate analysis of polynomial-time computation. To this end, we show that the analysis of an algorithm of Cabello and Knauer (Comp. Geom., 2009) in the regime of non-constant treewidth can be improved by revisiting the analysis of orthogonal range searching, improving bounds of the form log^d n to binom{d+ceil[log n]}{d}, as originally observed by Monier (J. Alg. 1980). We also investigate the parameterization by vertex cover number.
|
|
| 10. |
- Husfeldt, Thore
(författare)
-
Computing Graph Distances Parameterized by Treewidth and Diameter
- 2017
-
Ingår i: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). - 9783959770231 ; 63, s. 1-11
-
Konferensbidrag (refereegranskat)abstract
- We show that the eccentricity of every vertex in an undirected graph on n vertices can be computed in time n exp O(k*log(d)), where k is the treewidth of the graph and d is the diameter. This means that the diameter and the radius of the graph can be computed in the same time. In particular, if the diameter is constant, it can be determined in time n*exp(O(k)). This result matches a recent hardness result by Abboud, Vassilevska Williams, and Wang [SODA 2016] that shows that under the Strong Exponential Time Hypothesis of Impagliazzo, Paturi, and Zane [J. Comp. Syst. Sc., 2001], for any epsilon > 0, no algorithm with running time n^{2-epsilon}*exp(o(k)) can distinguish between graphs with diameter 2 and 3.
|
|
