Pragmatic Parameterized Algorithms
Final Report Abstract
It is generally believed that complex networks are in some way sparse. While sparsity in its most general definition only implies a small average number of edges, structural sparsity imposes stricter conditions which force this small average. An example of such a structural property is planarity or excluding some fixed graph as a minor. Exploiting such structural properties of a graph class usually leads to more efficient algorithms. Complex networks exhibit properties such as long-tailed degree distributions, low diameter, and small degeneracy. Unfortunately, these typical properties, unlike structural properties, are difficult to exploit in the design of fast algorithms. We made progress into bringing these two quite different worlds together by considering the possibility that certain classes of complex networks are contained in graph classes of bounded expansion, a relative new concept in the field of theoretical computer science. Graphs of bounded expansion generalize in particular graph classes characterized by forbidden (topological) minors, planar graphs, graphs of bounded genus, and graphs with bounded maximal degree. To establish this connection between complex networks and graphs of bounded expansion, we analyze several probabilistic graph models that are used to study complex networks, and show that they generate graphs of bounded expansion with high probability. Graph classes of bounded expansion provide a whole new algorithmic toolkit, which we used to tackle well known problems in the field of complex networks, such as motif counting and computing centrality measures. Our algorithms take linear time in the size of the network. Crucial to our algorithms is a width measure called treedepth. This measure is important from a theoretical point of view as it provides an alternative characterization of graphs of bounded expansion via low treedepth colorings. From a practical point of view, this measure is sometimes easier to work with than treewidth, for instance when counting motifs, and this provides motivation to use it as a parameter when designing algorithms. Many efficient algorithms for bounded expansion graphs rely on small treedepth decompositions of relatively large induced subgraphs of a network. While it is known in theory that computing an optimal treedepth decomposition is fixed parameter tractable, the underlying algorithms were not practical at all. We designed a direct algorithm that does not rely on meta-theorems any more with a running time of 2^O(t2)n. The combinations of techniques on low treedepth graphs and practical methods to compute low treedepth colorings for real world complex networks yielded algorithms that have linear running time in theory and do not suffer from huge hidden constants that would spoil their practical deployment. Moreover, they are oblivious to a priori unknown properties of the graph class from which we draw the instances, like the expansion function.
Publications
- Overlapping communities in social networks
J. Dreier, P. Kuinke, R. Przybylski, F. Reidl, P. Rossmanith and S. Sikdar
- Structural Sparsity of Complex Networks:, Random Graph Models and Linear Algorithms
E. D. Demaine, F. Reidl, P. Rossmanith, F. Sánchez Villaamil, S. Sikdar and B. D. Sullivan
- A Faster Parameterized Algorithm for Treedepth ICALP 2014
F. Reidl, P. Rossmanith, F. Sanchez Villaamil and S. Sikdar
(See online at https://doi.org/10.1007/978-3-662-43948-7_77) - Exact algorithms for problems related to the densest k-set problem. Inf. Process. Lett., 114(9):510-513, 2014
M. Chang, L. Chen, L. Hung, P. Rossmanith, and G. Wu
(See online at https://doi.org/10.1016/j.ipl.2014.04.009) - Hyperbolicity, degeneracy, and expansion of random intersection graphs. WAW 2015
M. Farrell, T. Goodrich, N. Lemons, F. Reidl, F. Sánchez Villaamil and B. D. Sullivan
(See online at https://doi.org/10.1007/978-3-319-26784-5_3)
