38 Search Results for "W�rtz, Rolf"


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
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
Parameterized Complexity of Geodetic Set

Authors: Leon Kellerhals and Tomohiro Koana

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)


Abstract
A vertex set S of a graph G is geodetic if every vertex of G lies on a shortest path between two vertices in S. Given a graph G and k ∈ ℕ, the NP-hard Geodetic Set problem asks whether there is a geodetic set of size at most k. Complementing various works on Geodetic Set restricted to special graph classes, we initiate a parameterized complexity study of Geodetic Set and show, on the negative side, that Geodetic Set is W[1]-hard when parameterized by feedback vertex number, path-width, and solution size, combined. On the positive side, we develop fixed-parameter algorithms with respect to the feedback edge number, the tree-depth, and the modular-width of the input graph.

Cite as

Leon Kellerhals and Tomohiro Koana. Parameterized Complexity of Geodetic Set. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{kellerhals_et_al:LIPIcs.IPEC.2020.20,
  author =	{Kellerhals, Leon and Koana, Tomohiro},
  title =	{{Parameterized Complexity of Geodetic Set}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.20},
  URN =		{urn:nbn:de:0030-drops-133237},
  doi =		{10.4230/LIPIcs.IPEC.2020.20},
  annote =	{Keywords: NP-hard graph problems, Shortest paths, Tree-likeness, Parameter hierarchy, Data reduction, Integer linear programming}
}
Document
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-dev.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
Parameterized Algorithms for Matrix Completion with Radius Constraints

Authors: Tomohiro Koana, Vincent Froese, and Rolf Niedermeier

Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)


Abstract
Considering matrices with missing entries, we study NP-hard matrix completion problems where the resulting completed matrix should have limited (local) radius. In the pure radius version, this means that the goal is to fill in the entries such that there exists a "center string" which has Hamming distance to all matrix rows as small as possible. In stringology, this problem is also known as Closest String with Wildcards. In the local radius version, the requested center string must be one of the rows of the completed matrix. Hermelin and Rozenberg [CPM 2014, TCS 2016] performed a parameterized complexity analysis for Closest String with Wildcards. We answer one of their open questions, fix a bug concerning a fixed-parameter tractability result in their work, and improve some running time upper bounds. For the local radius case, we reveal a computational complexity dichotomy. In general, our results indicate that, although being NP-hard as well, this variant often allows for faster (fixed-parameter) algorithms.

Cite as

Tomohiro Koana, Vincent Froese, and Rolf Niedermeier. Parameterized Algorithms for Matrix Completion with Radius Constraints. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{koana_et_al:LIPIcs.CPM.2020.20,
  author =	{Koana, Tomohiro and Froese, Vincent and Niedermeier, Rolf},
  title =	{{Parameterized Algorithms for Matrix Completion with Radius Constraints}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-149-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{161},
  editor =	{G{\o}rtz, Inge Li and Weimann, Oren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.20},
  URN =		{urn:nbn:de:0030-drops-121456},
  doi =		{10.4230/LIPIcs.CPM.2020.20},
  annote =	{Keywords: fixed-parameter tractability, consensus string problems, Closest String, Closest String with Wildcards}
}
Document
Faster Binary Mean Computation Under Dynamic Time Warping

Authors: Nathan Schaar, Vincent Froese, and Rolf Niedermeier

Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)


Abstract
Many consensus string problems are based on Hamming distance. We replace Hamming distance by the more flexible (e.g., easily coping with different input string lengths) dynamic time warping distance, best known from applications in time series mining. Doing so, we study the problem of finding a mean string that minimizes the sum of (squared) dynamic time warping distances to a given set of input strings. While this problem is known to be NP-hard (even for strings over a three-element alphabet), we address the binary alphabet case which is known to be polynomial-time solvable. We significantly improve on a previously known algorithm in terms of worst-case running time. Moreover, we also show the practical usefulness of one of our algorithms in experiments with real-world and synthetic data. Finally, we identify special cases solvable in linear time (e.g., finding a mean of only two binary input strings) and report some empirical findings concerning combinatorial properties of optimal means.

Cite as

Nathan Schaar, Vincent Froese, and Rolf Niedermeier. Faster Binary Mean Computation Under Dynamic Time Warping. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{schaar_et_al:LIPIcs.CPM.2020.28,
  author =	{Schaar, Nathan and Froese, Vincent and Niedermeier, Rolf},
  title =	{{Faster Binary Mean Computation Under Dynamic Time Warping}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{28:1--28:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-149-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{161},
  editor =	{G{\o}rtz, Inge Li and Weimann, Oren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.28},
  URN =		{urn:nbn:de:0030-drops-121538},
  doi =		{10.4230/LIPIcs.CPM.2020.28},
  annote =	{Keywords: consensus string problems, time series averaging, minimum 1-separated sum, sparse strings}
}
Document
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-dev.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
Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters

Authors: Robert Bredereck, Klaus Heeger, Dušan Knop, and Rolf Niedermeier

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)


Abstract
We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side of fixed-parameter tractability. Other than for its famous sister problem Stable Marriage which focuses on a bipartite scenario, Stable Roommates with Incomplete Lists allows for arbitrary acceptability graphs whose edges specify the possible matchings of each two agents (agents are represented by graph vertices). Herein, incomplete lists and ties reflect the fact that in realistic application scenarios the agents cannot bring all other agents into a linear order. Among our main contributions is to show that it is W[1]-hard to compute a maximum-cardinality stable matching for acceptability graphs of bounded treedepth, bounded tree-cut width, and bounded feedback vertex number (these are each time the respective parameters). However, if we "only" ask for perfect stable matchings or the mere existence of a stable matching, then we obtain fixed-parameter tractability with respect to tree-cut width but not with respect to treedepth. On the positive side, we also provide fixed-parameter tractability results for the parameter feedback edge set number.

Cite as

Robert Bredereck, Klaus Heeger, Dušan Knop, and Rolf Niedermeier. Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bredereck_et_al:LIPIcs.ISAAC.2019.44,
  author =	{Bredereck, Robert and Heeger, Klaus and Knop, Du\v{s}an and Niedermeier, Rolf},
  title =	{{Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{44:1--44:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.44},
  URN =		{urn:nbn:de:0030-drops-115406},
  doi =		{10.4230/LIPIcs.ISAAC.2019.44},
  annote =	{Keywords: Stable matching, acceptability graph, fixed-parameter tractability, W\lbrack1\rbrack-hardness, treewidth, treedepth, tree-cut width, feedback set numbers}
}
Document
Token Sliding on Split Graphs

Authors: Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)


Abstract
We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex that is currently in the set with one of its neighbors, while maintaining the set independent. Our main result is to show that this problem is PSPACE-complete on split graphs (and hence also on chordal graphs), thus resolving an open problem in this area. We then go on to consider the c-Colorable Reconfiguration problem under the same rule, where the constraint is now to maintain the set c-colorable at all times. As one may expect, a simple modification of our reduction shows that this more general problem is PSPACE-complete for all fixed c >= 1 on chordal graphs. Somewhat surprisingly, we show that the same cannot be said for split graphs: we give a polynomial time (n^{O(c)}) algorithm for all fixed values of c, except c=1, for which the problem is PSPACE-complete. We complement our algorithm with a lower bound showing that c-Colorable Reconfiguration is W[2]-hard on split graphs parameterized by c and the length of the solution, as well as a tight ETH-based lower bound for both parameters.

Cite as

Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora. Token Sliding on Split Graphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{belmonte_et_al:LIPIcs.STACS.2019.13,
  author =	{Belmonte, R\'{e}my and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and Otachi, Yota and Sikora, Florian},
  title =	{{Token Sliding on Split Graphs}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.13},
  URN =		{urn:nbn:de:0030-drops-102529},
  doi =		{10.4230/LIPIcs.STACS.2019.13},
  annote =	{Keywords: reconfiguration, independent set, split graph}
}
Document
Closure Properties of Synchronized Relations

Authors: María Emilia Descotte, Diego Figueira, and Santiago Figueira

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)


Abstract
A standard approach to define k-ary word relations over a finite alphabet A is through k-tape finite state automata that recognize regular languages L over {1, ..., k} x A, where (i,a) is interpreted as reading letter a from tape i. Accordingly, a word w in L denotes the tuple (u_1, ..., u_k) in (A^*)^k in which u_i is the projection of w onto i-labelled letters. While this formalism defines the well-studied class of rational relations, enforcing restrictions on the reading regime from the tapes, which we call synchronization, yields various sub-classes of relations. Such synchronization restrictions are imposed through regular properties on the projection of the language L onto {1, ..., k}. In this way, for each regular language C subseteq {1, ..., k}^*, one obtains a class Rel({C}) of relations. Synchronous, Recognizable, and Length-preserving rational relations are all examples of classes that can be defined in this way. We study basic properties of these classes of relations, in terms of closure under intersection, complement, concatenation, Kleene star and projection. We characterize the classes with each closure property. For the binary case (k=2) this yields effective procedures.

Cite as

María Emilia Descotte, Diego Figueira, and Santiago Figueira. Closure Properties of Synchronized Relations. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{descotte_et_al:LIPIcs.STACS.2019.22,
  author =	{Descotte, Mar{\'\i}a Emilia and Figueira, Diego and Figueira, Santiago},
  title =	{{Closure Properties of Synchronized Relations}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.22},
  URN =		{urn:nbn:de:0030-drops-102614},
  doi =		{10.4230/LIPIcs.STACS.2019.22},
  annote =	{Keywords: synchronized word relations, rational, closure, characterization, intersection, complement, Kleene star, concatenation}
}
Document
Lower Bounds for DeMorgan Circuits of Bounded Negation Width

Authors: Stasys Jukna and Andrzej Lingas

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)


Abstract
We consider Boolean circuits over {or, and, neg} with negations applied only to input variables. To measure the "amount of negation" in such circuits, we introduce the concept of their "negation width". In particular, a circuit computing a monotone Boolean function f(x_1,...,x_n) has negation width w if no nonzero term produced (purely syntactically) by the circuit contains more than w distinct negated variables. Circuits of negation width w=0 are equivalent to monotone Boolean circuits, while those of negation width w=n have no restrictions. Our motivation is that already circuits of moderate negation width w=n^{epsilon} for an arbitrarily small constant epsilon>0 can be even exponentially stronger than monotone circuits. We show that the size of any circuit of negation width w computing f is roughly at least the minimum size of a monotone circuit computing f divided by K=min{w^m,m^w}, where m is the maximum length of a prime implicant of f. We also show that the depth of any circuit of negation width w computing f is roughly at least the minimum depth of a monotone circuit computing f minus log K. Finally, we show that formulas of bounded negation width can be balanced to achieve a logarithmic (in their size) depth without increasing their negation width.

Cite as

Stasys Jukna and Andrzej Lingas. Lower Bounds for DeMorgan Circuits of Bounded Negation Width. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{jukna_et_al:LIPIcs.STACS.2019.41,
  author =	{Jukna, Stasys and Lingas, Andrzej},
  title =	{{Lower Bounds for DeMorgan Circuits of Bounded Negation Width}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{41:1--41:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.41},
  URN =		{urn:nbn:de:0030-drops-102801},
  doi =		{10.4230/LIPIcs.STACS.2019.41},
  annote =	{Keywords: Boolean circuits, monotone circuits, lower bounds}
}
Document
On Finite Monoids over Nonnegative Integer Matrices and Short Killing Words

Authors: Stefan Kiefer and Corto Mascle

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)


Abstract
Let n be a natural number and M a set of n x n-matrices over the nonnegative integers such that M generates a finite multiplicative monoid. We show that if the zero matrix 0 is a product of matrices in M, then there are M_1, ..., M_{n^5} in M with M_1 *s M_{n^5} = 0. This result has applications in automata theory and the theory of codes. Specifically, if X subset Sigma^* is a finite incomplete code, then there exists a word w in Sigma^* of length polynomial in sum_{x in X} |x| such that w is not a factor of any word in X^*. This proves a weak version of Restivo’s conjecture.

Cite as

Stefan Kiefer and Corto Mascle. On Finite Monoids over Nonnegative Integer Matrices and Short Killing Words. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{kiefer_et_al:LIPIcs.STACS.2019.43,
  author =	{Kiefer, Stefan and Mascle, Corto},
  title =	{{On Finite Monoids over Nonnegative Integer Matrices and Short Killing Words}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{43:1--43:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.43},
  URN =		{urn:nbn:de:0030-drops-102823},
  doi =		{10.4230/LIPIcs.STACS.2019.43},
  annote =	{Keywords: matrix semigroups, unambiguous automata, codes, Restivo’s conjecture}
}
Document
A Unified Approach to Tail Estimates for Randomized Incremental Construction

Authors: Sandeep Sen

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)


Abstract
By combining several interesting applications of random sampling in geometric algorithms like point location, linear programming, segment intersections, binary space partitioning, Clarkson and Shor [Kenneth L. Clarkson and Peter W. Shor, 1989] developed a general framework of randomized incremental construction (RIC ). The basic idea is to add objects in a random order and show that this approach yields efficient/optimal bounds on expected running time. Even quicksort can be viewed as a special case of this paradigm. However, unlike quicksort, for most of these problems, sharper tail estimates on their running times are not known. Barring some promising attempts in [Kurt Mehlhorn et al., 1993; Kenneth L. Clarkson et al., 1992; Raimund Seidel, 1991], the general question remains unresolved. In this paper we present a general technique to obtain tail estimates for RIC and and provide applications to some fundamental problems like Delaunay triangulations and construction of Visibility maps of intersecting line segments. The main result of the paper is derived from a new and careful application of Freedman’s [David Freedman, 1975] inequality for Martingale concentration that overcomes the bottleneck of the better known Azuma-Hoeffding inequality. Further, we explore instances, where an RIC based algorithm may not have inverse polynomial tail estimates. In particular, we show that the RIC time bounds for trapezoidal map can encounter a running time of Omega (n log n log log n) with probability exceeding 1/(sqrt{n)}. This rules out inverse polynomial concentration bounds within a constant factor of the O(n log n) expected running time.

Cite as

Sandeep Sen. A Unified Approach to Tail Estimates for Randomized Incremental Construction. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{sen:LIPIcs.STACS.2019.58,
  author =	{Sen, Sandeep},
  title =	{{A Unified Approach to Tail Estimates for Randomized Incremental Construction}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{58:1--58:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.58},
  URN =		{urn:nbn:de:0030-drops-102977},
  doi =		{10.4230/LIPIcs.STACS.2019.58},
  annote =	{Keywords: ric, tail estimates, martingale, lower bound}
}
Document
Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth

Authors: Bas A. M. van Geffen, Bart M. P. Jansen, Arnoud A. W. M. de Kroon, and Rolf Morel

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)


Abstract
Many combinatorial problems can be solved in time O^*(c^{tw}) on graphs of treewidth tw, for a problem-specific constant c. In several cases, matching upper and lower bounds on c are known based on the Strong Exponential Time Hypothesis (SETH). In this paper we investigate the complexity of solving problems on graphs of bounded cutwidth, a graph parameter that takes larger values than treewidth. We strengthen earlier treewidth-based lower bounds to show that, assuming SETH, Independent Set cannot be solved in O^*((2-epsilon)^{ctw}) time, and Dominating Set cannot be solved in O^*((3-epsilon)^{ctw}) time. By designing a new crossover gadget, we extend these lower bounds even to planar graphs of bounded cutwidth or treewidth. Hence planarity does not help when solving Independent Set or Dominating Set on graphs of bounded width. This sharply contrasts the fact that in many settings, planarity allows problems to be solved much more efficiently.

Cite as

Bas A. M. van Geffen, Bart M. P. Jansen, Arnoud A. W. M. de Kroon, and Rolf Morel. Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{vangeffen_et_al:LIPIcs.IPEC.2018.3,
  author =	{van Geffen, Bas A. M. and Jansen, Bart M. P. and de Kroon, Arnoud A. W. M. and Morel, Rolf},
  title =	{{Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.3},
  URN =		{urn:nbn:de:0030-drops-102049},
  doi =		{10.4230/LIPIcs.IPEC.2018.3},
  annote =	{Keywords: planarization, dominating set, cutwidth, lower bounds, strong exponential time hypothesis}
}
Document
Parameterized (Approximate) Defective Coloring

Authors: Rémy Belmonte, Michael Lampis, and Valia Mitsou

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)


Abstract
In Defective Coloring we are given a graph G=(V,E) and two integers chi_d,Delta^* and are asked if we can partition V into chi_d color classes, so that each class induces a graph of maximum degree Delta^*. We investigate the complexity of this generalization of Coloring with respect to several well-studied graph parameters, and show that the problem is W-hard parameterized by treewidth, pathwidth, tree-depth, or feedback vertex set, if chi_d=2. As expected, this hardness can be extended to larger values of chi_d for most of these parameters, with one surprising exception: we show that the problem is FPT parameterized by feedback vertex set for any chi_d != 2, and hence 2-coloring is the only hard case for this parameter. In addition to the above, we give an ETH-based lower bound for treewidth and pathwidth, showing that no algorithm can solve the problem in n^{o(pw)}, essentially matching the complexity of an algorithm obtained with standard techniques. We complement these results by considering the problem's approximability and show that, with respect to Delta^*, the problem admits an algorithm which for any epsilon>0 runs in time (tw/epsilon)^{O(tw)} and returns a solution with exactly the desired number of colors that approximates the optimal Delta^* within (1+epsilon). We also give a (tw)^{O(tw)} algorithm which achieves the desired Delta^* exactly while 2-approximating the minimum value of chi_d. We show that this is close to optimal, by establishing that no FPT algorithm can (under standard assumptions) achieve a better than 3/2-approximation to chi_d, even when an extra constant additive error is also allowed.

Cite as

Rémy Belmonte, Michael Lampis, and Valia Mitsou. Parameterized (Approximate) Defective Coloring. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{belmonte_et_al:LIPIcs.STACS.2018.10,
  author =	{Belmonte, R\'{e}my and Lampis, Michael and Mitsou, Valia},
  title =	{{Parameterized (Approximate) Defective Coloring}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.10},
  URN =		{urn:nbn:de:0030-drops-85304},
  doi =		{10.4230/LIPIcs.STACS.2018.10},
  annote =	{Keywords: Treewidth, Parameterized Complexity, Approximation, Coloring}
}
  • Refine by Author
  • 8 Niedermeier, Rolf
  • 4 Bellman, Kirstie
  • 4 Müller-Schloer, Christian
  • 4 Schmeck, Hartmut
  • 3 Fluschnik, Till
  • Show More...

  • Refine by Classification
  • 7 Theory of computation → Parameterized complexity and exact algorithms
  • 3 Mathematics of computing → Graph algorithms
  • 3 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Formal languages and automata theory
  • 2 Theory of computation → Pattern matching
  • Show More...

  • Refine by Keyword
  • 4 self-organization
  • 3 W[1]-hardness
  • 3 fixed-parameter tractability
  • 3 kernelization
  • 2 Emergence
  • Show More...

  • Refine by Type
  • 38 document

  • Refine by Publication Year
  • 10 2008
  • 8 2019
  • 5 2006
  • 4 2018
  • 4 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