Papers

Harmless Sets in Sparse Classes.

Published
Felix Reidl
Irene Muzi
Pål Grønås Drange
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.

Computing complexity measures of degenerate graphs

Published
Felix Reidl
Patrick Greaves
Irene Muzi
Pål Grønås Drange
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.

A Color-Avoiding Approach to Subgraph Counting in Bounded Expansion Classes.

Published
Felix Reidl
Blair D. Sullivan
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 for sparse host graphs.

Longest paths in 2-edge-connected cubic graphs

Published
Oded Lachish
Felix Reidl
Nikola K. Blanchard
Eldar Fischer
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)$.