Dokument

Summary:
In this thesis we investigate the computational complexity of two families of graph problems with applications in social network analysis and artificial intelligence. We analyze the classic, fine-grained, and parameterized complexity of the considered problems. Social networks can be modeled with the help of undirected graphs, in which the vertices correspond to the agents in the network and an edge between two vertices corresponds to a relationship or an interaction between two agents. One task in social network analysis is to classify the relationships into strong and weak relationships, if only the graph structure of the social network is known. In the computational problem Strong Triadic Closure (STC) we are given an undirected graph G and an integer k and aim to label the edges of G as strong or weak such that at most k edges are weak and G contains no induced P_3 with two strong edges. We investigate the classic and parameterized complexity of STC. We also study a version of STC with multiple strong relationship types (Multi-STC) and introduce further generalizations where-for example-one may use vertex lists (VL-Multi-STC) to restrict the set of possible strong relationship types incident with each vertex. We show that under the Exponential Time Hypothesis (ETH), VL-Multi-STC cannot be solved in time 2^{o(|V|^2)}. We then proceed with a parameterized complexity analysis of Multi-STC and its generalizations. For example, we provide a problem kernel for Multi-STC parameterized by an edge deletion distance to low-degree graphs. A Bayesian network structure is a directed acyclic graph, where the vertices correspond to random variables and the arcs correspond to conditional dependencies. We study the algorithmic task of learning an optimal network structure from observed data using a score-based approach. Extending previous work, we analyze the parameterized complexity of learning an optimal network structure when additional constraints are posed on the network structure or on its moralized graph. For example, we show that learning an optimal network whose moralized graph has dissociation number at most k can be done in polynomial time for constant k. Furthermore, we analyze the parameterized complexity of learning a good network structure where the underlying undirected graph is acyclic. This problem variant is known as Polytree Learning. Finally, we study parameterized local search algorithms for learning a network structure. We consider the ordering-based approach where a network structure is represented by a topological ordering. For a given integer r and a pre-defined distance function on the space of orderings, we aim to find an optimal ordering that has distance at most r to a given ordering. We analyze the parameterized complexity for r with regard to four natural distance functions.

Das Dokument ist im Internet frei zugänglich - Hinweise zu den Nutzungsrechten