Search Results

Documents authored by Fluschnik, Till

Document
DOI: 10.4230/OASIcs.ATMOS.2026.14
Algorithmics for Safe Bicycle Network Design with Bounded Detours in Rural Areas

Authors: Till Fluschnik

Published in: OASIcs, Volume 147, 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)

Abstract
We introduce the Safe Bicycle Network with Bounded Detours (SBNBD) problem, a network-design problem motivated by the upgrade of rural road networks for bicycle traffic. Given an undirected graph whose edges have length and are classified as safe or unsafe with unsafe edges carrying upgrade costs, a set of terminal pairs, an upgrade budget, and a detour factor α, the task is to upgrade unsafe edges so that every terminal pair is connected by a safe path whose length is at most α times its shortest-path distance in the original network. We study the computational complexity of SBNBD from a parameterized perspective. We prove strong NP-hardness even on highly restricted graph classes, including planar graphs of treewidth two, graphs with feedback vertex set number one, and graphs of maximum degree three. We complement these lower bounds with polynomial-time algorithms for trees and graphs of maximum degree two. For parameterized complexity, we show fixed-parameter tractability for the number of unsafe edges and prove matching lower bounds under SETH, a polynomial-kernel lower bound, and W-hardness for natural parameters. Our main positive structural result is an algorithm that maps any instance to an equivalent instance with O(fes+p) vertices and edges, where fes is the feedback edge number and p is the number of terminal pairs; this yields fixed-parameter tractability for the combined parameter fes+p. Finally, we construct and evaluate exact ILP-based algorithms on road networks derived from OpenStreetMap data for small German municipalities and their surrounding rural regions. The experiments show that these networks have small treewidth upper bounds and moderate feedback edge structure. We introduce a preprocessing routine based on the reduction algorithm for the parameter fes+p and a heuristic cut generation based on tree decompositions. Both improve exact solving performance, in particular for harder instances. Our results for different detour-factor bounds show that a moderate increase in α can substantially reduce the total length of the upgraded network, revealing practical trade-offs between upgrade budget and the maximum allowed relative detour. Our results indicate that structural graph parameters provide a useful algorithmic lens for safe bicycle-network design in rural areas.
Cite as

Till Fluschnik. Algorithmics for Safe Bicycle Network Design with Bounded Detours in Rural Areas. In 26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026). Open Access Series in Informatics (OASIcs), Volume 147, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fluschnik:OASIcs.ATMOS.2026.14,
  author =	{Fluschnik, Till},
  title =	{{Algorithmics for Safe Bicycle Network Design with Bounded Detours in Rural Areas}},
  booktitle =	{26th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2026)},
  pages =	{14:1--14:22},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-453-6},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{147},
  editor =	{Cacchiani, Valentina and Funke, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2026.14},
  URN =		{urn:nbn:de:0030-drops-278106},
  doi =		{10.4230/OASIcs.ATMOS.2026.14},
  annote =	{Keywords: Parameterized Algorithms, NP-hardness, Pairwise weighted spanners, Preprocessing, Integer linear programming, Cut generation}
}
Artifact
Software
DOI: 10.4230/artifacts.27626
buhtig-tf/Scheduling-Tasks-towards-Energy-Autarky

Authors: Robert Bredereck, Till Fluschnik, and Klaus Heeger

Abstract
Cite as

Robert Bredereck, Till Fluschnik, Klaus Heeger. buhtig-tf/Scheduling-Tasks-towards-Energy-Autarky (Software, Code and data). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27626,
   title = {{buhtig-tf/Scheduling-Tasks-towards-Energy-Autarky}}, 
   author = {Bredereck, Robert and Fluschnik, Till and Heeger, Klaus},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:ec658833659409634e2c49460594460b33fb79bc;origin=https://github.com/buhtig-tf/Scheduling-Tasks-towards-Energy-Autarky;visit=swh:1:snp:4dc374ef8186bd9c366ad76551db7b6234826a57;anchor=swh:1:rev:53b18632587db8612bf5de2a88d484f794727929}{\texttt{swh:1:dir:ec658833659409634e2c49460594460b33fb79bc}} (visited on 2026-08-25)},
   url = {https://github.com/buhtig-tf/Scheduling-Tasks-towards-Energy-Autarky},
   doi = {10.4230/artifacts.27626},
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.10
Scheduling Tasks Towards Energy Autarky: Benefits and Computational Costs of Flexibility

Authors: Robert Bredereck, Till Fluschnik, and Klaus Heeger

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
We study the autarky problem: given an energy forecast, a battery, and a set of energy-consuming jobs with time windows, decide whether all jobs can be scheduled without requiring external energy. We analyze the problem through the lens of job flexibility, defined as the number of time steps at which a job may be scheduled. We show that the problem is NP-hard already for flexibility two, even in restricted settings. On the positive side, we identify settings in which the problem is polynomial-time solvable, even for large flexibilities. Moreover, we obtain fixed-parameter tractability for combined parameters involving flexibility, such as the number of jobs. In contrast, we establish W-hardness when parameterized by maximum flexibility alone, even in a restricted setting. To complement our theoretical results, we formulate an integer linear program (ILP) that computes the minimum required external energy and evaluate it experimentally on instances derived from real-world energy-consumption and radiation data. The experiments indicate that increased job flexibility substantially reduces the need for external energy at moderate computational cost.
Cite as

Robert Bredereck, Till Fluschnik, and Klaus Heeger. Scheduling Tasks Towards Energy Autarky: Benefits and Computational Costs of Flexibility. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bredereck_et_al:LIPIcs.ESA.2026.10,
  author =	{Bredereck, Robert and Fluschnik, Till and Heeger, Klaus},
  title =	{{Scheduling Tasks Towards Energy Autarky: Benefits and Computational Costs of Flexibility}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.10},
  URN =		{urn:nbn:de:0030-drops-271469},
  doi =		{10.4230/LIPIcs.ESA.2026.10},
  annote =	{Keywords: computational sustainability, NP-hardness, parameterized complexity and algorithms, integer linear programming}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.29
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.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
DOI: 10.4230/LIPIcs.SAND.2022.16
Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring

Authors: Till Fluschnik and Pascal Kunz

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

Abstract
We consider the algorithmic complexity of recognizing bipartite temporal graphs. Rather than defining these graphs solely by their underlying graph or individual layers, we define a bipartite temporal graph as one in which every layer can be 2-colored in a way that results in few changes between any two consecutive layers. This approach follows the framework of multistage problems that has received a growing amount of attention in recent years. We investigate the complexity of recognizing these graphs. We show that this problem is NP-hard even if there are only two layers or if only one change is allowed between consecutive layers. We consider the parameterized complexity of the problem with respect to several structural graph parameters, which we transfer from the static to the temporal setting in three different ways. Finally, we consider a version of the problem in which we only restrict the total number of changes throughout the lifetime of the graph. We show that this variant is fixed-parameter tractable with respect to the number of changes.
Cite as

Till Fluschnik and Pascal Kunz. Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fluschnik_et_al:LIPIcs.SAND.2022.16,
  author =	{Fluschnik, Till and Kunz, Pascal},
  title =	{{Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{16:1--16:18},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.16},
  URN =		{urn:nbn:de:0030-drops-159587},
  doi =		{10.4230/LIPIcs.SAND.2022.16},
  annote =	{Keywords: structural parameters, NP-hardness, parameterized algorithms, multistage problems}
}
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.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/OASIcs.ATMOS.2018.10
Parameterized Algorithms and Data Reduction for Safe Convoy Routing

Authors: René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko

Published in: OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Abstract
We study a problem that models safely routing a convoy through a transportation network, where any vertex adjacent to the travel path of the convoy requires additional precaution: Given a graph G=(V,E), two vertices s,t in V, and two integers k,l, we search for a simple s-t-path with at most k vertices and at most l neighbors. We study the problem in two types of transportation networks: graphs with small crossing number, as formed by road networks, and tree-like graphs, as formed by waterways. For graphs with constant crossing number, we provide a subexponential 2^O(sqrt n)-time algorithm and prove a matching lower bound. We also show a polynomial-time data reduction algorithm that reduces any problem instance to an equivalent instance (a so-called problem kernel) of size polynomial in the vertex cover number of the input graph. In contrast, we show that the problem in general graphs is hard to preprocess. Regarding tree-like graphs, we obtain a 2^O(tw) * l^2 * n-time algorithm for graphs of treewidth tw, show that there is no problem kernel with size polynomial in tw, yet show a problem kernel with size polynomial in the feedback edge number of the input graph.
Cite as

René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko. Parameterized Algorithms and Data Reduction for Safe Convoy Routing. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vanbevern_et_al:OASIcs.ATMOS.2018.10,
  author =	{van Bevern, Ren\'{e} and Fluschnik, Till and Tsidulko, Oxana Yu.},
  title =	{{Parameterized Algorithms and Data Reduction for Safe Convoy Routing}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{10:1--10:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Bornd\"{o}rfer, Ralf and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.10},
  URN =		{urn:nbn:de:0030-drops-97157},
  doi =		{10.4230/OASIcs.ATMOS.2018.10},
  annote =	{Keywords: NP-hard problem, fixed-parameter tractability, problem kernelization, shortest path, secluded solution}
}
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.IPEC.2016.5
Finding Secluded Places of Special Interest in Graphs

Authors: René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
Finding a vertex subset in a graph that satisfies a certain property is one of the most-studied topics in algorithmic graph theory. The focus herein is often on minimizing or maximizing the size of the solution, that is, the size of the desired vertex set. In several applications, however, we also want to limit the "exposure" of the solution to the rest of the graph. This is the case, for example, when the solution represents persons that ought to deal with sensitive information or a segregated community. In this work, we thus explore the (parameterized) complexity of finding such secluded vertex subsets for a wide variety of properties that they shall fulfill. More precisely, we study the constraint that the (open or closed) neighborhood of the solution shall be bounded by a parameter and the influence of this constraint on the complexity of minimizing separators, feedback vertex sets, F-free vertex deletion sets, dominating sets, and the maximization of independent sets.
Cite as

René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Finding Secluded Places of Special Interest in Graphs. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{vanbevern_et_al:LIPIcs.IPEC.2016.5,
  author =	{van Bevern, Ren\'{e} and Fluschnik, Till and Mertzios, George B. and Molter, Hendrik and Sorge, Manuel and Such\'{y}, Ondrej},
  title =	{{Finding Secluded Places of Special Interest in Graphs}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.5},
  URN =		{urn:nbn:de:0030-drops-69380},
  doi =		{10.4230/LIPIcs.IPEC.2016.5},
  annote =	{Keywords: Neighborhood, Feedback Vertex Set, Vertex Deletion, Separator, Dominating Set}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.25
Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems

Authors: Till Fluschnik, Danny Hermelin, André Nichterlein, and Rolf Niedermeier

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Bodlaender et al.'s [Bodlaender/Jansen/Kratsch,2014] cross-composition technique is a popular method for excluding polynomial-size problem kernels for NP-hard parameterized problems. We present a new technique exploiting triangle-based fractal structures for extending the range of applicability of cross-compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of problems dealing with length-bounded cuts. Roughly speaking, our new technique combines the advantages of serial and parallel composition. In particular, answering an open question of Golovach and Thilikos [Golovach/Thilikos,2011], we show that, unless NP subseteq coNP/poly, the NP-hard Length-Bounded Edge-Cut problem (delete at most k edges such that the resulting graph has no s-t path of length shorter than l) parameterized by the combination of k and l has no polynomial-size problem kernel. Our framework applies to planar as well as directed variants of the basic problems and also applies to both edge and vertex deletion problems.
Cite as

Till Fluschnik, Danny Hermelin, André Nichterlein, and Rolf Niedermeier. Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fluschnik_et_al:LIPIcs.ICALP.2016.25,
  author =	{Fluschnik, Till and Hermelin, Danny and Nichterlein, Andr\'{e} and Niedermeier, Rolf},
  title =	{{Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.25},
  URN =		{urn:nbn:de:0030-drops-63049},
  doi =		{10.4230/LIPIcs.ICALP.2016.25},
  annote =	{Keywords: Parameterized complexity, polynomial-time data reduction, cross-compositions, lower bounds, graph modification problems, interdiction problems}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.448
The Parameterized Complexity of the Minimum Shared Edges Problem

Authors: Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, and Manuel Sorge

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract
We study the NP-complete Minimum Shared Edges (MSE) problem. Given an undirected graph, a source and a sink vertex, and two integers p and k, the question is whether there are p paths in the graph connecting the source with the sink and sharing at most k edges. Herein, an edge is shared if it appears in at least two paths. We show that MSE is W[1]-hard when parameterized by the treewidth of the input graph and the number k of shared edges combined. We show that MSE is fixed-parameter tractable with respect to p, but does not admit a polynomial-size kernel (unless NP is a subset of coNP/poly). In the proof of the fixed-parameter tractability of MSE parameterized by p, we employ the treewidth reduction technique due to Marx, O'Sullivan, and Razgon [ACM TALG 2013].
Cite as

Till Fluschnik, Stefan Kratsch, Rolf Niedermeier, and Manuel Sorge. The Parameterized Complexity of the Minimum Shared Edges Problem. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 448-462, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{fluschnik_et_al:LIPIcs.FSTTCS.2015.448,
  author =	{Fluschnik, Till and Kratsch, Stefan and Niedermeier, Rolf and Sorge, Manuel},
  title =	{{The Parameterized Complexity of the Minimum Shared Edges Problem}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{448--462},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.448},
  URN =		{urn:nbn:de:0030-drops-56323},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.448},
  annote =	{Keywords: Parameterized complexity, kernelization, treewidth, treewidth reduction}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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