# Papers

#### Harmless Sets in Sparse Classes.

*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.

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

*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.

#### Computing complexity measures of degenerate graphs

*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.

#### Longest paths in 2-edge-connected cubic graphs

*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)$.

Design Ⓒ Felix Reidl 2023