title: Parameterized Algorithmics for Graph-Based Data Analysis
title: Parametrisierte Algorithmik für graphbasierte Datenanalyse
titleType: AlternativeTitle
Creators: name: Grüttemeier, Niels
Publisher: name: Philipps-Universität Marburg
Year: 2022
Subjects: subject: Mathematics
subject: FOS: Mathematics
subject: Mathematik
subject: Parametrisierte Komplexität
subject: Parameterized Complexity Algorithms Graph Algorithms Strong Triadic Closure Bayesian Networks
subject: Algorithmik

description: In dieser Dissertation untersuchen wir die Berechnungskomplexität zweier Familien von Graphproblemen, die Anwendung im Bereich der Analyse sozialer Netzwerke und im Bereich der künstlichen Intelligenz finden. Wir analysieren die klassische, fine-grained und parametrisierte Komplexität. Soziale Netzwerke können mit Hilfe ungerichteter Graphen modelliert werden, wobei die Knoten den Agenten und die Kanten den Beziehungen oder Interaktionen entsprechen. Eine Aufgabe in der Analyse sozialer Netzwerke ist es, Beziehungen zwischen Agenten als stark oder schwach zu klassifizieren, wenn nur die Netzwerkstruktur gegeben ist. In Strong Triadic Closure (STC) ist die Eingabe ein Graph G und eine ganze Zahl k. Das Ziel ist es, die Kanten in G als stark oder schwach zu klassifizieren, sodass G keinen induzierten P_3 mit zwei starken Kanten enthält. Wir untersuchen die klassische und die parametrisierte Komplexität von STC und einer STC-Version mit mehreren starken Verbindungstypen (Multi-STC) und führen weitere Verallgemeinerungen des Problems ein, in denen etwa Knotenlisten benutzt werden können um mögliche starke Verbindungstypen an einem Knoten einzuschränken (VL-Multi-STC). Wir zeigen, dass VL-Multi-STC unter der Annahme der Exponential Time Hypothesis (ETH) nicht in 2^{o(|V|^2)} Zeit gelöst werden kann. Bezüglich der parametrisierten Komplexität liefern wir etwa einen Problemkern für Multi-STC parametrisiert durch einen Kantenlöschungsparameter, der die Distanz von G zu einem Graphen mit niedrigem Maximalgrad misst. Eine bayessche Netzwerkstruktur ist ein gerichteter Graph, wobei die Knoten Zufallsvariablen und die Kanten bedingten Abhängigkeiten entsprechen. Wir untersuchen die algorithmische Aufgabe eine optimale Netzwerkstruktur aus gemessenen Daten mit Hilfe eines score-basierten Ansatzes zu lernen. In Anknüpfung an bestehende Forschung untersuchen wir die parametrisierte Komplexität des Lernens einer Netzwerkstruktur, wenn zusätzliche Bedingungen an das Netzwerk oder an den moralisierten Graph gestellt werden. Wir zeigen beispielsweise, dass das Lernen einer Netzwerkstruktur, deren Moralgraph eine Dissociation Number von höchstens k hat, in polynomialzeit lösbar ist, falls k eine Konstante ist. Weiterhin analysieren wir die parametrisierte Komplexität vom Lernen einer Netzwerkstruktur, deren unterliegender, ungerichteter Graph azyklisch ist. Diese Problemversion ist auch als Polytree Learning bekannt. Schließlich betrachten wir parametrisierte lokale Suche für das Lernen von bayesschen Netzwerkstrukturen. Wir verwenden dabei einen ordnungsbasierten Ansatz, in dem eine Netzwerkstruktur durch ihre topologische Sortierung repräsentiert wird. Für eine gegebene Zahl r und eine vordefinierte Distanzfunktion auf dem Raum der topologischen Sortierungen geht es darum, eine optimale Sortierung mit Distanz höchstens r zur gegebenen Sortierung zu finden. Wir analysieren die parametrisierte Komplexität für den Parameter r für vier natürliche Distanzfunktionen.
description: 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.