Parameterized algorithmics for network analysis

This thesis studies the parameterized computational complexity of NP-hard problems that have applications in two areas of network analysis: clustering and querying. In particular, we aim at identifying parameters that describe the complexity of the computational problems and may thus serve as basis for efficient algorithms for these problems. Network clustering is the task of assigning the vertices of the network into groups such that the groups contain network vertices that are similar to each other. The origin of our investigations for network clustering is the well-studied NP-hard Cluster Editing problem. We extend previous work on Cluster Editing by showing NP-hardness and running time lower bounds for restricted cases of Cluster Editing, and by presenting parameterized algorithms for NP-hard generalizations and variants of Cluster Editing such as Consensus Clustering. Network querying is the task of finding a subnetwork of a large host network that is similar to a given small network, the query. Network querying problems are related to the Subgraph Isomorphism problem and therefore usually NP-hard. We present parameterized algorithms and hardness results for dense queries, for topology-free querying, and for the case that for each query vertex the number of similar vertices in the host is bounded.