Search Results

Documents authored by Husfeldt, Thore

Document
DOI: 10.4230/LIPIcs.ESA.2021.34
Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths

Authors: Radu Curticapean, Holger Dell, and Thore Husfeldt

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

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 n^{f(t,s)}-time algorithm to compute modulo 2^t 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 2^t. Complementing our algorithm, we also give a simple and self-contained proof that counting k-matchings modulo odd integers q is {Mod}_q W[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).
Cite as

Radu Curticapean, Holger Dell, and Thore Husfeldt. Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{curticapean_et_al:LIPIcs.ESA.2021.34,
  author =	{Curticapean, Radu and Dell, Holger and Husfeldt, Thore},
  title =	{{Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.34},
  URN =		{urn:nbn:de:0030-drops-146154},
  doi =		{10.4230/LIPIcs.ESA.2021.34},
  annote =	{Keywords: Counting complexity, matchings, paths, subgraphs, parameterized complexity}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.CPM.2020.1
Algebraic Algorithms for Finding Patterns in Graphs (Invited Talk)

Authors: Thore Husfeldt

Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)

Abstract
I will give a gentle introduction to algebraic graph algorithms by showing how to determine if a given graph contains a simple path of length k. This is a famous problem admitting a beautiful and widely-known algorithm, namely the colour-coding method of Alon, Yuster and Zwick (1995). Starting from this entirely combinatorial approach, I will carefully develop an algebraic perspective on the same problem. First, I will explain how the colour-coding algorithm can be understood as the evaluation of a well-known expression (sometimes called the "walk-sum" of the graph) in a commutative algebra called the zeon algebra. From there, I will introduce the exterior algebra and present the algebraic framework recently developed with Brand and Dell (2018). The presentation is aimed at a combinatorially-minded audience largely innocent of abstract algebra.
Cite as

Thore Husfeldt. Algebraic Algorithms for Finding Patterns in Graphs (Invited Talk). In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{husfeldt:LIPIcs.CPM.2020.1,
  author =	{Husfeldt, Thore},
  title =	{{Algebraic Algorithms for Finding Patterns in Graphs}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-149-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{161},
  editor =	{G{\o}rtz, Inge Li and Weimann, Oren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.1},
  URN =		{urn:nbn:de:0030-drops-121261},
  doi =		{10.4230/LIPIcs.CPM.2020.1},
  annote =	{Keywords: paths, exterior algebra, wedge product, color-coding, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.4
Multivariate Analysis of Orthogonal Range Searching and Graph Distances

Authors: Karl Bringmann, Thore Husfeldt, and Måns Magnusson

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

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

Karl Bringmann, Thore Husfeldt, and Måns Magnusson. Multivariate Analysis of Orthogonal Range Searching and Graph Distances. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.IPEC.2018.4,
  author =	{Bringmann, Karl and Husfeldt, Thore and Magnusson, M\r{a}ns},
  title =	{{Multivariate Analysis of Orthogonal Range Searching and Graph Distances}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{4:1--4:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.4},
  URN =		{urn:nbn:de:0030-drops-102050},
  doi =		{10.4230/LIPIcs.IPEC.2018.4},
  annote =	{Keywords: Diameter, radius, Wiener index, orthogonal range searching, treewidth, vertex cover number}
}
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.ISAAC.2018.19
Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm

Authors: Andreas Björklund and Thore Husfeldt

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

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

Andreas Björklund and Thore Husfeldt. Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bjorklund_et_al:LIPIcs.ISAAC.2018.19,
  author =	{Bj\"{o}rklund, Andreas and Husfeldt, Thore},
  title =	{{Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{19:1--19:13},
  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.19},
  URN =		{urn:nbn:de:0030-drops-99670},
  doi =		{10.4230/LIPIcs.ISAAC.2018.19},
  annote =	{Keywords: Shortest disjoint paths, Cubic planar graph}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.16
Computing Graph Distances Parameterized by Treewidth and Diameter

Authors: Thore Husfeldt

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

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

Thore Husfeldt. Computing Graph Distances Parameterized by Treewidth and Diameter. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 16:1-16:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{husfeldt:LIPIcs.IPEC.2016.16,
  author =	{Husfeldt, Thore},
  title =	{{Computing Graph Distances Parameterized by Treewidth and Diameter}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{16:1--16:11},
  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.16},
  URN =		{urn:nbn:de:0030-drops-69476},
  doi =		{10.4230/LIPIcs.IPEC.2016.16},
  annote =	{Keywords: Graph algorithms, diameter, treewidth, Strong Exponential Time Hypothesis}
}
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
Complete Volume
DOI: 10.4230/LIPIcs.IPEC.2015
LIPIcs, Volume 43, IPEC'15, Complete Volume

Authors: Thore Husfeldt and Iyad Kanj

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
LIPIcs, Volume 43, IPEC'15, Complete Volume
Cite as

10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Proceedings{husfeldt_et_al:LIPIcs.IPEC.2015,
  title =	{{LIPIcs, Volume 43, IPEC'15, Complete Volume}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015},
  URN =		{urn:nbn:de:0030-drops-56020},
  doi =		{10.4230/LIPIcs.IPEC.2015},
  annote =	{Keywords: Complexity Measures and Classes, Analysis of Algorithms and Problem Complexity, Discrete Mathematics}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.IPEC.2015.i
Front Matter, Table of Contents, Preface, Program Committee, External Reviewers, List of Authors

Authors: Thore Husfeldt and Iyad Kanj

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
Front Matter, Table of Contents, Preface, Program Committee, External Reviewers, List of Authors
Cite as

10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. i-xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{husfeldt_et_al:LIPIcs.IPEC.2015.i,
  author =	{Husfeldt, Thore and Kanj, Iyad},
  title =	{{Front Matter, Table of Contents, Preface, Program Committee, External Reviewers, List of Authors}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{i--xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.i},
  URN =		{urn:nbn:de:0030-drops-55676},
  doi =		{10.4230/LIPIcs.IPEC.2015.i},
  annote =	{Keywords: IPEC}
}
Document
DOI: 10.4230/DagRep.3.8.40
Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331)

Authors: Thore Husfeldt, Ramamohan Paturi, Gregory B. Sorkin, and Ryan Williams

Published in: Dagstuhl Reports, Volume 3, Issue 8 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13331 "Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time". Problems are often solved in practice by algorithms with worst-case exponential time complexity. It is of interest to find the fastest algorithms for a given problem, be it polynomial, exponential, or something in between. The focus of the Seminar is on finer-grained notions of complexity than np-completeness and on understanding the exact complexities of problems. The report provides a rationale for the workshop and chronicles the presentations at the workshop. The report notes the progress on the open problems posed at the past workshops on the same topic. It also reports a collection of results that cite the presentations at the previous seminar. The docoument presents the collection of the abstracts of the results presented at the Seminar. It also presents a compendium of open problems.
Cite as

Thore Husfeldt, Ramamohan Paturi, Gregory B. Sorkin, and Ryan Williams. Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331). In Dagstuhl Reports, Volume 3, Issue 8, pp. 40-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{husfeldt_et_al:DagRep.3.8.40,
  author =	{Husfeldt, Thore and Paturi, Ramamohan and Sorkin, Gregory B. and Williams, Ryan},
  title =	{{Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331)}},
  pages =	{40--72},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{8},
  editor =	{Husfeldt, Thore and Paturi, Ramamohan and Sorkin, Gregory B. and Williams, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.8.40},
  URN =		{urn:nbn:de:0030-drops-43422},
  doi =		{10.4230/DagRep.3.8.40},
  annote =	{Keywords: Algorithms, exponential time algorithms, exact algorithms, computational complexity, satisfiability}
}
Document
DOI: 10.4230/DagSemProc.10441.1
10441 Abstracts Collection – Exact Complexity of NP-hard Problems

Authors: Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, and Gregory B. Sorkin

Published in: Dagstuhl Seminar Proceedings, Volume 10441, Exact Complexity of NP-hard Problems (2011)

Abstract
A decade before NP-completeness became the lens through which Computer Science views computationally hard problems, beautiful algorithms were discovered that are much better than exhaustive search, for example Bellman's 1962 dynamic programming treatment of the Traveling Salesman problem and Ryser's 1963 inclusion--exclusion formula for the permanent.
Cite as

Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, and Gregory B. Sorkin. 10441 Abstracts Collection – Exact Complexity of NP-hard Problems. In Exact Complexity of NP-hard Problems. Dagstuhl Seminar Proceedings, Volume 10441, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{husfeldt_et_al:DagSemProc.10441.1,
  author =	{Husfeldt, Thore and Kratsch, Dieter and Paturi, Ramamohan and Sorkin, Gregory B.},
  title =	{{10441 Abstracts Collection – Exact Complexity of NP-hard Problems}},
  booktitle =	{Exact Complexity of NP-hard Problems},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10441},
  editor =	{Thore Husfeldt and Dieter Kratsch and Ramamohan Paturi and Gregory B. Sorkin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10441.1},
  URN =		{urn:nbn:de:0030-drops-29363},
  doi =		{10.4230/DagSemProc.10441.1},
  annote =	{Keywords: Complexity, Algorithms, NP-hard Problems, Exponential Time, SAT, Graphs}
}
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