| 31. |
- Björklund, Andreas, et al.
(författare)
-
The Traveling Salesman Problem in Bounded Degree Graphs
- 2012
-
Ingår i: ACM Transactions on Algorithms. - : Association for Computing Machinery (ACM). - 1549-6333 .- 1549-6325. ; 8:2, s. 18-18
-
Tidskriftsartikel (refereegranskat)abstract
- We show that the traveling salesman problem in bounded-degree graphs can be solved in time O((2 - epsilon)(n)), where epsilon > 0 depends only on the degree bound but not on the number of cities, n. The algorithm is a variant of the classical dynamic programming solution due to Bellman, and, independently, Held and Karp. In the case of bounded integer weights on the edges, we also give a polynomial-space algorithm with running time O(( 2 - epsilon)(n)) on bounded-degree graphs. In addition, we present an analogous analysis of Ryser's algorithm for the permanent of matrices with a bounded number of nonzero entries in each column.
|
|
| 32. |
- Björklund, Andreas, et al.
(författare)
-
The travelling salesman problem in bounded degree graphs
- 2008
-
Ingår i: Automata, Languages and Programming, part 1, Proceedings/Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783540705741 ; 5125, s. 198-209
-
Konferensbidrag (refereegranskat)abstract
- We show that the travelling salesman problem in bounded-degree graphs can be solved in tune O((2 - epsilon)(n)), where epsilon > 0 depends only on the degree bound but not on the number of cities, n. The algorithm is a variant of the classical dynamic programming solution due to Bellman, and, independently; Held and Karp. In the case of bounded integer weights on the edges, we also present a polynomial-space algorithm with running tune O((2 - epsilon)(n)) on bounded-degree graphs.
|
|
| 33. |
|
|
| 34. |
- Björklund, Andreas, et al.
(författare)
-
Trimmed moebius inversion and graphs of bounded degree
- 2008
-
Ingår i: STACS 2008: Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science. ; , s. 85-96
-
Konferensbidrag (refereegranskat)abstract
- We study ways to expedite Yates's algorithm for computing the zeta and Moebius transforms of a function defined on the subset lattice. We develop a trimmed variant of Moebius inversion that proceeds point by point, finishing the calculation at a subset before considering its supersets. For an n-element universe U and a family F of its subsets, trimmed Moebius inversion allows us to compute the number of parkings, coverings, and partitions of U with k sets from F in time within a polynomial factor (in n) of the number of supersets of the members of F. Relying on an intersection theorem of Chung et al. (1986) to bound the sizes of set families, we apply these ideas to well-studied combinatorial optimisation problems on graphs of maximum degree A. In particular, we show how to compute the Domatic Number in time within a polynomial factor of (2(Delta+1) - 2)(n/(Delta+1)) and the Chromatic Number in time within a polynomial factor of (2(Delta+1) - Delta - 1)(n/(Delta+1)) For any constant A, these bounds are 0 ((2 - epsilon)(n)) for epsilon > 0 independent of the number of vertices n.
|
|
| 35. |
- 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.
|
|
| 36. |
- 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.
|
|
| 37. |
- Bringmann, Karl, et al.
(författare)
-
Multivariate Analysis of Orthogonal Range Searching and Graph Distances
- 2020
-
Ingår i: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 82:8, s. 2292-2315
-
Tidskriftsartikel (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·(k+⌈logn⌉k)·2klogn), where k is linear in the treewidth of the graph. For every ϵ> 0 , this bound is n1 + ϵexp O(k) , which matches a hardness result of Abboud et al. (in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016. https://doi.org/10.1137/1.9781611974331.ch28) 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 (Comput Geom 42:815–824, 2009. https://doi.org/10.1016/j.comgeo.2009.02.001) in the regime of non-constant treewidth can be improved by revisiting the analysis of orthogonal range searching, improving bounds of the form log dn to (d+⌈logn⌉d), as originally observed by Monier (J Algorithms 1:60–74, 1980. https://doi.org/10.1016/0196-6774(80)90005-X). We also investigate the parameterization by vertex cover number.
|
|
| 38. |
- Curticapean, Radu, et al.
(författare)
-
Modular counting of subgraphs : Matchings, matching-splittable graphs, and paths
- 2021
-
Ingår i: 29th Annual European Symposium on Algorithms, ESA 2021. - 1868-8969. - 9783959772044 ; 204
-
Konferensbidrag (refereegranskat)abstract
- We systematically investigate the complexity of counting subgraph patterns modulo fixed integers. For example, it is known that the parity of the number of k-matchings can be determined in polynomial time by a simple reduction to the determinant. We generalize this to an nf(t,s)-time algorithm to compute modulo 2t the number of subgraph occurrences of patterns that are s vertices away from being matchings. This shows that the known polynomial-time cases of subgraph detection (Jansen and Marx, SODA 2015) carry over into the setting of counting modulo 2t. Complementing our algorithm, we also give a simple and self-contained proof that counting k-matchings modulo odd integers q is ModqW[1]-complete and prove that counting k-paths modulo 2 is ⊕W[1]-complete, answering an open question by Björklund, Dell, and Husfeldt (ICALP 2015).
|
|
| 39. |
- Dell, Holger, et al.
(författare)
-
Exponential Time Complexity of the Permanent and the Tutte Polynomial
- 2014
-
Ingår i: ACM Transactions on Algorithms. - : Association for Computing Machinery (ACM). - 1549-6333 .- 1549-6325. ; 10:4, s. 21-21
-
Tidskriftsartikel (refereegranskat)abstract
- We show conditional lower bounds for well-studied #P-hard problems: -The number of satisfying assignments of a 2-CNF formula with n variables cannot be computed in time exp(o(n)), and the same is true for computing the number of all independent sets in an n-vertex graph. -The permanent of an n x n matrix with entries 0 and 1 cannot be computed in time exp(o(n)). -The Tutte polynomial of an n-vertex multigraph cannot be computed in time exp(o(n)) at most evaluation points (x, y) in the case of multigraphs, and it cannot be computed in time exp(o(n/poly log n)) in the case of simple graphs. Our lower bounds are relative to (variants of) the Exponential Time Hypothesis (ETH), which says that the satisfiability of n-variable 3-CNF formulas cannot be decided in time exp(o(n)). We relax this hypothesis by introducing its counting version #ETH; namely, that the satisfying assignments cannot be counted in time exp(o(n)). In order to use #ETH for our lower bounds, we transfer the sparsification lemma for d-CNF formulas to the counting setting.
|
|
| 40. |
|
|
