Search Results

Documents authored by Froese, Vincent

Document
DOI: 10.4230/LIPIcs.ESA.2022.53
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.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
DOI: 10.4230/LIPIcs.STACS.2021.47
Binary Matrix Completion Under Diameter Constraints

Authors: Tomohiro Koana, Vincent Froese, and Rolf Niedermeier

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
We thoroughly study a novel but basic combinatorial matrix completion problem: Given a binary incomplete matrix, fill in the missing entries so that the resulting matrix has a specified maximum diameter (that is, upper-bounding the maximum Hamming distance between any two rows of the completed matrix) as well as a specified minimum Hamming distance between any two of the matrix rows. This scenario is closely related to consensus string problems as well as to recently studied clustering problems on incomplete data. We obtain an almost complete picture concerning the complexity landscape (P vs NP) regarding the diameter constraints and regarding the number of missing entries per row of the incomplete matrix. We develop polynomial-time algorithms for maximum diameter three, which are based on Deza’s theorem [Discret. Math. 1973, J. Comb. Theory, Ser. B 1974] from extremal set theory. In this way, we also provide one of the rare links between sunflower techniques and stringology. On the negative side, we prove NP-hardness for diameter at least four. For the number of missing entries per row, we show polynomial-time solvability when there is only one missing entry and NP-hardness when there can be at least two missing entries. In general, our algorithms heavily rely on Deza’s theorem and the correspondingly identified sunflower structures pave the way towards solutions based on computing graph factors and solving 2-SAT instances.
Cite as

Tomohiro Koana, Vincent Froese, and Rolf Niedermeier. Binary Matrix Completion Under Diameter Constraints. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{koana_et_al:LIPIcs.STACS.2021.47,
  author =	{Koana, Tomohiro and Froese, Vincent and Niedermeier, Rolf},
  title =	{{Binary Matrix Completion Under Diameter Constraints}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{47:1--47:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.47},
  URN =		{urn:nbn:de:0030-drops-136925},
  doi =		{10.4230/LIPIcs.STACS.2021.47},
  annote =	{Keywords: sunflowers, binary matrices, Hamming distance, stringology, consensus problems, complexity dichotomy, combinatorial algorithms, graph factors, 2-Sat, Hamming radius}
}
Document
DOI: 10.4230/LIPIcs.CPM.2020.20
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.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
DOI: 10.4230/LIPIcs.CPM.2020.28
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.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
DOI: 10.4230/LIPIcs.IPEC.2016.10
A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed Graphs

Authors: Robert Bredereck, Vincent Froese, Marcel Koseler, Marcelo Garlet Millani, André Nichterlein, and Rolf Niedermeier

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

Abstract
There has been intensive work on the parameterized complexity of the typically NP-hard task to edit undirected graphs into graphs fulfilling certain given vertex degree constraints. In this work, we lift the investigations to the case of directed graphs; herein, we focus on arc insertions. To this end, our general two-stage framework consists of efficiently solving a problem-specific number problem transferring its solution to a solution for the graph problem by applying flow computations. In this way, we obtain fixed-parameter tractability and polynomial kernelizability results, with the central parameter being the maximum vertex in- or outdegree of the output digraph. Although there are certain similarities with the much better studied undirected case, the flow computation used in the directed case seems not to work for the undirected case while f-factor computations as used in the undirected case seem not to work for the directed case.
Cite as

Robert Bredereck, Vincent Froese, Marcel Koseler, Marcelo Garlet Millani, André Nichterlein, and Rolf Niedermeier. A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed Graphs. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bredereck_et_al:LIPIcs.IPEC.2016.10,
  author =	{Bredereck, Robert and Froese, Vincent and Koseler, Marcel and Millani, Marcelo Garlet and Nichterlein, Andr\'{e} and Niedermeier, Rolf},
  title =	{{A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed Graphs}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{10:1--10:14},
  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.10},
  URN =		{urn:nbn:de:0030-drops-69353},
  doi =		{10.4230/LIPIcs.IPEC.2016.10},
  annote =	{Keywords: NP-hard graph problem, graph realizability, graph modification, arc insertion, fixed-parameter tractability, kernelization}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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