252 Search Results for "Niedermeier, Rolf"


Volume

LIPIcs, Volume 126

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

STACS 2019, March 13-16, 2019, Berlin, Germany

Editors: Rolf Niedermeier and Christophe Paul

Volume

LIPIcs, Volume 96

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

STACS 2018, February 28 to March 3, 2018, Caen, France

Editors: Rolf Niedermeier and Brigitte Vallée

Volume

LIPIcs, Volume 58

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

MFCS 2016, August 22-26, 2016, Kraków, Poland

Editors: Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier

Document
Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions

Authors: Klaus Heeger, André Nichterlein, and Rolf Niedermeier

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


Abstract
We provide a general framework to exclude parameterized running times of the form O(l^β + n^γ) for problems that have polynomial running time lower bounds under hypotheses from fine-grained complexity. Our framework is based on cross-compositions from parameterized complexity. We (conditionally) exclude running times of the form O(l^{γ/(γ-1) - ε} + n^γ) for any 1 < γ < 2 and ε > 0 for the following problems: - Longest Common (Increasing) Subsequence: Given two length-n strings over an alphabet Σ (over ℕ) and l ∈ ℕ, is there a common (increasing) subsequence of length l in both strings? - Discrete Fréchet Distance: Given two lists of n points each and k ∈ N, is the Fréchet distance of the lists at most k? Here l is the maximum number of points which one list is ahead of the other list in an optimum traversal. - Planar Motion Planning: Given a set of n non-intersecting axis-parallel line segment obstacles in the plane and a line segment robot (called rod), can the rod be moved to a specified target without touching any obstacles? Here l is the maximum number of segments any segment has in its vicinity. Moreover, we exclude running times O(l^{2γ/(γ-1) - ε} + n^γ) for any 1 < γ < 3 and ε > 0 for: - Negative Triangle: Given an edge-weighted graph with n vertices, is there a triangle whose sum of edge-weights is negative? Here l is the order of a maximum connected component. - Triangle Collection: Given a vertex-colored graph with n vertices, is there for each triple of colors a triangle whose vertices have these three colors? Here l is the order of a maximum connected component. - 2nd Shortest Path: Given an n-vertex edge-weighted digraph, vertices s and t, and k ∈ ℕ, has the second longest s-t-path length at most k? Here l is the directed feedback vertex set number. Except for 2nd Shortest Path all these running time bounds are tight, that is, algorithms with running time O(l^{γ/(γ-1)} + n^γ) for any 1 < γ < 2 and O(l^{2γ/(γ -1)} + n^γ) for any 1 < γ < 3, respectively, are known. Our running time lower bounds also imply lower bounds on kernelization algorithms for these problems.

Cite as

Klaus Heeger, André Nichterlein, and Rolf Niedermeier. Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{heeger_et_al:LIPIcs.STACS.2023.35,
  author =	{Heeger, Klaus and Nichterlein, Andr\'{e} and Niedermeier, Rolf},
  title =	{{Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{35:1--35:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.35},
  URN =		{urn:nbn:de:0030-drops-176876},
  doi =		{10.4230/LIPIcs.STACS.2023.35},
  annote =	{Keywords: FPT in P, Kernelization, Decomposition}
}
Document
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-dev.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
Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time

Authors: Hjalmar Schulz, André Nichterlein, Rolf Niedermeier, and Christopher Weyand

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)


Abstract
Given an undirected graph, the task in Cluster Editing is to insert and delete a minimum number of edges to obtain a cluster graph, that is, a disjoint union of cliques. In the weighted variant each vertex pair comes with a weight and the edge modifications have to be of minimum overall weight. In this work, we provide the first polynomial-time algorithm to apply the following data reduction rule of Böcker et al. [Algorithmica, 2011] for Weighted Cluster Editing: For a graph G = (V,E), merge a vertex set S ⊆ V into a single vertex if the minimum cut of G[S] is at least the combined cost of inserting all missing edges within G[S] plus the cost of cutting all edges from S to the rest of the graph. Complementing our theoretical findings, we experimentally demonstrate the effectiveness of the data reduction rule, shrinking real-world test instances from the PACE Challenge 2021 by around 24% while previous heuristic implementations of the data reduction rule only achieve 8%.

Cite as

Hjalmar Schulz, André Nichterlein, Rolf Niedermeier, and Christopher Weyand. Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{schulz_et_al:LIPIcs.IPEC.2022.25,
  author =	{Schulz, Hjalmar and Nichterlein, Andr\'{e} and Niedermeier, Rolf and Weyand, Christopher},
  title =	{{Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.25},
  URN =		{urn:nbn:de:0030-drops-173816},
  doi =		{10.4230/LIPIcs.IPEC.2022.25},
  annote =	{Keywords: Correlation Clustering, Minimum Cut, Maximum s-t-Flow}
}
Document
There and Back Again: On Applying Data Reduction Rules by Undoing Others

Authors: Aleksander Figiel, Vincent Froese, André Nichterlein, and Rolf Niedermeier

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)


Abstract
Data reduction rules are an established method in the algorithmic toolbox for tackling computationally challenging problems. A data reduction rule is a polynomial-time algorithm that, given a problem instance as input, outputs an equivalent, typically smaller instance of the same problem. The application of data reduction rules during the preprocessing of problem instances allows in many cases to considerably shrink their size, or even solve them directly. Commonly, these data reduction rules are applied exhaustively and in some fixed order to obtain irreducible instances. It was often observed that by changing the order of the rules, different irreducible instances can be obtained. We propose to "undo" data reduction rules on irreducible instances, by which they become larger, and then subsequently apply data reduction rules again to shrink them. We show that this somewhat counter-intuitive approach can lead to significantly smaller irreducible instances. The process of undoing data reduction rules is not limited to "rolling back" data reduction rules applied to the instance during preprocessing. Instead, we formulate so-called backward rules, which essentially undo a data reduction rule, but without using any information about which data reduction rules were applied to it previously. In particular, based on the example of Vertex Cover we propose two methods applying backward rules to shrink the instances further. In our experiments we show that this way smaller irreducible instances consisting of real-world graphs from the SNAP and DIMACS datasets can be computed.

Cite as

Aleksander Figiel, Vincent Froese, André Nichterlein, and Rolf Niedermeier. There and Back Again: On Applying Data Reduction Rules by Undoing Others. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{figiel_et_al:LIPIcs.ESA.2022.53,
  author =	{Figiel, Aleksander and Froese, Vincent and Nichterlein, Andr\'{e} and Niedermeier, Rolf},
  title =	{{There and Back Again: On Applying Data Reduction Rules by Undoing Others}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{53:1--53:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.53},
  URN =		{urn:nbn:de:0030-drops-169914},
  doi =		{10.4230/LIPIcs.ESA.2022.53},
  annote =	{Keywords: Kernelization, Preprocessing, Vertex Cover}
}
Document
Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems

Authors: Niclas Boehmer, Klaus Heeger, and Rolf Niedermeier

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)


Abstract
When computing stable matchings, it is usually assumed that the preferences of the agents in the matching market are fixed. However, in many realistic scenarios, preferences change over time. Consequently, an initially stable matching may become unstable. Then, a natural goal is to find a matching which is stable with respect to the modified preferences and as close as possible to the initial one. For Stable Marriage/Roommates, this problem was formally defined as Incremental Stable Marriage/Roommates by Bredereck et al. [AAAI '20]. As they showed that Incremental Stable Roommates and Incremental Stable Marriage with Ties are NP-hard, we focus on the parameterized complexity of these problems. We answer two open questions of Bredereck et al. [AAAI '20]: We show that Incremental Stable Roommates is W[1]-hard parameterized by the number of changes in the preferences, yet admits an intricate XP-algorithm, and we show that Incremental Stable Marriage with Ties is W[1]-hard parameterized by the number of ties. Furthermore, we analyze the influence of the degree of "similarity" between the agents' preference lists, identifying several polynomial-time solvable and fixed-parameter tractable cases, but also proving that Incremental Stable Roommates and Incremental Stable Marriage with Ties parameterized by the number of different preference lists are W[1]-hard.

Cite as

Niclas Boehmer, Klaus Heeger, and Rolf Niedermeier. Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{boehmer_et_al:LIPIcs.MFCS.2022.21,
  author =	{Boehmer, Niclas and Heeger, Klaus and Niedermeier, Rolf},
  title =	{{Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.21},
  URN =		{urn:nbn:de:0030-drops-168194},
  doi =		{10.4230/LIPIcs.MFCS.2022.21},
  annote =	{Keywords: Stable Marriage, Stable Roommates, adapting to changing preferences, NP-hardness, W\lbrack1\rbrack-hardness, XP, FPT, master lists, incremental algorithms}
}
Document
An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions

Authors: Laurent Bulteau, Mark Jones, Rolf Niedermeier, and Till Tantau

Published in: LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)


Abstract
In the NP-hard Longest Common Subsequence problem (LCS), given a set of strings, the task is to find a string that can be obtained from every input string using as few deletions as possible. LCS is one of the most fundamental string problems with numerous applications in various areas, having gained a lot of attention in the algorithms and complexity research community. Significantly improving on an algorithm by Irving and Fraser [CPM'92], featured as a research challenge in a 2014 survey paper, we show that LCS is fixed-parameter tractable (FPT) when parameterized by the maximum number of deletions per input string. Given the relatively moderate running time of our algorithm (linear time when the parameter is a constant) and small parameter values to be expected in several applications, we believe that our purely theoretical analysis could finally pave the way to a new, exact and practically useful algorithm for this notoriously hard string problem.

Cite as

Laurent Bulteau, Mark Jones, Rolf Niedermeier, and Till Tantau. An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 6:1-6:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bulteau_et_al:LIPIcs.CPM.2022.6,
  author =	{Bulteau, Laurent and Jones, Mark and Niedermeier, Rolf and Tantau, Till},
  title =	{{An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions}},
  booktitle =	{33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
  pages =	{6:1--6:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-234-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{223},
  editor =	{Bannai, Hideo and Holub, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.6},
  URN =		{urn:nbn:de:0030-drops-161338},
  doi =		{10.4230/LIPIcs.CPM.2022.6},
  annote =	{Keywords: NP-hard string problems, multiple sequence alignment, center string, parameterized complexity, search tree algorithms, enumerative algorithms}
}
Document
Most Classic Problems Remain NP-Hard on Relative Neighborhood Graphs and Their Relatives

Authors: Pascal Kunz, Till Fluschnik, Rolf Niedermeier, and Malte Renken

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)


Abstract
Proximity graphs have been studied for several decades, motivated by applications in computational geometry, geography, data mining, and many other fields. However, the computational complexity of classic graph problems on proximity graphs mostly remained open. We study 3-Colorability, Dominating Set, Feedback Vertex Set, Hamiltonian Cycle, and Independent Set on the following classes of proximity graphs: relative neighborhood graphs, Gabriel graphs, and relatively closest graphs. We prove that all of the aforementioned problems remain NP-hard on these graphs, except for 3-Colorability and Hamiltonian Cycle on relatively closest graphs, where the former is trivial and the latter is left open. Moreover, for every NP-hard case we additionally show that no 2^{o(n^{1/4})}-time algorithm exists unless the Exponential-Time Hypothesis (ETH) fails, where n denotes the number of vertices.

Cite as

Pascal Kunz, Till Fluschnik, Rolf Niedermeier, and Malte Renken. Most Classic Problems Remain NP-Hard on Relative Neighborhood Graphs and Their Relatives. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 29:1-29:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{kunz_et_al:LIPIcs.SWAT.2022.29,
  author =	{Kunz, Pascal and Fluschnik, Till and Niedermeier, Rolf and Renken, Malte},
  title =	{{Most Classic Problems Remain NP-Hard on Relative Neighborhood Graphs and Their Relatives}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{29:1--29:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.29},
  URN =		{urn:nbn:de:0030-drops-161891},
  doi =		{10.4230/LIPIcs.SWAT.2022.29},
  annote =	{Keywords: Proximity Graphs, Relatively Closest Graphs, Gabriel Graphs, 3-Colorability, Dominating Set, Feedback Vertex Set, Hamiltonian Cycle, Independent Set, Exponential-Time Hypothesis}
}
Document
Temporal Connectivity: Coping with Foreseen and Unforeseen Delays

Authors: Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
Consider planning a trip in a train network. In contrast to, say, a road network, the edges are temporal, i.e., they are only available at certain times. Another important difficulty is that trains, unfortunately, sometimes get delayed. This is especially bad if it causes one to miss subsequent trains. The best way to prepare against this is to have a connection that is robust to some number of (small) delays. An important factor in determining the robustness of a connection is how far in advance delays are announced. We give polynomial-time algorithms for the two extreme cases: delays known before departure and delays occurring without prior warning (the latter leading to a two-player game scenario). Interestingly, in the latter case, we show that the problem becomes PSPACE-complete if the itinerary is demanded to be a path.

Cite as

Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken. Temporal Connectivity: Coping with Foreseen and Unforeseen Delays. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fuchsle_et_al:LIPIcs.SAND.2022.17,
  author =	{F\"{u}chsle, Eugen and Molter, Hendrik and Niedermeier, Rolf and Renken, Malte},
  title =	{{Temporal Connectivity: Coping with Foreseen and Unforeseen Delays}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.17},
  URN =		{urn:nbn:de:0030-drops-159598},
  doi =		{10.4230/LIPIcs.SAND.2022.17},
  annote =	{Keywords: Paths and walks in temporal graphs, static expansions of temporal graphs, two-player games, flow computations, dynamic programming, PSPACE-completeness}
}
Document
Temporal Unit Interval Independent Sets

Authors: Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Rolf Niedermeier

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
Temporal graphs have been recently introduced to model changes to a given network that occur throughout a fixed period of time. We introduce and investigate the Temporal Δ Independent Set problem, a temporal variant of the well known Independent Set problem. This problem is e.g. motivated in the context of finding conflict-free schedules for maximum subsets of tasks, that have certain (changing) constraints on each day they need to be performed. We are specifically interested in the case where each task needs to be performed in a certain time-interval on each day and two tasks are in conflict on a day if their time-intervals overlap on that day. This leads us to considering Temporal Δ Independent Set on the restricted class of temporal unit interval graphs, i.e., temporal graphs where each layer is unit interval. We present several hardness results for this problem, as well as two algorithms: The first is a constant-factor approximation algorithm for instances where τ, the total number of time steps (layers) of the temporal graph, and Δ, a parameter that allows us to model some tolerance in the conflicts, are constants. For the second result we use the notion of order preservation for temporal unit interval graphs that, informally, requires the intervals of every layer to obey a common ordering. We provide an FPT algorithm parameterized by the size of minimum vertex deletion set to order preservation.

Cite as

Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Rolf Niedermeier. Temporal Unit Interval Independent Sets. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hermelin_et_al:LIPIcs.SAND.2022.19,
  author =	{Hermelin, Danny and Itzhaki, Yuval and Molter, Hendrik and Niedermeier, Rolf},
  title =	{{Temporal Unit Interval Independent Sets}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.19},
  URN =		{urn:nbn:de:0030-drops-159617},
  doi =		{10.4230/LIPIcs.SAND.2022.19},
  annote =	{Keywords: Temporal Graphs, Vertex Orderings, Order Preservation, Interval Graphs, Algorithms and Complexity}
}
Document
Delay-Robust Routes in Temporal Graphs

Authors: Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)


Abstract
Most transportation networks are inherently temporal: Connections (e.g. flights, train runs) are only available at certain, scheduled times. When transporting passengers or commodities, this fact must be considered for the the planning of itineraries. This has already led to several well-studied algorithmic problems on temporal graphs. The difficulty of the described task is increased by the fact that connections are often unreliable - in particular, many modes of transportation suffer from occasional delays. If these delays cause subsequent connections to be missed, the consequences can be severe. Thus, it is a vital problem to design itineraries that are robust to (small) delays. We initiate the study of this problem from a parameterized complexity perspective by proving its NP-completeness as well as several hardness and tractability results for natural parameterizations.

Cite as

Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken. Delay-Robust Routes in Temporal Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fuchsle_et_al:LIPIcs.STACS.2022.30,
  author =	{F\"{u}chsle, Eugen and Molter, Hendrik and Niedermeier, Rolf and Renken, Malte},
  title =	{{Delay-Robust Routes in Temporal Graphs}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.30},
  URN =		{urn:nbn:de:0030-drops-158403},
  doi =		{10.4230/LIPIcs.STACS.2022.30},
  annote =	{Keywords: algorithms and complexity, parameterized complexity, time-varying networks, temporal paths, journeys}
}
Document
Temporal Graphs: Structure, Algorithms, Applications (Dagstuhl Seminar 21171)

Authors: Arnaud Casteigts, Kitty Meeks, George B. Mertzios, and Rolf Niedermeier

Published in: Dagstuhl Reports, Volume 11, Issue 3 (2021)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 121171 "Temporal Graphs: Structure, Algorithms, Applications". The seminar was organized around four core areas: models, concepts, classes; concrete algorithmic problems; distributed aspects; applications. Because of the ongoing pandemic crisis, the seminar had to be held fully online, with talk and open problems sessions focussing on afternoons. Besides 19 contributed talks and small-group discussions, there were lively open-problem sessions, and some of the problems and research directions proposed there are part of this document. Despite strongly missing the usual Dagstuhl atmosphere and personal interaction possibilities, the seminar helped to establish new contacts and to identify new research directions in a thriving research area between (algorithmic) graph theory and network science.

Cite as

Arnaud Casteigts, Kitty Meeks, George B. Mertzios, and Rolf Niedermeier. Temporal Graphs: Structure, Algorithms, Applications (Dagstuhl Seminar 21171). In Dagstuhl Reports, Volume 11, Issue 3, pp. 16-46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@Article{casteigts_et_al:DagRep.11.3.16,
  author =	{Casteigts, Arnaud and Meeks, Kitty and Mertzios, George B. and Niedermeier, Rolf},
  title =	{{Temporal Graphs: Structure, Algorithms, Applications (Dagstuhl Seminar 21171)}},
  pages =	{16--46},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{3},
  editor =	{Casteigts, Arnaud and Meeks, Kitty and Mertzios, George B. and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.11.3.16},
  URN =		{urn:nbn:de:0030-drops-146892},
  doi =		{10.4230/DagRep.11.3.16},
  annote =	{Keywords: algorithm engineering, complex network analysis, distributed computing, models and classes, parameterized complexity analysis}
}
Document
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-dev.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}
}
  • Refine by Author
  • 39 Niedermeier, Rolf
  • 9 Nichterlein, André
  • 7 Zschoche, Philipp
  • 6 Fluschnik, Till
  • 6 Molter, Hendrik
  • Show More...

  • Refine by Classification
  • 19 Theory of computation → Graph algorithms analysis
  • 17 Theory of computation → Parameterized complexity and exact algorithms
  • 15 Mathematics of computing → Graph algorithms
  • 11 Theory of computation → Fixed parameter tractability
  • 7 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 10 fixed-parameter tractability
  • 10 kernelization
  • 8 complexity
  • 8 computational complexity
  • 6 parameterized complexity
  • Show More...

  • Refine by Type
  • 249 document
  • 3 volume

  • Refine by Publication Year
  • 93 2016
  • 65 2018
  • 64 2019
  • 8 2022
  • 7 2020
  • Show More...

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