DAM • 2018 • Katrin Casel, Jan Dreier, Henning Fernau, Moritz Gobbert, Philipp Kuinke, Fernando Sánchez Villaamil, Markus L. Schmid, Erik Jan van Leeuwen
An independency (cliquy) tree of an n-vertex graph G is a spanning tree of in which the set of leaves induces an independent set (clique). We study the problems of minimizing or maximizing the number of leaves of such trees, and fully characterize their parameterized complexity. We show that all four variants of deciding if an independency/cliquy tree with at least/most l leaves exists parameterized by l are either Para-NP- or W-hard. We prove that minimizing the number of leaves of a cliquy tree parameterized by the number of internal vertices is Para-NP-hard too. However, we show that minimizing the number of leaves of an independency tree parameterized by the number k of internal vertices has an O*(4^k)-time algorithm and a 2k vertex kernel. Moreover, we prove that maximizing the number of leaves of an independency/cliquy tree parameterized by the number k of internal vertices both have an O*(18^k)-time algorithm and an O(k2^k) vertex kernel, but no polynomial kernel unless the polynomial hierarchy collapses to the third level. Finally, we present an O(3^n f(n))-time algorithm to find a spanning tree where the leaf set has a property that can be decided in f(n) time and has minimum or maximum size.
Preprint • 2018 • Jan Dreier, Philipp Kuinke, Peter Rossmanith
Preferential attachment graphs are random graphs designed to mimic properties of typical real world networks. They are constructed by a random process that iteratively adds vertices and attaches them preferentially to vertices that already have high degree. We use improved concentration bounds for vertex degrees to show that preferential attachment graphs contain asymptotically almost surely (a.a.s.) a one-subdivided clique of size at least (log n)^1/4. Therefore, preferential attachment graphs are a.a.s somewhere-dense. This implies that algorithmic techniques developed for sparse graphs are not directly applicable to them. The concentration bounds state: Assuming that the exact degree d of a fixed vertex (or set of vertices) at some early time t of the random process is known, the probability distribution of d is sharply concentrated as the random process evolves if and only if d is large at time t.
SOFSEM • 2018 • Jan Dreier, Philipp Kuinke, Ba Le Xuan, Peter Rossmanith
We analyze local properties of sparse Erdős–Rényi graphs, where d(n)/n is the edge probability. In particular we study the behavior of very short paths. For d(n)=o(1) we show that G(n,d(n)/n) has asymptotically almost surely (a.a.s.) bounded local treewidth and therefore is a.a.s. nowhere dense. We also discover a new and simpler proof that G(n,d/n) has a.a.s. bounded expansion for constant d. The local structure of sparse Erdős–Rényi graphs is very special, which implies efficient algorithms for subgraph isomorphism, in particular for finding subgraphs with small diameter.