Project Details
Projekt Print View

Pragmatic Parameterized Algorithms

Subject Area Theoretical Computer Science
Term from 2012 to 2015
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 221760991
 
Final Report Year 2016

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

 
 

Additional Information

Textvergrößerung und Kontrastanpassung