Papers

Abstract: We study the property of $H$-freeness in graphs with known bounded average degree, i.e. the property of a graph not containing some graph $H$ as a subgraph. $H$-freeness is one of the fundamental graph properties that has been studied in the property testing framework. Levi [Reut Levi, 2021] showed that triangle-freeness is testable in graphs of bounded arboricity, which is a superset of e.g. planar graphs or graphs of bounded degree. Complementing this result is a recent preprint [Talya Eden et al., 2024] by Eden which shows that, for every $r \geq 4$, $C_r$-freeness is not testable in graphs of bounded arboricity.

Abstract: The $2$-admissibility of a graph is a promising measure to identify real-world networks which have an algorithmically favourable structure. In contrast to other related measures, like the weak/strong $2$-colouring numbers or the maximum density of graphs that appear as~$1$-subdivisions, the $2$-admissibility can be computed in polynomial time. However, so far these results are theoretical only and no practical implementation to compute the $2$-admissibility exists. Here we present an algorithm which decides whether the $2$-admissibility of an input graph $G$ is at most $p$ in time $O(p^4 |V(G)|)$ and space $O(|E(G)| + p^2)$. The simple structure of the algorithm makes it easy to implement. We evaluate our implementation on a corpus of 214 real-world networks and find that the algorithm runs efficiently even on networks with millions of edges, that it has a low memory footprint, and that indeed many networks have a small $2$-admissibility.

Abstract: We show that the VC-dimension of a graph can be computed in time $n^{\lceil\log d+1\rceil} d^{O(d)}$, where~$d$ is the degeneracy of the input graph. The core idea of our algorithm is a data structure to efficiently query the number of vertices that see a specific subset of vertices inside of a (small) query set. The construction of this data structure takes time $O(d2^dn)$, afterwards queries can be computed efficiently using fast Möbius inversion.

Abstract: In the classic TARGET SET SELECTION problem, we are asked to minimise the number of nodes to activate so that, after the application of a certain propagation process, all nodes of the graph are active. Bazgan and Chopin [Discrete Optimization, 14:170--182, 2014] introduced the opposite problem, named HARMLESS SET, in which they ask to maximise the number of nodes to activate such that not a single additional node is activated. In this paper we investigate how sparsity impacts the tractability of HARMLESS SET.

Abstract: We present an algorithm to count the number of occurrences of a pattern graph $H$ on $h$ vertices as an induced subgraph in a host graph $G$. If $G$ belongs to a bounded expansion class, the algorithm runs in linear time, if $G$ belongs to a nowhere dense class it runs in almost-linear time. Our design choices are motivated by the need for an approach that can be engineered into a practical implementation

Abstract: We prove almost tight bounds on the length of paths in $2$-edge-connected cubic graphs. Concretely, we show that (i) every $2$-edge-connected cubic graph of size $n$ has a path of length $\Omega(\log_2 n / \log\log n)$, and (ii) there exists a $2$-edge-connected cubic graph, such that every path in the graph has length $O(\log_2 n)$.