Search Results

Documents authored by Kaski, Petteri

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.26
Another Hamiltonian Cycle in Bipartite Pfaffian Graphs

Authors: Andreas Björklund, Petteri Kaski, and Jesper Nederlof

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Finding a Hamiltonian cycle in a given graph is computationally challenging, and in general remains so even when one is further given one Hamiltonian cycle in the graph and asked to find another. In fact, no significantly faster algorithms are known for finding another Hamiltonian cycle than for finding a first one even in the setting where another Hamiltonian cycle is structurally guaranteed to exist, such as for odd-degree graphs. We identify a graph class - the bipartite Pfaffian graphs of minimum degree three - where it is NP-complete to decide whether a given graph in the class is Hamiltonian, but when presented with a Hamiltonian cycle as part of the input, another Hamiltonian cycle can be found efficiently. We prove that Thomason’s lollipop method [Ann. Discrete Math., 1978], a well-known algorithm for finding another Hamiltonian cycle, runs in a linear number of steps in cubic bipartite Pfaffian graphs. This was conjectured for cubic bipartite planar graphs by Haddadan [MSc thesis, Waterloo, 2015]; in contrast, examples are known of both cubic bipartite graphs and cubic planar graphs where the lollipop method takes exponential time. Beyond the reach of the lollipop method, we address a slightly more general graph class and present two algorithms, one running in linear-time and one operating in logarithmic space, that take as input (i) a bipartite Pfaffian graph G of minimum degree three, (ii) a Hamiltonian cycle H in G, and (iii) an edge e in H, and output at least three other Hamiltonian cycles through the edge e in G. We also present further improved algorithms for finding optimal traveling salesperson tours and counting Hamiltonian cycles in bipartite planar graphs with running times that are not achieved yet in general planar graphs. Our technique also has purely graph-theoretical consequences; for example, we show that every cubic bipartite Pfaffian graph has either zero or at least six distinct Hamiltonian cycles; the latter case is tight for the cube graph.
Cite as

Andreas Björklund, Petteri Kaski, and Jesper Nederlof. Another Hamiltonian Cycle in Bipartite Pfaffian Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 26:1-26:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2024.26,
  author =	{Bj\"{o}rklund, Andreas and Kaski, Petteri and Nederlof, Jesper},
  title =	{{Another Hamiltonian Cycle in Bipartite Pfaffian Graphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{26:1--26:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.26},
  URN =		{urn:nbn:de:0030-drops-201692},
  doi =		{10.4230/LIPIcs.ICALP.2024.26},
  annote =	{Keywords: Another Hamiltonian cycle, Pfaffian graph, planar graph, Thomason’s lollipop method}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.29
Counting Short Vector Pairs by Inner Product and Relations to the Permanent

Authors: Andreas Björklund and Petteri Kaski

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Given as input two n-element sets A, B ⊆ {0,1}^d with d = clog n ≤ (log n)²/(log log n)⁴ and a target t ∈ {0,1,…,d}, we show how to count the number of pairs (x,y) ∈ A× B with integer inner product ⟨ x,y ⟩ = t deterministically, in n²/2^{Ω(√{log nlog log n/(clog² c)})} time. This demonstrates that one can solve this problem in deterministic subquadratic time almost up to log² n dimensions, nearly matching the dimension bound of a subquadratic randomized detection algorithm of Alman and Williams [FOCS 2015]. We also show how to modify their randomized algorithm to count the pairs w.h.p., to obtain a fast randomized algorithm. Our deterministic algorithm builds on a novel technique of reconstructing a function from sum-aggregates by prime residues, or modular tomography, which can be seen as an additive analog of the Chinese Remainder Theorem. As our second contribution, we relate the fine-grained complexity of the task of counting of vector pairs by inner product to the task of computing a zero-one matrix permanent over the integers.
Cite as

Andreas Björklund and Petteri Kaski. Counting Short Vector Pairs by Inner Product and Relations to the Permanent. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 29:1-29:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2021.29,
  author =	{Bj\"{o}rklund, Andreas and Kaski, Petteri},
  title =	{{Counting Short Vector Pairs by Inner Product and Relations to the Permanent}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{29:1--29:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.29},
  URN =		{urn:nbn:de:0030-drops-140988},
  doi =		{10.4230/LIPIcs.ICALP.2021.29},
  annote =	{Keywords: additive reconstruction, Chinese Remainder Theorem, counting, inner product, modular tomography, orthogonal vectors, permanent}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.26
Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction

Authors: Andreas Björklund, Petteri Kaski, and Ryan Williams

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We consider the problem of finding solutions to systems of polynomial equations over a finite field. Lokshtanov et al. [SODA'17] recently obtained the first worst-case algorithms that beat exhaustive search for this problem. In particular for degree-d equations modulo two in n variables, they gave an O^*(2^{(1-1/(5d))n}) time algorithm, and for the special case d=2 they gave an O^*(2^{0.876n}) time algorithm. We modify their approach in a way that improves these running times to O^*(2^{(1-1/(2.7d))n}) and O^*{2^{0.804n}), respectively. In particular, our latter bound - that holds for all systems of quadratic equations modulo 2 - comes close to the O^*(2^{0.792n}) expected time bound of an algorithm empirically found to hold for random equation systems in Bardet et al. [J. Complexity, 2013]. Our improvement involves three observations: 1) The Valiant-Vazirani lemma can be used to reduce the solution-finding problem to that of counting solutions modulo 2. 2) The monomials in the probabilistic polynomials used in this solution-counting modulo 2 have a special form that we exploit to obtain better bounds on their number than in Lokshtanov et al. [SODA'17]. 3) The problem of solution-counting modulo 2 can be "embedded" in a smaller instance of the original problem, which enables us to apply the algorithm as a subroutine to itself.
Cite as

Andreas Björklund, Petteri Kaski, and Ryan Williams. Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2019.26,
  author =	{Bj\"{o}rklund, Andreas and Kaski, Petteri and Williams, Ryan},
  title =	{{Solving Systems of Polynomial Equations over GF(2) by a Parity-Counting Self-Reduction}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{26:1--26:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.26},
  URN =		{urn:nbn:de:0030-drops-106023},
  doi =		{10.4230/LIPIcs.ICALP.2019.26},
  annote =	{Keywords: equation systems, polynomial method}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.7
Tensor Network Complexity of Multilinear Maps

Authors: Per Austrin, Petteri Kaski, and Kaie Kubjas

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
We study tensor networks as a model of arithmetic computation for evaluating multilinear maps. These capture any algorithm based on low border rank tensor decompositions, such as O(n^{omega+epsilon}) time matrix multiplication, and in addition many other algorithms such as O(n log n) time discrete Fourier transform and O^*(2^n) time for computing the permanent of a matrix. However tensor networks sometimes yield faster algorithms than those that follow from low-rank decompositions. For instance the fastest known O(n^{(omega +epsilon)t}) time algorithms for counting 3t-cliques can be implemented with tensor networks, even though the underlying tensor has border rank n^{3t} for all t >= 2. For counting homomorphisms of a general pattern graph P into a host graph on n vertices we obtain an upper bound of O(n^{(omega+epsilon)bw(P)/2}) where bw(P) is the branchwidth of P. This essentially matches the bound for counting cliques, and yields small improvements over previous algorithms for many choices of P. While powerful, the model still has limitations, and we are able to show a number of unconditional lower bounds for various multilinear maps, including: b) an Omega(n^{bw(P)}) time lower bound for counting homomorphisms from P to an n-vertex graph, matching the upper bound if omega = 2. In particular for P a v-clique this yields an Omega(n^{ceil[2v/3]}) time lower bound for counting v-cliques, and for P a k-uniform v-hyperclique we obtain an Omega(n^v) time lower bound for k >= 3, ruling out tensor networks as an approach to obtaining non-trivial algorithms for hyperclique counting and the Max-3-CSP problem. c) an Omega(2^{0.918n}) time lower bound for the permanent of an n x n matrix.
Cite as

Per Austrin, Petteri Kaski, and Kaie Kubjas. Tensor Network Complexity of Multilinear Maps. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{austrin_et_al:LIPIcs.ITCS.2019.7,
  author =	{Austrin, Per and Kaski, Petteri and Kubjas, Kaie},
  title =	{{Tensor Network Complexity of Multilinear Maps}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.7},
  URN =		{urn:nbn:de:0030-drops-101006},
  doi =		{10.4230/LIPIcs.ITCS.2019.7},
  annote =	{Keywords: arithmetic complexity, lower bound, multilinear map, tensor network}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.17
Counting Connected Subgraphs with Maximum-Degree-Aware Sieving

Authors: Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

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].
Cite as

Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Counting Connected Subgraphs with Maximum-Degree-Aware Sieving. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bjorklund_et_al:LIPIcs.ISAAC.2018.17,
  author =	{Bj\"{o}rklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko},
  title =	{{Counting Connected Subgraphs with Maximum-Degree-Aware Sieving}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.17},
  URN =		{urn:nbn:de:0030-drops-99655},
  doi =		{10.4230/LIPIcs.ISAAC.2018.17},
  annote =	{Keywords: graph embedding, k-path, subgraph counting, maximum degree}
}
Document
DOI: 10.4230/LIPIcs.SEA.2018.28
Engineering Motif Search for Large Motifs

Authors: Petteri Kaski, Juho Lauri, and Suhas Thejaswi

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract
Given a vertex-colored graph H and a multiset M of colors as input, the graph motif problem asks us to decide whether H has a connected induced subgraph whose multiset of colors agrees with M. The graph motif problem is NP-complete but known to admit randomized algorithms based on constrained multilinear sieving over GF(2^b) that run in time O(2^kk^2m {M({2^b})}) and with a false-negative probability of at most k/2^{b-1} for a connected m-edge input and a motif of size k. On modern CPU microarchitectures such algorithms have practical edge-linear scalability to inputs with billions of edges for small motif sizes, as demonstrated by Björklund, Kaski, Kowalik, and Lauri [ALENEX'15]. This scalability to large graphs prompts the dual question whether it is possible to scale to large motif sizes. We present a vertex-localized variant of the constrained multilinear sieve that enables us to obtain, in time O(2^kk^2m{M({2^b})}) and for every vertex simultaneously, whether the vertex participates in at least one match with the motif, with a per-vertex probability of at most k/2^{b-1} for a false negative. Furthermore, the algorithm is easily vector-parallelizable for up to 2^k threads, and parallelizable for up to 2^kn threads, where n is the number of vertices in H. Here {M({2^b})} is the time complexity to multiply in GF(2^b). We demonstrate with an open-source implementation that our variant of constrained multilinear sieving can be engineered for vector-parallel microarchitectures to yield hardware utilization that is bound by the available memory bandwidth. Our main engineering contributions are (a) a version of the recurrence for tightly labeled arborescences that can be executed as a sequence of memory-and-arithmetic coalescent parallel workloads on multiple GPUs, and (b) a bit-sliced low-level implementation for arithmetic in characteristic 2 to support (a).
Cite as

Petteri Kaski, Juho Lauri, and Suhas Thejaswi. Engineering Motif Search for Large Motifs. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{kaski_et_al:LIPIcs.SEA.2018.28,
  author =	{Kaski, Petteri and Lauri, Juho and Thejaswi, Suhas},
  title =	{{Engineering Motif Search for Large Motifs}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{28:1--28:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.28},
  URN =		{urn:nbn:de:0030-drops-89631},
  doi =		{10.4230/LIPIcs.SEA.2018.28},
  annote =	{Keywords: algorithm engineering, constrained multilinear sieving, graph motif problem, multi-GPU, vector-parallel, vertex-localization}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.6
Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants

Authors: Andreas Björklund, Petteri Kaski, and Ryan Williams

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
We present two new data structures for computing values of an n-variate polynomial P of degree at most d over a finite field of q elements. Assuming that d divides q-1, our first data structure relies on (d+1)^{n+2} tabulated values of P to produce the value of P at any of the q^n points using O(nqd^2) arithmetic operations in the finite field. Assuming that s divides d and d/s divides q-1, our second data structure assumes that P satisfies a degree-separability condition and relies on (d/s+1)^{n+s} tabulated values to produce the value of P at any point using O(nq^ssq) arithmetic operations. Our data structures are based on generalizing upper-bound constructions due to Mockenhaupt and Tao (2004), Saraf and Sudan (2008), and Dvir (2009) for Kakeya sets in finite vector spaces from linear to higher-degree polynomial curves. As an application we show that the new data structures enable a faster algorithm for computing integer-valued fermionants, a family of self-reducible polynomial functions introduced by Chandrasekharan and Wiese (2011) that captures numerous fundamental algebraic and combinatorial invariants such as the determinant, the permanent, the number of Hamiltonian cycles in a directed multigraph, as well as certain partition functions of strongly correlated electron systems in statistical physics. In particular, a corollary of our main theorem for fermionants is that the permanent of an m-by-m integer matrix with entries bounded in absolute value by a constant can be computed in time 2^{m-Omega(sqrt(m/log log m))}, improving an earlier algorithm of Bjorklund (2016) that runs in time 2^{m-Omega(sqrt(m/log m))}.
Cite as

Andreas Björklund, Petteri Kaski, and Ryan Williams. Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bjorklund_et_al:LIPIcs.IPEC.2017.6,
  author =	{Bj\"{o}rklund, Andreas and Kaski, Petteri and Williams, Ryan},
  title =	{{Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.6},
  URN =		{urn:nbn:de:0030-drops-85728},
  doi =		{10.4230/LIPIcs.IPEC.2017.6},
  annote =	{Keywords: Besicovitch set, fermionant, finite field, finite vector space, Hamiltonian cycle, homogeneous polynomial, Kakeya set, permanent, polynomial evaluatio}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.91
Directed Hamiltonicity and Out-Branchings via Generalized Laplacians

Authors: Andreas Björklund, Petteri Kaski, and Ioannis Koutis

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We are motivated by a tantalizing open question in exact algorithms: can we detect whether an n-vertex directed graph G has a Hamiltonian cycle in time significantly less than 2^n? We present new randomized algorithms that improve upon several previous works: 1. We show that for any constant 0<lambda<1 and prime p we can count the Hamiltonian cycles modulo p^((1-lambda)n/(3p)) in expected time less than c^n for a constant c<2 that depends only on p and lambda. Such an algorithm was previously known only for the case of counting modulo two [Bj\"orklund and Husfeldt, FOCS 2013]. 2. We show that we can detect a Hamiltonian cycle in O^*(3^(n-alpha(G))) time and polynomial space, where alpha(G) is the size of the maximum independent set in G. In particular, this yields an O^*(3^(n/2)) time algorithm for bipartite directed graphs, which is faster than the exponential-space algorithm in [Cygan et al., STOC 2013]. Our algorithms are based on the algebraic combinatorics of "incidence assignments" that we can capture through evaluation of determinants of Laplacian-like matrices, inspired by the Matrix--Tree Theorem for directed graphs. In addition to the novel algorithms for directed Hamiltonicity, we use the Matrix--Tree Theorem to derive simple algebraic algorithms for detecting out-branchings. Specifically, we give an O^*(2^k)-time randomized algorithm for detecting out-branchings with at least k internal vertices, improving upon the algorithms of [Zehavi, ESA 2015] and [Bj\"orklund et al., ICALP 2015]. We also present an algebraic algorithm for the directed k-Leaf problem, based on a non-standard monomial detection problem.
Cite as

Andreas Björklund, Petteri Kaski, and Ioannis Koutis. Directed Hamiltonicity and Out-Branchings via Generalized Laplacians. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 91:1-91:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bjorklund_et_al:LIPIcs.ICALP.2017.91,
  author =	{Bj\"{o}rklund, Andreas and Kaski, Petteri and Koutis, Ioannis},
  title =	{{Directed Hamiltonicity and Out-Branchings via Generalized Laplacians}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{91:1--91:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.91},
  URN =		{urn:nbn:de:0030-drops-74208},
  doi =		{10.4230/LIPIcs.ICALP.2017.91},
  annote =	{Keywords: counting, directed Hamiltonicity, graph Laplacian, independent set, k-internal out-branching}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.30
The First Parameterized Algorithms and Computational Experiments Challenge

Authors: Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
In this article, the steering committee of the Parameterized Algorithms and Computational Experiments challenge (PACE) reports on the first iteration of the challenge. Where did PACE come from, how did it go, who won, and what's next?
Cite as

Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. The First Parameterized Algorithms and Computational Experiments Challenge. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 30:1-30:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dell_et_al:LIPIcs.IPEC.2016.30,
  author =	{Dell, Holger and Husfeldt, Thore and Jansen, Bart M. P. and Kaski, Petteri and Komusiewicz, Christian and Rosamond, Frances A.},
  title =	{{The First Parameterized Algorithms and Computational Experiments Challenge}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{30:1--30:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.30},
  URN =		{urn:nbn:de:0030-drops-69310},
  doi =		{10.4230/LIPIcs.IPEC.2016.30},
  annote =	{Keywords: treewidth, feedback vertex set, contest, implementation challenge, FPT}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.52
Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time

Authors: Matti Karppa, Petteri Kaski, Jukka Kohonen, and Padraig Ó Catháin

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
We derandomize G. Valiant's [J.ACM 62(2015) Art.13] subquadratic-time algorithm for finding outlier correlations in binary data. Our derandomized algorithm gives deterministic subquadratic scaling essentially for the same parameter range as Valiant's randomized algorithm, but the precise constants we save over quadratic scaling are more modest. Our main technical tool for derandomization is an explicit family of correlation amplifiers built via a family of zigzag-product expanders in Reingold, Vadhan, and Wigderson [Ann. of Math 155(2002), 157-187]. We say that a function f:{-1,1}^d ->{-1,1}^D is a correlation amplifier with threshold 0 <= tau <= 1, error gamma >= 1, and strength p an even positive integer if for all pairs of vectors x,y in {-1,1}^d it holds that (i) |<x,y>|<tau d implies |<f(x),f(y)>| <= (tau*gamma)^p*D; and (ii) |<x,y>| >= tau*d implies (<x,y>/gamma^d})^p*D <= <f(x),f(y)> <= (gamma*<x,y>/d)^p*D.
Cite as

Matti Karppa, Petteri Kaski, Jukka Kohonen, and Padraig Ó Catháin. Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{karppa_et_al:LIPIcs.ESA.2016.52,
  author =	{Karppa, Matti and Kaski, Petteri and Kohonen, Jukka and \'{O} Cath\'{a}in, Padraig},
  title =	{{Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{52:1--52:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.52},
  URN =		{urn:nbn:de:0030-drops-63944},
  doi =		{10.4230/LIPIcs.ESA.2016.52},
  annote =	{Keywords: correlation, derandomization, outlier, similarity search, expander graph}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.13
Dense Subset Sum May Be the Hardest

Authors: Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
The SUBSET SUM problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O^*(2^{n/2})-time algorithm for SUBSET SUM by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", O^*(2^{(0.5-delta)*n})-time algorithm, with some constant delta > 0. Continuing an earlier work [STACS 2015], we study SUBSET SUM parameterized by the maximum bin size beta, defined as the largest number of subsets of the n input integers that yield the same sum. For every epsilon > 0 we give a truly faster algorithm for instances with beta <= 2^{(0.5-epsilon)*n}, as well as instances with beta >= 2^{0.661n}. Consequently, we also obtain a characterization in terms of the popular density parameter n/log_2(t): if all instances of density at least 1.003 admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from a novel combinatorial analysis of mixings of earlier algorithms for SUBSET SUM and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.
Cite as

Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Dense Subset Sum May Be the Hardest. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{austrin_et_al:LIPIcs.STACS.2016.13,
  author =	{Austrin, Per and Kaski, Petteri and Koivisto, Mikko and Nederlof, Jesper},
  title =	{{Dense Subset Sum May Be the Hardest}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{13:1--13:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.13},
  URN =		{urn:nbn:de:0030-drops-57143},
  doi =		{10.4230/LIPIcs.STACS.2016.13},
  annote =	{Keywords: subset sum, additive combinatorics, exponential-time algorithm, homo-morphic hashing, littlewood–offord problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2015.48
Subset Sum in the Absence of Concentration

Authors: Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

Abstract
We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly concentrated on any particular integer value. We present a randomized algorithm that runs in O(2^0.3399nB^4) time on instances with the property that no value can arise as a sum of more than B different subsets of the n given integers.
Cite as

Per Austrin, Petteri Kaski, Mikko Koivisto, and Jesper Nederlof. Subset Sum in the Absence of Concentration. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 48-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{austrin_et_al:LIPIcs.STACS.2015.48,
  author =	{Austrin, Per and Kaski, Petteri and Koivisto, Mikko and Nederlof, Jesper},
  title =	{{Subset Sum in the Absence of Concentration}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{48--61},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.48},
  URN =		{urn:nbn:de:0030-drops-49034},
  doi =		{10.4230/LIPIcs.STACS.2015.48},
  annote =	{Keywords: subset sum, additive combinatorics, exponential-time algorithm, homomorphic hashing, Littlewood--Offord problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.20
Probably Optimal Graph Motifs

Authors: Andreas Björklund, Petteri Kaski, and Lukasz Kowalik

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

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.
Cite as

Andreas Björklund, Petteri Kaski, and Lukasz Kowalik. Probably Optimal Graph Motifs. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 20-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bjorklund_et_al:LIPIcs.STACS.2013.20,
  author =	{Bj\"{o}rklund, Andreas and Kaski, Petteri and Kowalik, Lukasz},
  title =	{{Probably Optimal Graph Motifs}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{20--31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.20},
  URN =		{urn:nbn:de:0030-drops-39196},
  doi =		{10.4230/LIPIcs.STACS.2013.20},
  annote =	{Keywords: graph motif, FPT algorithm}
}
Document
DOI: 10.4230/DagSemProc.08431.3
08431 Open Problems – Moderately Exponential Time Algorithms

Authors: Fedor V. Fomin, Kazuo Iwama, Dieter Kratsch, Petteri Kaski, Mikko Koivisto, Lukasz Kowalik, Yoshio Okamoto, Johan van Rooij, and Ryan Williams

Published in: Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)

Abstract
Two problem sessions were part of the seminar on Moderately Exponential Time Algorithms. Some of the open problems presented at those sessions have been collected.
Cite as

Fedor V. Fomin, Kazuo Iwama, Dieter Kratsch, Petteri Kaski, Mikko Koivisto, Lukasz Kowalik, Yoshio Okamoto, Johan van Rooij, and Ryan Williams. 08431 Open Problems – Moderately Exponential Time Algorithms. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:DagSemProc.08431.3,
  author =	{Fomin, Fedor V. and Iwama, Kazuo and Kratsch, Dieter and Kaski, Petteri and Koivisto, Mikko and Kowalik, Lukasz and Okamoto, Yoshio and van Rooij, Johan and Williams, Ryan},
  title =	{{08431 Open Problems – Moderately Exponential Time Algorithms}},
  booktitle =	{Moderately Exponential Time Algorithms},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8431},
  editor =	{Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.3},
  URN =		{urn:nbn:de:0030-drops-17986},
  doi =		{10.4230/DagSemProc.08431.3},
  annote =	{Keywords: Algorithms, NP-hard problems, Moderately Exponential Time Algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1336
Trimmed Moebius Inversion and Graphs of Bounded Degree

Authors: Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

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 $scr F$ of its subsets, trimmed Moebius inversion allows us to compute the number of packings, coverings, and partitions of $U$ with $k$ sets from $scr F$ in time within a polynomial factor (in $n$) of the number of supersets of the members of $scr 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 $Delta$. 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 $Delta$, these bounds are $O bigl((2-epsilon)^n bigr)$ for $epsilon>0$ independent of the number of vertices $n$.
Cite as

Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Trimmed Moebius Inversion and Graphs of Bounded Degree. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 85-96, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bjorklund_et_al:LIPIcs.STACS.2008.1336,
  author =	{Bj\"{o}rklund, Andreas and Husfeldt, Thore and Kaski, Petteri and Koivisto, Mikko},
  title =	{{Trimmed Moebius Inversion and Graphs of Bounded Degree}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{85--96},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1336},
  URN =		{urn:nbn:de:0030-drops-13369},
  doi =		{10.4230/LIPIcs.STACS.2008.1336},
  annote =	{Keywords: }
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact