| 1. |
- Björklund, Andreas, et al.
(författare)
-
Constrained Multilinear Detection and Generalized Graph Motifs
- 2016
-
Ingår i: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 74:2, s. 947-967
-
Tidskriftsartikel (refereegranskat)abstract
- 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 to have coefficients from a field of characteristic two. As applications of the technique, we show an O^∗(2^k)-time polynomial space algorithm for the k-sized Graph Motif problem. We also introduce a new optimization variant of the problem, called Closest Graph Motif and solve it within the same time bound. The Closest Graph Motif problem encompasses several previously studied optimization variants, like Maximum Graph Motif, Min-Substitute Graph Motif, and Min-Add Graph Motif. Finally, we provide a piece of evidence that our result might be essentially tight: the existence of an O^∗((2−ϵ)^k)-time algorithm for the Graph Motif problem implies an O((2−ϵ′)^n)-time algorithm for Set Cover.
|
|
| 2. |
- Björklund, Andreas, et al.
(författare)
-
Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time
- 2014
-
Ingår i: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. - Philadelphia, PA : Society for Industrial and Applied Mathematics. - 9781611973389 ; , s. 594-603
-
Konferensbidrag (refereegranskat)abstract
- Vassilevska and Williams (STOC 2009) showed how to count simple paths on k vertices and matchings on k/2 edges in an n-vertex graph in time n^{k/2+O(1)}. In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP 2009), and Björklund et al. (ESA 2009), via nst/2+O(1)-time algorithms for counting t-tuples of pairwise disjoint sets drawn from a given family of s-sized subsets of an n-element universe. Shortly afterwards, Alon and Gutner (TALG 2010) showed that these problems have Ω(n^{⌊st/2⌋}) and Ω(n^{⌊k/2⌋}) lower bounds when counting by color coding. Here we show that one can do better, namely, we show that the “meet-in-the-middle” exponent st/2 can be beaten and give an algorithm that counts in time n^{0.4547st+O(1)} for t a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on k vertices and pathwidth p ≪ k in an n-vertex graph in n^{0.4547k+2p+O(1)} time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound.
|
|
| 3. |
- Björklund, Andreas, et al.
(författare)
-
Counting thin subgraphs via packings faster than meet-in-the-middle time
- 2017
-
Ingår i: ACM Transactions on Algorithms. - : Association for Computing Machinery (ACM). - 1549-6325 .- 1549-6333. ; 13:4
-
Tidskriftsartikel (refereegranskat)abstract
- Vassilevska and Williams (STOC'09) showed how to count simple paths on k vertices and matchings on k/2 edges in ann-vertex graph in time nk/2+O(1). In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP'09), and Bjorklund et al. (ESA'09), via nst/2+O(1)-time algorithms for counting t-tuples of pairwise disjoint sets drawn from a given family of s-sized subsets of an n-element universe. Shortly afterwards, Alon and Gutner (TALG'10) showed that these problems have O(n st/2) and O(nk/2) lower bounds when counting by color coding. Here, we show that one can do better-we show that the "meet-in-the-middle" exponent st/2 can be beaten and give an algorithm that counts in time n0.45470382st+O(1) for t a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on k vertices and pathwidth pk in an n-vertex graph in n0.45470382k+2p+O(1) time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound. We also give improved bounds for counting t-tuples of disjoint s-sets for s = 2, 3, 4. Our algorithms use fast matrix multiplication. We show an argument that this is necessary to go below the meet-in-the-middle barrier.
|
|
| 4. |
- Björklund, Andreas, et al.
(författare)
-
Engineering Motif Search for Large Graphs
- 2015
-
Ingår i: [Host publication title missing]. - Philadelphia, PA : Society for Industrial and Applied Mathematics. ; , s. 104-118
-
Konferensbidrag (refereegranskat)abstract
- In the graph motif problem, we are given as input a vertex-colored graph H (the host graph) and a multiset of colors M (the motif). Our task is to decide whether H has a connected set of vertices whose multiset of colors agrees with M. The graph motif problem is NP-complete but known to admit parameterized algorithms that run in linear time in the size of H. We demonstrate that algorithms based on constrained multilinear sieving are viable in practice, scaling to graphs with hundreds of millions of edges as long as M remains small. Furthermore, our implementation is topology-invariant relative to the host graph H, meaning only the most crude graph parameters (number of edges and number of vertices) suffice in practice to determine the algorithm performance.
|
|
| 5. |
- Björklund, Andreas, et al.
(författare)
-
Fast Witness Extraction using a Decision Oracle
- 2014
-
Ingår i: Algorithms - ESA 2014/Lecture notes in computer science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783662447772 ; 8737, s. 149-160
-
Konferensbidrag (refereegranskat)abstract
- The gist of many (NP-)hard combinatorial problems is to decide whether a universe of n elements contains a witness consisting of k elements that match some prescribed pattern. For some of these problems there are known advanced algebra-based FPT algorithms which solve the decision problem but do not return the witness. We investigate techniques for turning such a YES/NO-decision oracle into an algorithm for extracting a single witness, with an objective to obtain practical scalability for large values of n. By relying on techniques from combinatorial group testing, we demonstrate that a witness may be extracted with O(klogn) queries to either a deterministic or a randomized set inclusion oracle with one-sided probability of error. Furthermore, we demonstrate through implementation and experiments that the algebra-based FPT algorithms are practical, in particular in the setting of the k-path problem. Also discussed are engineering issues such as optimizing finite field arithmetic.
|
|
| 6. |
- Björklund, Andreas, et al.
(författare)
-
Probably Optimal Graph Motifs
- 2013
-
Ingår i: [Host publication title missing]. - 1868-8969. ; 20, s. 20-31
-
Konferensbidrag (refereegranskat)abstract
- We show an O^*(2^k)-time polynomial space algorithm for the k-sized Graph Motif problem. We also introduce a new optimization variant of the problem, called Closest Graph Motif and solve it within the same time bound. The Closest Graph Motif problem encompasses several previously studied optimization variants, like Maximum Graph Motif, Min-Substitute, and Min-Add. Moreover, we provide a piece of evidence that our result might be essentially tight: the existence of an O^*((2-epsilon)^k)-time algorithm for the Graph Motif problem implies an ((2-epsilon')^n)-time algorithm for Set Cover.
|
|
| 7. |
- Björklund, Andreas, et al.
(författare)
-
Spotting Trees with Few Leaves
- 2015
-
Ingår i: Lecture Notes in Computer Science/Automata, Languages, and Programming. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 0302-9743 .- 1611-3349. - 9783662476727 ; 9134, s. 243-255
-
Konferensbidrag (refereegranskat)abstract
- We show two results related to the Hamiltonicity and k -Path algorithms in undirected graphs by Björklund [FOCS’10], and Björklund et al., [arXiv’10]. First, we demonstrate that the technique used can be generalized to finding some k-vertex tree with l leaves in an n-vertex undirected graph in O∗(1.657^k2^{l/2}) time. It can be applied as a subroutine to solve the k -Internal Spanning Tree (k-IST) problem in O∗(min(3.455^k,1.946^n)) time using polynomial space, improving upon previous algorithms for this problem. In particular, for the first time, we break the natural barrier of O∗(2^n). Second, we show that the iterated random bipartition employed by the algorithm can be improved whenever the host graph admits a vertex coloring with few colors; it can be an ordinary proper vertex coloring, a fractional vertex coloring, or a vector coloring. In effect, we show improved bounds for k-Path and Hamiltonicity in any graph of maximum degree Δ=4,…,12 or with vector chromatic number at most 8.
|
|
| 8. |
- Björklund, Andreas, et al.
(författare)
-
Spotting Trees with Few Leaves
- 2017
-
Ingår i: SIAM Journal on Discrete Mathematics. - 0895-4801. ; 31:2, s. 687-713
-
Tidskriftsartikel (refereegranskat)abstract
- We show two results related to finding trees and paths in graphs. First, we show that in $O^*(1.657^k2^{l/2})$ time one can either find a $k$-vertex tree with $l$ leaves in an $n$-vertex undirected graph or conclude that such a tree does not exist. Our solution can be applied as a subroutine to solve the $k$-Internal Spanning Tree problem in $O^*(min(3.455^k, 1.946^n))$ time using polynomial space, improving upon previous algorithms for this problem. In particular, for the first time we break the natural barrier of $O^*(2^n)$. Second, we show that the running time can be improved whenever the host graph admits a vertex coloring with few colors; it can be an ordinary proper vertex coloring, a fractional vertex coloring, or a vector coloring. In effect, we show improved bounds for Hamiltonicity and $k$-Path in any graph of maximum degree $\Delta=4,\ldots,12$ or with vector chromatic number at most 8. Our results extend the technique by Björklund [SIAM J. Comput., 43 (2014), pp. 280--299] and Björklund et al. [Narrow Sieves for Parameterized Paths and Packings, CoRR, arXiv:1007. 1161, 2010] to finding structures more general than paths as well as refine it to handle special classes of graphs more efficiently.Read More: http://epubs.siam.org/doi/abs/10.1137/15M1048975
|
|
