Search

Published in print by Universitätsverlag der TU Berlin, ISBN 978-3-7983-3209-6 (ISSN 2199-5249) In dieser Arbeit entwickeln wir schnellere exakte Algorithmen (schneller bezüglich der Worst-Case-Laufzeit) für Spezialfälle von Graphproblemen. Diese Algorithmen beruhen größtenteils auf dynamischem Programmieren und auf 2-SAT-Programmierung. Dynamisches Programmieren beschreibt den Vorgang, ein Problem rekursiv in Unterprobleme zu zerteilen, sodass diese Unterprobleme gemeinsame Unterunterprobleme haben. Wenn diese Unterprobleme optimal gelöst wurden, dann kombiniert das dynamische Programm diese Lösungen zu einer optimalen Lösung des Ursprungsproblems. 2-SAT-Programmierung bezeichnet den Prozess, ein Problem durch eine Menge von 2-SAT-Formeln (aussagenlogische Formeln in konjunktiver Normalform, wobei jede Klausel aus maximal zwei Literalen besteht) auszudrücken. Dabei müssen erfüllende Wahrheitswertbelegungen für eine Teilmenge der 2-SAT-Formeln zu einer Lösung des Ursprungsproblems korrespondieren. Wenn eine 2-SAT-Formel erfüllbar ist, dann kann eine erfüllende Wahrheitswertbelegung in Linearzeit in der Länge der Formel berechnet werden. Wenn entsprechende 2-SAT-Formeln also in polynomieller Zeit in der Eingabegröße des Ursprungsproblems erstellt werden können, dann kann das Ursprungsproblem in polynomieller Zeit gelöst werden. Im folgenden beschreiben wir die Hauptresultate der Arbeit. Bei dem Diameter-Problem wird die größte Distanz zwischen zwei beliebigen Knoten in einem gegebenen ungerichteten Graphen gesucht. Das Ergebnis (der Durchmesser des Eingabegraphen) gehört zu den wichtigsten Parametern der Graphanalyse. In dieser Arbeit erzielen wir sowohl positive als auch negative Ergebnisse für Diameter. Wir konzentrieren uns dabei auf parametrisierte Algorithmen für Parameterkombinationen, die in vielen praktischen Anwendungen klein sind, und auf Parameter, die eine Distanz zur Trivialität messen. Bei dem Problem Length-Bounded Cut geht es darum, ob es eine Kantenmenge begrenzter Größe in einem Eingabegraphen gibt, sodass das Entfernen dieser Kanten die Distanz zwischen zwei gegebenen Knoten auf ein gegebenes Minimum erhöht. Wir bestätigen in dieser Arbeit eine Vermutung aus der wissenschaftlichen Literatur, dass Length-Bounded Cut in polynomieller Zeit in der Eingabegröße auf Einheitsintervallgraphen (Intervallgraphen, in denen jedes Intervall die gleiche Länge hat) gelöst werden kann. Der Algorithmus basiert auf dynamischem Programmieren. k-Disjoint Shortest Paths beschreibt das Problem, knotendisjunkte Pfade zwischen k gegebenen Knotenpaaren zu suchen, sodass jeder der k Pfade ein kürzester Pfad zwischen den jeweiligen Endknoten ist. Wir beschreiben ein dynamisches Programm mit einer Laufzeit n^O((k+1)!) für dieses Problem, wobei n die Anzahl der Knoten im Eingabegraphen ist. Dies zeigt, dass k-Disjoint Shortest Paths in polynomieller Zeit für jedes konstante k gelöst werden kann, was für über 20 Jahre ein ungelöstes Problem der algorithmischen Graphentheorie war. Das Problem Tree Containment fragt, ob ein gegebener phylogenetischer Baum T in einem gegebenen phylogenetischen Netzwerk N enthalten ist. Ein phylogenetisches Netzwerk (bzw. ein phylogenetischer Baum) ist ein gerichteter azyklischer Graph (bzw. ein gerichteter Baum) mit genau einer Quelle, in dem jeder Knoten höchstens eine ausgehende oder höchstens eine eingehende Kante hat und jedes Blatt eine Beschriftung trägt. Das Problem stammt aus der Bioinformatik aus dem Bereich der Suche nach dem Baums des Lebens (der Geschichte der Artenbildung). Wir führen eine neue Variante des Problems ein, die wir Soft Tree Containment nennen und die bestimmte Unsicherheitsfaktoren berücksichtigt. Wir zeigen mit Hilfe von 2-SAT-Programmierung, dass Soft Tree Containment in polynomieller Zeit gelöst werden kann, wenn N ein phylogenetischer Baum ist, in dem jeweils maximal zwei Blätter die gleiche Beschriftung tragen. Wir ergänzen dieses Ergebnis mit dem Beweis, dass Soft Tree Containment NP-schwer ist, selbst wenn N auf phylogenetische Bäume beschränkt ist, in denen jeweils maximal drei Blätter die gleiche Beschriftung tragen. Abschließend betrachten wir das Problem Reachable Object. Hierbei wird nach einer Sequenz von rationalen Tauschoperationen zwischen Agentinnen gesucht, sodass eine bestimmte Agentin ein bestimmtes Objekt erhält. Eine Tauschoperation ist rational, wenn beide an dem Tausch beteiligten Agentinnen ihr neues Objekt gegenüber dem jeweiligen alten Objekt bevorzugen. Reachable Object ist eine Verallgemeinerung des bekannten und viel untersuchten Problems Housing Market. Hierbei sind die Agentinnen in einem Graphen angeordnet und nur benachbarte Agentinnen können Objekte miteinander tauschen. Wir zeigen, dass Reachable Object NP-schwer ist, selbst wenn jede Agentin maximal drei Objekte gegenüber ihrem Startobjekt bevorzugt und dass Reachable Object polynomzeitlösbar ist, wenn jede Agentin maximal zwei Objekte gegenüber ihrem Startobjekt bevorzugt. Wir geben außerdem einen Polynomzeitalgorithmus für den Spezialfall an, in dem der Graph der Agentinnen ein Kreis ist. Dieser Polynomzeitalgorithmus basiert auf 2-SAT-Programmierung. This thesis presents faster (in terms of worst-case running times) exact algorithms for special cases of graph problems through dynamic programming and 2-SAT programming. Dynamic programming describes the procedure of breaking down a problem recursively into overlapping subproblems, that is, subproblems with common subsubproblems. Given optimal solutions to these subproblems, the dynamic program then combines them into an optimal solution for the original problem. 2-SAT programming refers to the procedure of reducing a problem to a set of 2-SAT formulas, that is, boolean formulas in conjunctive normal form in which each clause contains at most two literals. Computing whether such a formula is satisfiable (and computing a satisfying truth assignment, if one exists) takes linear time in the formula length. Hence, when satisfying truth assignments to some 2-SAT formulas correspond to a solution of the original problem and all formulas can be computed efficiently, that is, in polynomial time in the input size of the original problem, then the original problem can be solved in polynomial time. We next describe our main results. Diameter asks for the maximal distance between any two vertices in a given undirected graph. It is arguably among the most fundamental graph parameters. We provide both positive and negative parameterized results for distance-from-triviality-type parameters and parameter combinations that were observed to be small in real-world applications. In Length-Bounded Cut, we search for a bounded-size set of edges that intersects all paths between two given vertices of at most some given length. We confirm a conjecture from the literature by providing a polynomial-time algorithm for proper interval graphs which is based on dynamic programming. k-Disjoint Shortest Paths is the problem of finding (vertex-)disjoint paths between given vertex terminals such that each of these paths is a shortest path between the respective terminals. Its complexity for constant k > 2 has been an open problem for over 20 years. Using dynamic programming, we show that k-Disjoint Shortest Paths can be solved in polynomial time for each constant k. The problem Tree Containment asks whether a phylogenetic tree T is contained in a phylogenetic network N. A phylogenetic network (or tree) is a leaf-labeled single-source directed acyclic graph (or tree) in which each vertex has in-degree at most one or out-degree at most one. The problem stems from computational biology in the context of the tree of life (the history of speciation). We introduce a particular variant that resembles certain types of uncertainty in the input. We show that if each leaf label occurs at most twice in a phylogenetic tree N, then the problem can be solved in polynomial time and if labels can occur up to three times, then the problem becomes NP-hard. Lastly, Reachable Object is the problem of deciding whether there is a sequence of rational trades of objects among agents such that a given agent can obtain a certain object. A rational trade is a swap of objects between two agents where both agents profit from the swap, that is, they receive objects they prefer over the objects they trade away. This problem can be seen as a natural generalization of the well-known and well-studied Housing Market problem where the agents are arranged in a graph and only neighboring agents can trade objects. We prove a dichotomy result that states that the problem is polynomial-time solvable if each agent prefers at most two objects over its initially held object and it is NP-hard if each agent prefers at most three objects over its initially held object. We also provide a polynomial-time 2-SAT program for the case where the graph of agents is a cycle.

The efficient and fair distribution of indivisible resources among agents is a common problem in the field of \emph{Multi-Agent-Systems}. We consider a graph-based version of this problem called Reachable Assignments, introduced by Gourves, Lesca, and Wilczynski [AAAI, 2017]. The input for this problem consists of a set of agents, a set of objects, the agent's preferences over the objects, a graph with the agents as vertices and edges encoding which agents can trade resources with each other, and an initial and a target distribution of the objects, where each agent owns exactly one object in each distribution. The question is then whether the target distribution is reachable via a sequence of rational trades. A trade is rational when the two participating agents are neighbors in the graph and both obtain an object they prefer over the object they previously held. We show that Reachable Assignments is NP-hard even when restricting the input graph to be a clique and develop an $O(n^3)$-time algorithm for the case where the input graph is a cycle with $n$ vertices.

This is the technical report for the Isabelle/HOL formalization accompanying the dissertation of Nils Berg. For explanations with regard to content please refer to the dissertation. The intention of this document is to give a mapping from the formalization in the dissertation to the formalization in Isabelle/HOL. Formalized are the parts where user interaction is required, i.e., the first part of the dissertation, where Communicating Sequential Processes (CSP) processes and Communicating Unstructured Code (CUC) programs are related. More specifically, the sections 5.2 to 5.5 of the dissertation are formalized.

Node connectivity plays a central role in temporal network analysis. We provide a comprehensive study of various concepts of walks in temporal graphs, that is, graphs with fixed vertex sets but edge sets changing over time. Taking into account the temporal aspect leads to a rich set of optimization criteria for "shortest" walks. Extending and significantly broadening state-of-the-art work of Wu et al. [IEEE TKDE 2016], we provide an algorithm for computing optimal walks that is capable to deal with various optimization criteria and any linear combination of these. It runs in $O (|V| + |E| \log |E|)$ time where $|V|$ is the number of vertices and $|E|$ is the number of time edges. A central distinguishing factor to Wu et al.'s work is that our model allows to, motivated by real-world applications, respect waiting-time constraints for vertices, that is, the minimum and maximum waiting time allowed in intermediate vertices of a walk. Moreover, other than Wu et al. our algorithm also allows to search for walks that pass multiple subsequent edges in one time step, and it can optimize a richer set of optimization criteria. Our experimental studies indicate that our richer modeling can be achieved without significantly worsening the running time when compared to Wu et al.'s algorithms.