Search Results

Documents authored by Zschoche, Philipp

Document
DOI: 10.4230/LIPIcs.STACS.2023.55
Restless Temporal Path Parameterized Above Lower Bounds

Authors: Philipp Zschoche

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
Reachability questions are one of the most fundamental algorithmic primitives in temporal graphs - graphs whose edge set changes over discrete time steps. A core problem here is the NP-hard Short Restless Temporal Path: given a temporal graph G, two distinct vertices s and z, and two numbers δ and k, is there a δ-restless temporal s-z path of length at most k? A temporal path is a path whose edges appear in chronological order and a temporal path is δ-restless if two consecutive path edges appear at most δ time steps apart from each other. Among others, this problem has applications in neuroscience and epidemiology. While Short Restless Temporal Path is known to be computationally hard, e.g., it is NP-hard even if the temporal graph consists of three discrete time steps and it is W[1]-hard when parameterized by the feedback vertex number of the underlying graph, it is fixed-parameter tractable when parameterized by the path length k. We improve on this by showing that Short Restless Temporal Path can be solved in (randomized) 4^(k-d)|G|^O(1) time, where d is the minimum length of a temporal s-z path.
Cite as

Philipp Zschoche. Restless Temporal Path Parameterized Above Lower Bounds. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{zschoche:LIPIcs.STACS.2023.55,
  author =	{Zschoche, Philipp},
  title =	{{Restless Temporal Path Parameterized Above Lower Bounds}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{55:1--55:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.55},
  URN =		{urn:nbn:de:0030-drops-177077},
  doi =		{10.4230/LIPIcs.STACS.2023.55},
  annote =	{Keywords: temporal graphs, FPT, above-lower-bound parameterization}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.26
The PACE 2021 Parameterized Algorithms and Computational Experiments Challenge: Cluster Editing

Authors: Leon Kellerhals, Tomohiro Koana, André Nichterlein, and Philipp Zschoche

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
The Parameterized Algorithms and Computational Experiments challenge (PACE) 2021 was devoted to engineer algorithms solving the NP-hard Cluster Editing problem, also known as Correlation Clustering: Given an undirected graph the task is to compute a minimum number of edges to insert or remove in a way that the resulting graph is a cluster graph, that is, a graph in which each connected component is a clique. Altogether 67 participants from 21 teams, 11 countries, and 3 continents submitted their implementations to the competition. In this report, we describe the setup of the challenge, the selection of benchmark instances, and the ranking of the participating teams. We also briefly discuss the approaches used in the submitted solvers.
Cite as

Leon Kellerhals, Tomohiro Koana, André Nichterlein, and Philipp Zschoche. The PACE 2021 Parameterized Algorithms and Computational Experiments Challenge: Cluster Editing. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kellerhals_et_al:LIPIcs.IPEC.2021.26,
  author =	{Kellerhals, Leon and Koana, Tomohiro and Nichterlein, Andr\'{e} and Zschoche, Philipp},
  title =	{{The PACE 2021 Parameterized Algorithms and Computational Experiments Challenge: Cluster Editing}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.26},
  URN =		{urn:nbn:de:0030-drops-154096},
  doi =		{10.4230/LIPIcs.IPEC.2021.26},
  annote =	{Keywords: Correlation Clustering, Cluster Editing, Algorithm Engineering, FPT, Kernelization, Heuristics}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.55
Parameterized Algorithms for Diverse Multistage Problems

Authors: Leon Kellerhals, Malte Renken, and Philipp Zschoche

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
The world is rarely static - many problems need not only be solved once but repeatedly, under changing conditions. This setting is addressed by the multistage view on computational problems. We study the diverse multistage variant, where consecutive solutions of large variety are preferable to similar ones, e.g. for reasons of fairness or wear minimization. While some aspects of this model have been tackled before, we introduce a framework allowing us to prove that a number of diverse multistage problems are fixed-parameter tractable by diversity, namely Perfect Matching, s-t Path, Matroid Independent Set, and Plurality Voting. This is achieved by first solving special, colored variants of these problems, which might also be of independent interest.
Cite as

Leon Kellerhals, Malte Renken, and Philipp Zschoche. Parameterized Algorithms for Diverse Multistage Problems. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kellerhals_et_al:LIPIcs.ESA.2021.55,
  author =	{Kellerhals, Leon and Renken, Malte and Zschoche, Philipp},
  title =	{{Parameterized Algorithms for Diverse Multistage Problems}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{55:1--55:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.55},
  URN =		{urn:nbn:de:0030-drops-146360},
  doi =		{10.4230/LIPIcs.ESA.2021.55},
  annote =	{Keywords: Temporal graphs, dissimilar solutions, fixed-parameter tractability, perfect matchings, s-t paths, committee election, spanning forests, matroids}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.75
The Complexity of Transitively Orienting Temporal Graphs

Authors: George B. Mertzios, Hendrik Molter, Malte Renken, Paul G. Spirakis, and Philipp Zschoche

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
In a temporal network with discrete time-labels on its edges, entities and information can only "flow" along sequences of edges whose time-labels are non-decreasing (resp. increasing), i.e. along temporal (resp. strict temporal) paths. Nevertheless, in the model for temporal networks of [Kempe, Kleinberg, Kumar, JCSS, 2002], the individual time-labeled edges remain undirected: an edge e = {u,v} with time-label t specifies that "u communicates with v at time t". This is a symmetric relation between u and v, and it can be interpreted that the information can flow in either direction. In this paper we make a first attempt to understand how the direction of information flow on one edge can impact the direction of information flow on other edges. More specifically, naturally extending the classical notion of a transitive orientation in static graphs, we introduce the fundamental notion of a temporal transitive orientation and we systematically investigate its algorithmic behavior in various situations. An orientation of a temporal graph is called temporally transitive if, whenever u has a directed edge towards v with time-label t₁ and v has a directed edge towards w with time-label t₂ ≥ t₁, then u also has a directed edge towards w with some time-label t₃ ≥ t₂. If we just demand that this implication holds whenever t₂ > t₁, the orientation is called strictly temporally transitive, as it is based on the fact that there is a strict directed temporal path from u to w. Our main result is a conceptually simple, yet technically quite involved, polynomial-time algorithm for recognizing whether a given temporal graph 𝒢 is transitively orientable. In wide contrast we prove that, surprisingly, it is NP-hard to recognize whether 𝒢 is strictly transitively orientable. Additionally we introduce and investigate further related problems to temporal transitivity, notably among them the temporal transitive completion problem, for which we prove both algorithmic and hardness results.
Cite as

George B. Mertzios, Hendrik Molter, Malte Renken, Paul G. Spirakis, and Philipp Zschoche. The Complexity of Transitively Orienting Temporal Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 75:1-75:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mertzios_et_al:LIPIcs.MFCS.2021.75,
  author =	{Mertzios, George B. and Molter, Hendrik and Renken, Malte and Spirakis, Paul G. and Zschoche, Philipp},
  title =	{{The Complexity of Transitively Orienting Temporal Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{75:1--75:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.75},
  URN =		{urn:nbn:de:0030-drops-145157},
  doi =		{10.4230/LIPIcs.MFCS.2021.75},
  annote =	{Keywords: Temporal graph, transitive orientation, transitive closure, polynomial-time algorithm, NP-hardness, satisfiability}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.76
Temporal Reachability Minimization: Delaying vs. Deleting

Authors: Hendrik Molter, Malte Renken, and Philipp Zschoche

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We study spreading processes in temporal graphs, i. e., graphs whose connections change over time. These processes naturally model real-world phenomena such as infectious diseases or information flows. More precisely, we investigate how such a spreading process, emerging from a given set of sources, can be contained to a small part of the graph. To this end we consider two ways of modifying the graph, which are (1) deleting connections and (2) delaying connections. We show a close relationship between the two associated problems and give a polynomial time algorithm when the graph has tree structure. For the general version, we consider parameterization by the number of vertices to which the spread is contained. Surprisingly, we prove W[1]-hardness for the deletion variant but fixed-parameter tractability for the delaying variant.
Cite as

Hendrik Molter, Malte Renken, and Philipp Zschoche. Temporal Reachability Minimization: Delaying vs. Deleting. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 76:1-76:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{molter_et_al:LIPIcs.MFCS.2021.76,
  author =	{Molter, Hendrik and Renken, Malte and Zschoche, Philipp},
  title =	{{Temporal Reachability Minimization: Delaying vs. Deleting}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{76:1--76:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.76},
  URN =		{urn:nbn:de:0030-drops-145161},
  doi =		{10.4230/LIPIcs.MFCS.2021.76},
  annote =	{Keywords: Temporal Graphs, Temporal Paths, Disease Spreading, Network Flows, Parameterized Algorithms, NP-hard Problems}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.26
Using a Geometric Lens to Find k Disjoint Shortest Paths

Authors: Matthias Bentert, André Nichterlein, Malte Renken, and Philipp Zschoche

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Given an undirected n-vertex graph and k pairs of terminal vertices (s_1,t_1), …, (s_k,t_k), the k-Disjoint Shortest Paths (k-DSP) problem asks whether there are k pairwise vertex-disjoint paths P_1, …, P_k such that P_i is a shortest s_i-t_i-path for each i ∈ [k]. Recently, Lochet [SODA '21] provided an algorithm that solves k-DSP in n^{O(k^{5^k})} time, answering a 20-year old question about the computational complexity of k-DSP for constant k. On the one hand, we present an improved O(kn^{16k ⋅ k! + k + 1})-time algorithm based on a novel geometric view on this problem. For the special case k = 2, we show that the running time can be further reduced to O(nm) by small modifications of the algorithm and a further refined analysis. On the other hand, we show that k-DSP is W[1]-hard with respect to k, showing that the dependency of the degree of the polynomial running time on the parameter k is presumably unavoidable.
Cite as

Matthias Bentert, André Nichterlein, Malte Renken, and Philipp Zschoche. Using a Geometric Lens to Find k Disjoint Shortest Paths. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.ICALP.2021.26,
  author =	{Bentert, Matthias and Nichterlein, Andr\'{e} and Renken, Malte and Zschoche, Philipp},
  title =	{{Using a Geometric Lens to Find k Disjoint Shortest Paths}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.26},
  URN =		{urn:nbn:de:0030-drops-140954},
  doi =		{10.4230/LIPIcs.ICALP.2021.26},
  annote =	{Keywords: graph algorithms, dynamic programming, W\lbrack1\rbrack-hardness, geometry}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.30
Finding Temporal Paths Under Waiting Time Constraints

Authors: Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration Δ, referred to as Δ-restless temporal paths. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the "restless variant" of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the feedback vertex number or the pathwidth of the underlying graph. The main question thus is whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work.
Cite as

Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, and Philipp Zschoche. Finding Temporal Paths Under Waiting Time Constraints. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{casteigts_et_al:LIPIcs.ISAAC.2020.30,
  author =	{Casteigts, Arnaud and Himmel, Anne-Sophie and Molter, Hendrik and Zschoche, Philipp},
  title =	{{Finding Temporal Paths Under Waiting Time Constraints}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{30:1--30:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.30},
  URN =		{urn:nbn:de:0030-drops-133745},
  doi =		{10.4230/LIPIcs.ISAAC.2020.30},
  annote =	{Keywords: Temporal graphs, disease spreading, waiting-time policies, restless temporal paths, timed feedback vertex set, NP-hard problems, parameterized algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.43
Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs

Authors: Till Fluschnik, Rolf Niedermeier, Carsten Schubert, and Philipp Zschoche

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Addressing a quest by Gupta et al. [ICALP'14], we provide a first, comprehensive study of finding a short s-t path in the multistage graph model, referred to as the Multistage s-t Path problem. Herein, given a sequence of graphs over the same vertex set but changing edge sets, the task is to find short s-t paths in each graph ("snapshot") such that in the found path sequence the consecutive s-t paths are "similar". We measure similarity by the size of the symmetric difference of either the vertex set (vertex-similarity) or the edge set (edge-similarity) of any two consecutive paths. We prove that these two variants of Multistage s-t Path are already NP-hard for an input sequence of only two graphs and maximum vertex degree four. Motivated by this fact and natural applications of this scenario e.g. in traffic route planning, we perform a parameterized complexity analysis. Among other results, for both variants, vertex- and edge-similarity, we prove parameterized hardness (W[1]-hardness) regarding the parameter path length (solution size) for both variants, vertex- and edge-similarity. As a further conceptual study, we then modify the multistage model by asking for dissimilar consecutive paths. One of our main technical results (employing so-called representative sets known from non-temporal settings) is that dissimilarity allows for fixed-parameter tractability for the parameter solution size, contrasting the W[1]-hardness of the corresponding similarity case. We also provide partially positive results concerning efficient and effective data reduction (kernelization).
Cite as

Till Fluschnik, Rolf Niedermeier, Carsten Schubert, and Philipp Zschoche. Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fluschnik_et_al:LIPIcs.ISAAC.2020.43,
  author =	{Fluschnik, Till and Niedermeier, Rolf and Schubert, Carsten and Zschoche, Philipp},
  title =	{{Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.43},
  URN =		{urn:nbn:de:0030-drops-133879},
  doi =		{10.4230/LIPIcs.ISAAC.2020.43},
  annote =	{Keywords: Temporal graphs, shortest paths, consecutive similarity, consecutive dissimilarity, parameterized complexity, kernelization, representative sets in temporal graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.27
Computing Maximum Matchings in Temporal Graphs

Authors: George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Temporal graphs are graphs whose topology is subject to discrete changes over time. Given a static underlying graph G, a temporal graph is represented by assigning a set of integer time-labels to every edge e of G, indicating the discrete time steps at which e is active. We introduce and study the complexity of a natural temporal extension of the classical graph problem Maximum Matching, taking into account the dynamic nature of temporal graphs. In our problem, Maximum Temporal Matching, we are looking for the largest possible number of time-labeled edges (simply time-edges) (e,t) such that no vertex is matched more than once within any time window of Δ consecutive time slots, where Δ ∈ ℕ is given. The requirement that a vertex cannot be matched twice in any Δ-window models some necessary "recovery" period that needs to pass for an entity (vertex) after being paired up for some activity with another entity. We prove strong computational hardness results for Maximum Temporal Matching, even for elementary cases. To cope with this computational hardness, we mainly focus on fixed-parameter algorithms with respect to natural parameters, as well as on polynomial-time approximation algorithms.
Cite as

George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche. Computing Maximum Matchings in Temporal Graphs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{mertzios_et_al:LIPIcs.STACS.2020.27,
  author =	{Mertzios, George B. and Molter, Hendrik and Niedermeier, Rolf and Zamaraev, Viktor and Zschoche, Philipp},
  title =	{{Computing Maximum Matchings in Temporal Graphs}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.27},
  URN =		{urn:nbn:de:0030-drops-118881},
  doi =		{10.4230/LIPIcs.STACS.2020.27},
  annote =	{Keywords: Temporal Graph, Link Stream, Temporal Line Graph, NP-hardness, APX-hardness, Approximation Algorithm, Fixed-parameter Tractability, Independent Set}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.14
Multistage Vertex Cover

Authors: Till Fluschnik, Rolf Niedermeier, Valentin Rohm, and Philipp Zschoche

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
Covering all edges of a graph by a small number of vertices, this is the NP-hard Vertex Cover problem, is among the most fundamental algorithmic tasks. Following a recent trend in studying dynamic and temporal graphs, we initiate the study of Multistage Vertex Cover. Herein, having a series of graphs with same vertex set but over time changing edge sets (known as temporal graph consisting of time layers), the goal is to find for each layer of the temporal graph a small vertex cover and to guarantee that the two vertex cover sets between two subsequent layers differ not too much (specified by a given parameter). We show that, different from classic Vertex Cover and some other dynamic or temporal variants of it, Multistage Vertex Cover is computationally hard even in fairly restricted settings. On the positive side, however, we also spot several fixed-parameter tractability results based on some of the most natural parameterizations.
Cite as

Till Fluschnik, Rolf Niedermeier, Valentin Rohm, and Philipp Zschoche. Multistage Vertex Cover. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fluschnik_et_al:LIPIcs.IPEC.2019.14,
  author =	{Fluschnik, Till and Niedermeier, Rolf and Rohm, Valentin and Zschoche, Philipp},
  title =	{{Multistage Vertex Cover}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.14},
  URN =		{urn:nbn:de:0030-drops-114753},
  doi =		{10.4230/LIPIcs.IPEC.2019.14},
  annote =	{Keywords: NP-hardness, dynamic graph problems, temporal graphs, time-evolving networks, W\lbrack1\rbrack-hardness, fixed-parameter tractability, kernelization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.45
The Complexity of Finding Small Separators in Temporal Graphs

Authors: Philipp Zschoche, Till Fluschnik, Hendrik Molter, and Rolf Niedermeier

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Temporal graphs are graphs with time-stamped edges. We study the problem of finding a small vertex set (the separator) with respect to two designated terminal vertices such that the removal of the set eliminates all temporal paths connecting one terminal to the other. Herein, we consider two models of temporal paths: paths that pass through arbitrarily many edges per time step (non-strict) and paths that pass through at most one edge per time step (strict). Regarding the number of time steps of a temporal graph, we show a complexity dichotomy (NP-hardness versus polynomial-time solvability) for both problem variants. Moreover we prove both problem variants to be NP-complete even on temporal graphs whose underlying graph is planar. We further show that, on temporal graphs with planar underlying graph, if additionally the number of time steps is constant, then the problem variant for strict paths is solvable in quasi-linear time. Finally, we introduce and motivate the notion of a temporal core (vertices whose incident edges change over time). We prove that the non-strict variant is fixed-parameter tractable when parameterized by the size of the temporal core, while the strict variant remains NP-complete, even for constant-size temporal cores.
Cite as

Philipp Zschoche, Till Fluschnik, Hendrik Molter, and Rolf Niedermeier. The Complexity of Finding Small Separators in Temporal Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 45:1-45:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{zschoche_et_al:LIPIcs.MFCS.2018.45,
  author =	{Zschoche, Philipp and Fluschnik, Till and Molter, Hendrik and Niedermeier, Rolf},
  title =	{{The Complexity of Finding Small Separators in Temporal Graphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{45:1--45:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.45},
  URN =		{urn:nbn:de:0030-drops-96277},
  doi =		{10.4230/LIPIcs.MFCS.2018.45},
  annote =	{Keywords: (non-)strict temporal paths, temporal core, single-source shortest paths, node multiway cut, length-bounded cuts, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.53
Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments

Authors: Viatcheslav Korenwein, André Nichterlein, Rolf Niedermeier, and Philipp Zschoche

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
Finding a maximum-cardinality or maximum-weight matching in (edge-weighted) undirected graphs is among the most prominent problems of algorithmic graph theory. For n-vertex and m-edge graphs, the best known algorithms run in O~(m sqrt{n}) time. We build on recent theoretical work focusing on linear-time data reduction rules for finding maximum-cardinality matchings and complement the theoretical results by presenting and analyzing (thereby employing the kernelization methodology of parameterized complexity analysis) linear-time data reduction rules for the positive-integer-weighted case. Moreover, we experimentally demonstrate that these data reduction rules provide significant speedups of the state-of-the art implementation for computing matchings in real-world graphs: the average speedup is 3800% in the unweighted case and "just" 30% in the weighted case.
Cite as

Viatcheslav Korenwein, André Nichterlein, Rolf Niedermeier, and Philipp Zschoche. Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 53:1-53:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{korenwein_et_al:LIPIcs.ESA.2018.53,
  author =	{Korenwein, Viatcheslav and Nichterlein, Andr\'{e} and Niedermeier, Rolf and Zschoche, Philipp},
  title =	{{Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{53:1--53:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.53},
  URN =		{urn:nbn:de:0030-drops-95169},
  doi =		{10.4230/LIPIcs.ESA.2018.53},
  annote =	{Keywords: Maximum-cardinality matching, maximum-weight matching, linear-time algorithms, preprocessing, kernelization, parameterized complexity analysis}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact