Loading…
Parameterized algorithmics for time-evolving structures: temporalizing and multistaging
Zschoche, Philipp
The thesis studies temporal graph problems and multistage problems. Since these problems typically are computationally hard, the focus is on developing fast exact (FPT-)algorithms.
Temporal graph problems. A temporal graph is a graph whose edge set changes over time. Here, an edge at a specific time step is called time-edge. One of our main contributions is the introduction of a set of parameters tailored for temporal graph problems. We focus mainly on four problems on temporal graphs.
Minimizing Reachability by Delaying. Given a temporal graph, a set of source vertices, and three integers k, r, and δ, the problem Minimizing Temporal Reachability by Delaying asks whether we can delay at most k time-edges by δ time steps (i.e., moving the edges δ time steps into the future) such that the sources can reach at most r vertices via temporal paths (i.e., paths using edges appearing in non-decreasing time-order). Our main contribution here is an algorithm running in O(r!k|G|) time, where |G| is the size of the temporal graph. This stands in contrast to the W[1]-hardness when parameterized by r for the problem of deleting instead of delaying time-edges.
Restless Temporal Paths. A restless temporal path is a temporal path that can stay only a bounded amount of time at one vertex. Our main contribution here is a randomized algorithm to find a length-at-most-k restless temporal path from vertex s to vertex z in 4^ℓ |G|^O(1) time, where ℓ is the difference between k and the length of the shortest temporal path from s to z. Moreover, we show that finding these restless temporal paths is fixed-parameter tractable when parameterized by the timed feedback vertex number (that is, a temporal version of the classical feedback vertex number introduced in this thesis). This stands in contrast to the W[1]-hardness when parameterized by the feedback vertex number of the underlying graph.
Temporal Separation. A temporal separator is a vertex set that intersects the vertices of all temporal paths between two distinguished vertices. We contribute two algorithms to find minimum temporal separators. The first algorithm runs in ω^ω |G|^O(1) time, where ω is the temporal core size—another parameter for temporal graphs introduced here. The second algorithm runs in 4^x |G|^O(1) time, where x is the timed feedback vertex number. This stands in contrast to the W[1]-hardness when parameterized by the feedback vertex number of the underlying graph.
Temporal Matching. A δ-temporal matching in a temporal graph is a set of time-edges such that two distinct time-edges either do not share an endpoint or they are at least δ time steps apart. We present two algorithms to find δ-temporal matchings of size k. The first algorithm runs in O((2k − 1)^k |G|) time. Previously, only the fixed-parameter tractability for k + δ was known due to kernelization. The second algorithm runs in δ^O(ν) |G| time, where ν is the δ-vertex cover number—another new parameter we introduce here.
Multistage problems. Many problems need not only be solved once but repeatedly, under changing conditions. This setting is addressed by the “multistage” view on computational problems, where the input contains a sequence of instances of a computational problem, and we are asked to find a sequence of solutions (one for each instance) under (dis)similarity constraints. We study two different variants.
First, we study a “diverse multistage” variant, where consecutive solutions shall differ by at least ℓ elements, e.g., for reasons of fairness or wear minimization. We introduce a general framework allowing to prove that several diverse multistage problems are fixed-parameter tractable when parameterized by ℓ, namely Perfect Matching, s-t Path, and Plurality Voting.
Second, we study Multistage Vertex Cover—a (non-diverse) “multistage” variant of Vertex Cover where we are given a sequence of instances of Vertex Cover, all instances asking for a vertex cover of size at most k. In contrast to the diverse multistage variant, consecutive vertex covers shall differ by at most ℓ vertices. In general, this multistage variant is motivated by scenarios where the adaptation of the current solution generates reconfiguration costs which shall not exceed ℓ. We show that Multistage Vertex Cover parameterized by k is W[1]-hard, already when ℓ = 2.
Die Arbeit untersucht temporale Graphenprobleme und mehrstufige Probleme. Da diese Probleme typischerweise berechnungsschwer sind, liegt der Schwerpunkt auf der Entwicklung schneller, exakter (FPT-)Algorithmen.
Temporale Graphenprobleme. Ein temporaler Graph ist ein Graph, dessen Kantenmenge sich im Laufe der Zeit verändert. Dabei wird eine Kante zu einem bestimmten Zeitpunkt als Zeitkante bezeichnet. Einer der wichtigsten Beiträge dieser Arbeit ist die Einführung einer Reihe von Parametern für temporale Graphenprobleme. Wir konzentrieren uns hauptsächlich auf vier temporale Graphenprobleme.
Minimierung der Erreichbarkeit durch Verzögern. Gegeben ein temporaler Graph, eine Menge von Quellknoten und drei natürliche Zahlen k, r und δ, so fragt das Problem Minimierung der temporalen Erreichbarkeit durch Verzögern, ob wir höchstens k Zeitkanten um δ verzögern (d. h. die Zeitkante um δ Zeitschritte in die Zukunft verschieben) können, so dass die Quellen höchstens r Knoten über temporale Pfade erreichen können (d. h. Pfade mit Kanten, die in nicht abnehmender zeitlicher Reihenfolge auftreten). Hier ist unser Hauptbeitrag ein Algorithmus mit einer Laufzeit von O(r!k|G|), wobei |G| die Größe des temporalen Graphen ist. Dies steht im Gegensatz zu der W[1]-Schwere mit Parameter r, wenn wir Zeitkanten löschen statt verzögern.
Rastlose temporale Pfade. Ein rastloser temporaler Pfad ist ein temporaler Pfad, der nur eine begrenzte Zeit an einem Knoten verweilen kann. Unser Hauptbeitrag ist ein randomisierter Algorithmus zum Finden eines rastlosen temporalen Pfades der Länge höchstens k von einem Knoten s zu einem Knoten z mit einer Laufzeit von 4^ℓ |G|^O(1) , wobei ℓ die Differenz zwischen k und der Länge eines kürzesten temporalen Pfades von s nach z ist. Außerdem zeigen wir, dass das Finden dieser rastlosen temporalen Pfade in FPT liegt, wenn das Problem mit der temporalen kreiskritischen Knotenzahl (das ist eine temporale Version der klassischen kreiskritischen Knotenzahl, die in dieser Arbeit eingeführt wird) parametrisiert wird. Dies steht im Gegensatz zu der W[1]-Schwere, wenn das Problem mit der kreiskritischen Knotenzahl des zugrundeliegenden Graphen parametrisiert wird.
Temporale Trennung. Ein temporaler Trenner ist eine Knotenmenge, die die die Knotenmenge aller zeitlichen Pfade zwischen zwei bestimmten Knoten schneidet. Wir präsentieren zwei Algorithmen, um minimale temporale Trenner zu finden. Der erste Algorithmus hat eine Laufzeit von ω^ω |G|^O(1) , wobei ω die temporale Kerngröße ist – ein weiterer hier eingeführter Parameter für temporale Graphen. Der zweite Algorithmus hat eine Laufzeit von 4^x |G|^O(1) , wobei x die temporale kreiskritische Knotenzahl ist. Dies steht im Gegensatz zur der W[1]-Schwere, wenn das Problem mit der kreiskritischen Knotenzahl des zugrundeliegenden Graphen parametrisiert wird.
Temporale Paarung. Ein δ-temporale Paarung in einem temporalen Graphen ist eine Menge von Zeitkanten, in der zwei unterschiedliche Zeitkanten entweder keinen gemeinsamen Endpunkt haben oder mindestens δ Zeitschritte voneinander entfernt sind. Wir entwickeln zwei Algorithmen, um δ-temporale Paarungen der Größe k zu finden. Der erste Algorithmus hat eine Laufzeit von O((2k − 1)^k |G|). Bislang war nur bekannt, dass dieses Problem in FPT liegt, wenn es mit k + δ parametrisiert wird. Der zweite Algorithmus hat eine Laufzeit von δ^O(ν) |G|, wobei ν die δ-Knotenüberdeckungszahl ist – ein weiterer neuer Parameter, der hier eingeführt wird.
Mehrstufige Probleme. Viele Probleme müssen nicht nur einmal gelöst werden, sondern öfter und unter wechselnden Bedingungen. Dieser Umstand wird durch die „mehrstufige“ Betrachtung von Problemen adressiert, wobei die Eingabe eine Sequenz von Instanzen eines Problems enthält und wir nach einer Sequenz von Lösungen (für jede Instanz eine) unter (Un-)Ähnlichkeitsbeschränkungen suchen. Wir untersuchen zwei verschiedene Varianten.
Erstens untersuchen wir eine „diverse mehrstufige“ Variante, bei der sich aufeinanderfolgende Lösungen um mindestens ℓ Elemente unterscheiden, z. B. aus Gründen der Gerechtigkeit oder der Verschleißminimierung. Wir führen ein allgemeines Werkzeug ein, welches erlaubt zu beweisen, dass mehrere diverse mehrstufige Probleme in FPT liegen, wenn sie mit ℓ parametrisiert werden. Wir wenden das Werkzeug für die Probleme Perfekte Paarung, s-t Pfad und Pluralitätsabstimmung an.
Zweitens untersuchen wir die Mehrstufige Knotenüberdeckung – eine (nicht-diverse) „mehrstufige“ Variante von der Knotenüberdeckung, wobei alle Instanzen nach einer Knotenüberdeckung der Größe höchstens k fragen. Im Gegensatz zu der diversen mehrstufigen Variante dürfen aufeinanderfolgende Knotenüberdeckungen sich um höchstens ℓ Knoten unterscheiden. Im Allgemeinen ist diese mehrstufige Variante motiviert durch Szenarien, in denen die Anpassung der aktuellen Lösung Rekonfigurationskosten verursacht, die ℓ nicht überschreiten dürfen. Wir zeigen, dass Mehrstufige Knotenüberdeckung W[1]-schwer ist, wenn es mit k parametrisiert wird, selbst wenn ℓ = 2 gilt.
