Search Results

Documents authored by Bressan, Marco

Document
DOI: 10.4230/LIPIcs.ITCS.2023.27
Counting Subgraphs in Somewhere Dense Graphs

Authors: Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, and Marc Roth

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We study the problems of counting copies and induced copies of a small pattern graph H in a large host graph G. Recent work fully classified the complexity of those problems according to structural restrictions on the patterns H. In this work, we address the more challenging task of analysing the complexity for restricted patterns and restricted hosts. Specifically we ask which families of allowed patterns and hosts imply fixed-parameter tractability, i.e., the existence of an algorithm running in time f(H)⋅|G|^O(1) for some computable function f. Our main results present exhaustive and explicit complexity classifications for families that satisfy natural closure properties. Among others, we identify the problems of counting small matchings and independent sets in subgraph-closed graph classes 𝒢 as our central objects of study and establish the following crisp dichotomies as consequences of the Exponential Time Hypothesis: - Counting k-matchings in a graph G ∈ 𝒢 is fixed-parameter tractable if and only if 𝒢 is nowhere dense. - Counting k-independent sets in a graph G ∈ 𝒢 is fixed-parameter tractable if and only if 𝒢 is nowhere dense. Moreover, we obtain almost tight conditional lower bounds if 𝒢 is somewhere dense, i.e., not nowhere dense. These base cases of our classifications subsume a wide variety of previous results on the matching and independent set problem, such as counting k-matchings in bipartite graphs (Curticapean, Marx; FOCS 14), in F-colourable graphs (Roth, Wellnitz; SODA 20), and in degenerate graphs (Bressan, Roth; FOCS 21), as well as counting k-independent sets in bipartite graphs (Curticapean et al.; Algorithmica 19). At the same time our proofs are much simpler: using structural characterisations of somewhere dense graphs, we show that a colourful version of a recent breakthrough technique for analysing pattern counting problems (Curticapean, Dell, Marx; STOC 17) applies to any subgraph-closed somewhere dense class of graphs, yielding a unified view of our current understanding of the complexity of subgraph counting.
Cite as

Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, and Marc Roth. Counting Subgraphs in Somewhere Dense Graphs. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bressan_et_al:LIPIcs.ITCS.2023.27,
  author =	{Bressan, Marco and Goldberg, Leslie Ann and Meeks, Kitty and Roth, Marc},
  title =	{{Counting Subgraphs in Somewhere Dense Graphs}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.27},
  URN =		{urn:nbn:de:0030-drops-175304},
  doi =		{10.4230/LIPIcs.ITCS.2023.27},
  annote =	{Keywords: counting problems, somewhere dense graphs, parameterised complexity theory}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.6
Faster Subgraph Counting in Sparse Graphs

Authors: Marco Bressan

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
A fundamental graph problem asks to compute the number of induced copies of a k-node pattern graph H in an n-node graph G. The fastest algorithm to date is still the 35-years-old algorithm by Nešetřil and Poljak [Nešetřil and Poljak, 1985], with running time f(k) * O(n^{omega floor[k/3] + 2}) where omega <=2.373 is the matrix multiplication exponent. In this work we show that, if one takes into account the degeneracy d of G, then the picture becomes substantially richer and leads to faster algorithms when G is sufficiently sparse. More precisely, after introducing a novel notion of graph width, the DAG-treewidth, we prove what follows. If H has DAG-treewidth tau(H) and G has degeneracy d, then the induced copies of H in G can be counted in time f(d,k) * O~(n^{tau(H)}); and, under the Exponential Time Hypothesis, no algorithm can solve the problem in time f(d,k) * n^{o(tau(H)/ln tau(H))} for all H. This result characterises the complexity of counting subgraphs in a d-degenerate graph. Developing bounds on tau(H), then, we obtain natural generalisations of classic results and faster algorithms for sparse graphs. For example, when d=O(poly log(n)) we can count the induced copies of any H in time f(k) * O~(n^{floor[k/4] + 2}), beating the Nešetřil-Poljak algorithm by essentially a cubic factor in n.
Cite as

Marco Bressan. Faster Subgraph Counting in Sparse Graphs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bressan:LIPIcs.IPEC.2019.6,
  author =	{Bressan, Marco},
  title =	{{Faster Subgraph Counting in Sparse Graphs}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{6:1--6:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.6},
  URN =		{urn:nbn:de:0030-drops-114673},
  doi =		{10.4230/LIPIcs.IPEC.2019.6},
  annote =	{Keywords: subgraph counting, tree decomposition, degeneracy}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.18
On Approximating the Stationary Distribution of Time-reversible Markov Chains

Authors: Marco Bressan, Enoch Peserico, and Luca Pretto

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
Approximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches require tilde{O}(tau/pi(v)) operations to approximate the probability pi(v) of a state v in a chain with mixing time tau, and even the best available techniques still have complexity tilde{O}(tau^1.5 / pi(v)^0.5); and since these complexities depend inversely on pi(v), they can grow beyond any bound in the size of the chain or in its mixing time. In this paper we show that, for time-reversible Markov chains, there exists a simple randomized approximation algorithm that breaks this "small-pi(v) barrier".
Cite as

Marco Bressan, Enoch Peserico, and Luca Pretto. On Approximating the Stationary Distribution of Time-reversible Markov Chains. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bressan_et_al:LIPIcs.STACS.2018.18,
  author =	{Bressan, Marco and Peserico, Enoch and Pretto, Luca},
  title =	{{On Approximating the Stationary Distribution of Time-reversible Markov Chains}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.18},
  URN =		{urn:nbn:de:0030-drops-84949},
  doi =		{10.4230/LIPIcs.STACS.2018.18},
  annote =	{Keywords: Markov chains, MCMC sampling, large graph algorithms, randomized algorithms, sublinear algorithms}
}
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 About DROPS Imprint Privacy Contact