4 papers
The Parametrised Complexity of Counting Small Sub-Hypergraphs
Marco Bressan, Julian Brinkmann, Holger Dell +2
Subgraph counting is a fundamental and well-studied problem whose computational complexity is well understood. Quite surprisingly, the hypergraph version of subgraph counting has b…
An Efficient Streaming Algorithm for Approximating Graphlet Distributions
Marco Bressan, T-H. Hubert Chan, Qipeng Kuang +1
In recent years, the problem of computing the frequencies of the induced -vertex subgraphs of a graph, or \emph{-graphlets}, has become central. One approach for this problem…
Counting HyperGraphlets via Color Coding: a Quadratic Barrier and How to Break It
Marco Bressan, Stefano Clemente, Giacomo Fumagalli
We study the problem of counting -hypergraphlets, an interesting but surprisingly ignored primitive, with the aim of understanding whether efficient algorithms exist. To this en…
On Finding Randomly Planted Cliques in Arbitrary Graphs
Francesco Agrimonti, Marco Bressan, Tommaso d'Orsi
We study a planted clique model introduced by Feige where a complete graph of size is planted uniformly at random in an arbitrary -vertex graph. We give a simple dete…