102 Search Results for "K�nig, Robert"

Document
DOI: 10.4230/LIPIcs.STACS.2024.7
Computing Twin-Width Parameterized by the Feedback Edge Number

Authors: Jakub Balabán, Robert Ganian, and Mathis Rocton

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
The problem of whether and how one can compute the twin-width of a graph - along with an accompanying contraction sequence - lies at the forefront of the area of algorithmic model theory. While significant effort has been aimed at obtaining a fixed-parameter approximation for the problem when parameterized by twin-width, here we approach the question from a different perspective and consider whether one can obtain (near-)optimal contraction sequences under a larger parameterization, notably the feedback edge number k. As our main contributions, under this parameterization we obtain (1) a linear bikernel for the problem of either computing a 2-contraction sequence or determining that none exists and (2) an approximate fixed-parameter algorithm which computes an 𝓁-contraction sequence (for an arbitrary specified 𝓁) or determines that the twin-width of the input graph is at least 𝓁. These algorithmic results rely on newly obtained insights into the structure of optimal contraction sequences, and as a byproduct of these we also slightly tighten the bound on the twin-width of graphs with small feedback edge number.
Cite as

Jakub Balabán, Robert Ganian, and Mathis Rocton. Computing Twin-Width Parameterized by the Feedback Edge Number. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.STACS.2024.7,
  author =	{Balab\'{a}n, Jakub and Ganian, Robert and Rocton, Mathis},
  title =	{{Computing Twin-Width Parameterized by the Feedback Edge Number}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.7},
  URN =		{urn:nbn:de:0030-drops-197170},
  doi =		{10.4230/LIPIcs.STACS.2024.7},
  annote =	{Keywords: twin-width, parameterized complexity, kernelization, feedback edge number}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.18
Consistency Checking Problems: A Gateway to Parameterized Sample Complexity

Authors: Robert Ganian, Liana Khazaliya, and Kirill Simonov

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
Recently, Brand, Ganian and Simonov introduced a parameterized refinement of the classical PAC-learning sample complexity framework. A crucial outcome of their investigation is that for a very wide range of learning problems, there is a direct and provable correspondence between fixed-parameter PAC-learnability (in the sample complexity setting) and the fixed-parameter tractability of a corresponding "consistency checking" search problem (in the setting of computational complexity). The latter can be seen as generalizations of classical search problems where instead of receiving a single instance, one receives multiple yes- and no-examples and is tasked with finding a solution which is consistent with the provided examples. Apart from a few initial results, consistency checking problems are almost entirely unexplored from a parameterized complexity perspective. In this article, we provide an overview of these problems and their connection to parameterized sample complexity, with the primary aim of facilitating further research in this direction. Afterwards, we establish the fixed-parameter (in)-tractability for some of the arguably most natural consistency checking problems on graphs, and show that their complexity-theoretic behavior is surprisingly very different from that of classical decision problems. Our new results cover consistency checking variants of problems as diverse as (k-)Path, Matching, 2-Coloring, Independent Set and Dominating Set, among others.
Cite as

Robert Ganian, Liana Khazaliya, and Kirill Simonov. Consistency Checking Problems: A Gateway to Parameterized Sample Complexity. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.IPEC.2023.18,
  author =	{Ganian, Robert and Khazaliya, Liana and Simonov, Kirill},
  title =	{{Consistency Checking Problems: A Gateway to Parameterized Sample Complexity}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.18},
  URN =		{urn:nbn:de:0030-drops-194374},
  doi =		{10.4230/LIPIcs.IPEC.2023.18},
  annote =	{Keywords: consistency checking, sample complexity, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.DNA.29.10
Complexity of Reconfiguration in Surface Chemical Reaction Networks

Authors: Robert M. Alaniz, Josh Brunner, Michael Coulombe, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Elise Grizzell, Ryan Knobel, Jayson Lynch, Andrew Rodriguez, Robert Schweller, and Tim Wylie

Published in: LIPIcs, Volume 276, 29th International Conference on DNA Computing and Molecular Programming (DNA 29) (2023)

Abstract
We analyze the computational complexity of basic reconfiguration problems for the recently introduced surface Chemical Reaction Networks (sCRNs), where ordered pairs of adjacent species nondeterministically transform into a different ordered pair of species according to a predefined set of allowed transition rules (chemical reactions). In particular, two questions that are fundamental to the simulation of sCRNs are whether a given configuration of molecules can ever transform into another given configuration, and whether a given cell can ever contain a given species, given a set of transition rules. We show that these problems can be solved in polynomial time, are NP-complete, or are PSPACE-complete in a variety of different settings, including when adjacent species just swap instead of arbitrary transformation (swap sCRNs), and when cells can change species a limited number of times (k-burnout). Most problems turn out to be at least NP-hard except with very few distinct species (2 or 3).
Cite as

Robert M. Alaniz, Josh Brunner, Michael Coulombe, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Elise Grizzell, Ryan Knobel, Jayson Lynch, Andrew Rodriguez, Robert Schweller, and Tim Wylie. Complexity of Reconfiguration in Surface Chemical Reaction Networks. In 29th International Conference on DNA Computing and Molecular Programming (DNA 29). Leibniz International Proceedings in Informatics (LIPIcs), Volume 276, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{alaniz_et_al:LIPIcs.DNA.29.10,
  author =	{Alaniz, Robert M. and Brunner, Josh and Coulombe, Michael and Demaine, Erik D. and Diomidova, Jenny and Gomez, Timothy and Grizzell, Elise and Knobel, Ryan and Lynch, Jayson and Rodriguez, Andrew and Schweller, Robert and Wylie, Tim},
  title =	{{Complexity of Reconfiguration in Surface Chemical Reaction Networks}},
  booktitle =	{29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
  pages =	{10:1--10:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-297-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{276},
  editor =	{Chen, Ho-Lin and Evans, Constantine G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.10},
  URN =		{urn:nbn:de:0030-drops-187936},
  doi =		{10.4230/LIPIcs.DNA.29.10},
  annote =	{Keywords: Chemical Reaction Networks, reconfiguration, hardness}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2023.1
Optimal Bicycle Routes with Few Signal Stops

Authors: Ekkehard Köhler, Markus Rogge, Robert Scheffler, and Martin Strehler

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
With the increasing popularity of cycling as a mode of transportation, there is a growing need for efficient routing algorithms that consider the specific requirements of cyclists. This paper studies the optimization of bicycle routes while minimizing the number of stops at traffic signals. In particular, we consider three different types of stopping strategies and three types of routes, namely paths, trails, and walks. We present hardness results as well as a pseudo-polynomial algorithm for the problem of computing an optimal route with respect to a pre-defined stop bound.
Cite as

Ekkehard Köhler, Markus Rogge, Robert Scheffler, and Martin Strehler. Optimal Bicycle Routes with Few Signal Stops. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kohler_et_al:OASIcs.ATMOS.2023.1,
  author =	{K\"{o}hler, Ekkehard and Rogge, Markus and Scheffler, Robert and Strehler, Martin},
  title =	{{Optimal Bicycle Routes with Few Signal Stops}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{1:1--1:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.1},
  URN =		{urn:nbn:de:0030-drops-187628},
  doi =		{10.4230/OASIcs.ATMOS.2023.1},
  annote =	{Keywords: Constrained shortest path, traffic signals, bicycle routes}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.18
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth

Authors: Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michał Pilipczuk, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition’s width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth. Here, shrubdepth is a bounded-depth analogue of cliquewidth, in the same way as treedepth is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. More precisely, we prove that on n-vertex graphs equipped with a tree-model (a decomposition notion underlying shrubdepth) of depth d and using k labels, - Independent Set can be solved in time 2^𝒪(dk) ⋅ n^𝒪(1) using 𝒪(dk²log n) space; - Max Cut can be solved in time n^𝒪(dk) using 𝒪(dk log n) space; and - Dominating Set can be solved in time 2^𝒪(dk) ⋅ n^𝒪(1) using n^𝒪(1) space via a randomized algorithm. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of Independent Set the exponent of the parametric factor in the time complexity has to grow with d if one wishes to keep the space complexity polynomial.
Cite as

Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michał Pilipczuk, and Erik Jan van Leeuwen. Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bergougnoux_et_al:LIPIcs.ESA.2023.18,
  author =	{Bergougnoux, Benjamin and Chekan, Vera and Ganian, Robert and Kant\'{e}, Mamadou Moustapha and Mnich, Matthias and Oum, Sang-il and Pilipczuk, Micha{\l} and van Leeuwen, Erik Jan},
  title =	{{Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.18},
  URN =		{urn:nbn:de:0030-drops-186710},
  doi =		{10.4230/LIPIcs.ESA.2023.18},
  annote =	{Keywords: Parameterized complexity, shrubdepth, space complexity, algebraic methods}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.36
Colourful TFNP and Propositional Proofs

Authors: Ben Davis and Robert Robere

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
Recent work has shown that many of the standard TFNP classes - such as PLS, PPADS, PPAD, SOPL, and EOPL - have corresponding proof systems in propositional proof complexity, in the sense that a total search problem is in the class if and only if the totality of the problem can be efficiently proved by the corresponding proof system. We build on this line of work by studying coloured variants of these TFNP classes: C-PLS, C-PPADS, C-PPAD, C-SOPL, and C-EOPL. While C-PLS has been studied in the literature before, the coloured variants of the other classes are introduced here for the first time. We give a family of results showing that these coloured TFNP classes are natural objects of study, and that the correspondence between TFNP and natural propositional proof systems is not an exceptional phenomenon isolated to weak TFNP classes. Namely, we show that: - Each of the classes C-PLS, C-PPADS, and C-SOPL have corresponding proof systems characterizing them. Specifically, the proof systems for these classes are obtained by adding depth to the formulas in the corresponding proof system for the uncoloured class. For instance, while it was previously known that PLS is characterized by bounded-width Resolution (i.e. depth 0.5 Frege), we prove that C-PLS is characterized by depth-1.5 Frege (Res(polylog(n)). - The classes C-PPAD and C-EOPL coincide exactly with the uncoloured classes PPADS and SOPL, respectively. Thus, both of these classes also have corresponding proof systems: unary Sherali-Adams and Reversible Resolution, respectively. - Finally, we prove a coloured intersection theorem for the coloured sink classes, showing C-PLS ∩ C-PPADS = C-SOPL, generalizing the intersection theorem PLS ∩ PPADS = SOPL. However, while it is known in the uncoloured world that PLS ∩ PPAD = EOPL = CLS, we prove that this equality fails in the coloured world in the black-box setting. More precisely, we show that there is an oracle O such that C-PLS^O ∩ C-PPAD^O ⊋ C-EOPL^O. To prove our results, we introduce an abstract multivalued proof system - the Blockwise Calculus - which may be of independent interest.
Cite as

Ben Davis and Robert Robere. Colourful TFNP and Propositional Proofs. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{davis_et_al:LIPIcs.CCC.2023.36,
  author =	{Davis, Ben and Robere, Robert},
  title =	{{Colourful TFNP and Propositional Proofs}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{36:1--36:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.36},
  URN =		{urn:nbn:de:0030-drops-183066},
  doi =		{10.4230/LIPIcs.CCC.2023.36},
  annote =	{Keywords: oracle separations, TFNP, proof complexity, Res(k), lower bounds}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.59
Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds

Authors: Robert Ferens and Marek Szykuła

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
A complete deterministic finite (semi)automaton (DFA) with a set of states Q is completely reachable if every non-empty subset of Q can be obtained as the image of the action of some word applied to Q. The concept of completely reachable automata appeared several times, in particular, in connection with synchronizing automata; the class contains the Černý automata and covers a few separately investigated subclasses. The notion was introduced by Bondar and Volkov (2016), who also raised the question about the complexity of deciding if an automaton is completely reachable. We develop a polynomial-time algorithm for this problem, which is based on a new complement-intersecting technique for finding an extending word for a subset of states. The algorithm works in 𝒪(|Σ|⋅ n³) time, where n = |Q| is the number of states and |Σ| is the size of the input alphabet. Finally, we prove a weak Don’s conjecture for this class of automata: a subset of size k is reachable with a word of length smaller than 2n(n-k). This implies a quadratic upper bound in n on the length of the shortest synchronizing words (reset threshold) for the class of completely reachable automata and generalizes earlier upper bounds derived for its subclasses.
Cite as

Robert Ferens and Marek Szykuła. Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 59:1-59:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ferens_et_al:LIPIcs.ICALP.2023.59,
  author =	{Ferens, Robert and Szyku{\l}a, Marek},
  title =	{{Completely Reachable Automata: A Polynomial Algorithm and Quadratic Upper Bounds}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{59:1--59:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.59},
  URN =		{urn:nbn:de:0030-drops-181110},
  doi =		{10.4230/LIPIcs.ICALP.2023.59},
  annote =	{Keywords: \v{C}ern\'{y} conjecture, complete reachability, DFA, extending word, reachability, reset threshold, reset word, simple idempotent, synchronizing automaton, synchronizing word}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.28
The Parameterized Complexity of Coordinated Motion Planning

Authors: Eduard Eiben, Robert Ganian, and Iyad Kanj

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
In Coordinated Motion Planning (CMP), we are given a rectangular-grid on which k robots occupy k distinct starting gridpoints and need to reach k distinct destination gridpoints. In each time step, any robot may move to a neighboring gridpoint or stay in its current gridpoint, provided that it does not collide with other robots. The goal is to compute a schedule for moving the k robots to their destinations which minimizes a certain objective target - prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. We refer to the problem arising from minimizing the former objective target as CMP-M and the latter as CMP-L. Both CMP-M and CMP-L are fundamental problems that were posed as the computational geometry challenge of SoCG 2021, and CMP also embodies the famous (n²-1)-puzzle as a special case. In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters: the number of robots, and the objective target. We develop a new approach to establish the fixed-parameter tractability of both problems under the former parameterization that relies on novel structural insights into optimal solutions to the problem. When parameterized by the objective target, we show that CMP-L remains fixed-parameter tractable while CMP-M becomes para-NP-hard. The latter result is noteworthy, not only because it improves the previously-known boundaries of intractability for the problem, but also because the underlying reduction allows us to establish - as a simpler case - the NP-hardness of the classical Vertex Disjoint and Edge Disjoint Paths problems with constant path-lengths on grids.
Cite as

Eduard Eiben, Robert Ganian, and Iyad Kanj. The Parameterized Complexity of Coordinated Motion Planning. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.SoCG.2023.28,
  author =	{Eiben, Eduard and Ganian, Robert and Kanj, Iyad},
  title =	{{The Parameterized Complexity of Coordinated Motion Planning}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.28},
  URN =		{urn:nbn:de:0030-drops-178784},
  doi =		{10.4230/LIPIcs.SoCG.2023.28},
  annote =	{Keywords: coordinated motion planning, multi-agent path finding, parameterized complexity, disjoint paths on grids}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.23
On Low-End Obfuscation and Learning

Authors: Elette Boyle, Yuval Ishai, Pierre Meyer, Robert Robere, and Gal Yehuda

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Most recent works on cryptographic obfuscation focus on the high-end regime of obfuscating general circuits while guaranteeing computational indistinguishability between functionally equivalent circuits. Motivated by the goals of simplicity and efficiency, we initiate a systematic study of "low-end" obfuscation, focusing on simpler representation models and information-theoretic notions of security. We obtain the following results. - Positive results via "white-box" learning. We present a general technique for obtaining perfect indistinguishability obfuscation from exact learning algorithms that are given restricted access to the representation of the input function. We demonstrate the usefulness of this approach by obtaining simple obfuscation for decision trees and multilinear read-k arithmetic formulas. - Negative results via PAC learning. A proper obfuscation scheme obfuscates programs from a class C by programs from the same class. Assuming the existence of one-way functions, we show that there is no proper indistinguishability obfuscation scheme for k-CNF formulas for any constant k ≥ 3; in fact, even obfuscating 3-CNF by k-CNF is impossible. This result applies even to computationally secure obfuscation, and makes an unexpected use of PAC learning in the context of negative results for obfuscation. - Separations. We study the relations between different information-theoretic notions of indistinguishability obfuscation, giving cryptographic evidence for separations between them.
Cite as

Elette Boyle, Yuval Ishai, Pierre Meyer, Robert Robere, and Gal Yehuda. On Low-End Obfuscation and Learning. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 23:1-23:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{boyle_et_al:LIPIcs.ITCS.2023.23,
  author =	{Boyle, Elette and Ishai, Yuval and Meyer, Pierre and Robere, Robert and Yehuda, Gal},
  title =	{{On Low-End Obfuscation and Learning}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{23:1--23:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.23},
  URN =		{urn:nbn:de:0030-drops-175265},
  doi =		{10.4230/LIPIcs.ITCS.2023.23},
  annote =	{Keywords: Indistinguishability obfuscation, cryptography, learning}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.31
Clustering Permutations: New Techniques with Streaming Applications

Authors: Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We study the classical metric k-median clustering problem over a set of input rankings (i.e., permutations), which has myriad applications, from social-choice theory to web search and databases. A folklore algorithm provides a 2-approximate solution in polynomial time for all k = O(1), and works irrespective of the underlying distance measure, so long it is a metric; however, going below the 2-factor is a notorious challenge. We consider the Ulam distance, a variant of the well-known edit-distance metric, where strings are restricted to be permutations. For this metric, Chakraborty, Das, and Krauthgamer [SODA, 2021] provided a (2-δ)-approximation algorithm for k = 1, where δ≈ 2^{-40}. Our primary contribution is a new algorithmic framework for clustering a set of permutations. Our first result is a 1.999-approximation algorithm for the metric k-median problem under the Ulam metric, that runs in time (k log (nd))^{O(k)} nd³ for an input consisting of n permutations over [d]. In fact, our framework is powerful enough to extend this result to the streaming model (where the n input permutations arrive one by one) using only polylogarithmic (in n) space. Additionally, we show that similar results can be obtained even in the presence of outliers, which is presumably a more difficult problem.
Cite as

Diptarka Chakraborty, Debarati Das, and Robert Krauthgamer. Clustering Permutations: New Techniques with Streaming Applications. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 31:1-31:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ITCS.2023.31,
  author =	{Chakraborty, Diptarka and Das, Debarati and Krauthgamer, Robert},
  title =	{{Clustering Permutations: New Techniques with Streaming Applications}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{31:1--31:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.31},
  URN =		{urn:nbn:de:0030-drops-175340},
  doi =		{10.4230/LIPIcs.ITCS.2023.31},
  annote =	{Keywords: Clustering, Approximation Algorithms, Ulam Distance, Rank Aggregation, Streaming}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.58
An Algorithmic Bridge Between Hamming and Levenshtein Distances

Authors: Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, and Barna Saha

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
The edit distance between strings classically assigns unit cost to every character insertion, deletion, and substitution, whereas the Hamming distance only allows substitutions. In many real-life scenarios, insertions and deletions (abbreviated indels) appear frequently but significantly less so than substitutions. To model this, we consider substitutions being cheaper than indels, with cost 1/a for a parameter a ≥ 1. This basic variant, denoted ED_a, bridges classical edit distance (a = 1) with Hamming distance (a → ∞), leading to interesting algorithmic challenges: Does the time complexity of computing ED_a interpolate between that of Hamming distance (linear time) and edit distance (quadratic time)? What about approximating ED_a? We first present a simple deterministic exact algorithm for ED_a and further prove that it is near-optimal assuming the Orthogonal Vectors Conjecture. Our main result is a randomized algorithm computing a (1+ε)-approximation of ED_a(X,Y), given strings X,Y of total length n and a bound k ≥ ED_a(X,Y). For simplicity, let us focus on k ≥ 1 and a constant ε > 0; then, our algorithm takes Õ(n/a + ak³) time. Unless a = Õ(1), in which case ED_a resembles the standard edit distance, and for the most interesting regime of small enough k, this running time is sublinear in n. We also consider a very natural version that asks to find a (k_I, k_S)-alignment, i.e., an alignment with at most k_I indels and k_S substitutions. In this setting, we give an exact algorithm and, more importantly, an Õ((nk_I)/k_S + k_S k_I³)-time (1,1+ε)-bicriteria approximation algorithm. The latter solution is based on the techniques we develop for ED_a for a = Θ(k_S/k_I), and its running time is again sublinear in n whenever k_I ≪ k_S and the overall distance is small enough. These bounds are in stark contrast to unit-cost edit distance, where state-of-the-art algorithms are far from achieving (1+ε)-approximation in sublinear time, even for a favorable choice of k.
Cite as

Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, and Barna Saha. An Algorithmic Bridge Between Hamming and Levenshtein Distances. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 58:1-58:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{goldenberg_et_al:LIPIcs.ITCS.2023.58,
  author =	{Goldenberg, Elazar and Kociumaka, Tomasz and Krauthgamer, Robert and Saha, Barna},
  title =	{{An Algorithmic Bridge Between Hamming and Levenshtein Distances}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{58:1--58:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.58},
  URN =		{urn:nbn:de:0030-drops-175615},
  doi =		{10.4230/LIPIcs.ITCS.2023.58},
  annote =	{Keywords: edit distance, Hamming distance, Longest Common Extension queries}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.23
Graph Product Structure for h-Framed Graphs

Authors: Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, and Michael Kaufmann

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Graph product structure theory expresses certain graphs as subgraphs of the strong product of much simpler graphs. In particular, an elegant formulation for the corresponding structural theorems involves the strong product of a path and of a bounded treewidth graph, and allows to lift combinatorial results for bounded treewidth graphs to graph classes for which the product structure holds, such as to planar graphs [Dujmović et al., J. ACM, 67(4), 22:1-38, 2020]. In this paper, we join the search for extensions of this powerful tool beyond planarity by considering the h-framed graphs, a graph class that includes 1-planar, optimal 2-planar, and k-map graphs (for appropriate values of h). We establish a graph product structure theorem for h-framed graphs stating that the graphs in this class are subgraphs of the strong product of a path, of a planar graph of treewidth at most 3, and of a clique of size 3⌊ h/2 ⌋+⌊ h/3 ⌋-1. This allows us to improve over the previous structural theorems for 1-planar and k-map graphs. Our results constitute significant progress over the previous bounds on the queue number, non-repetitive chromatic number, and p-centered chromatic number of these graph classes, e.g., we lower the currently best upper bound on the queue number of 1-planar graphs and k-map graphs from 115 to 82 and from ⌊ 33/2(k+3 ⌊ k/2⌋ -3)⌋ to ⌊ 33/2 (3⌊ k/2 ⌋+⌊ k/3 ⌋-1) ⌋, respectively. We also employ the product structure machinery to improve the current upper bounds on the twin-width of 1-planar graphs from O(1) to 80. All our structural results are constructive and yield efficient algorithms to obtain the corresponding decompositions.
Cite as

Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, and Michael Kaufmann. Graph Product Structure for h-Framed Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.ISAAC.2022.23,
  author =	{Bekos, Michael A. and Da Lozzo, Giordano and Hlin\v{e}n\'{y}, Petr and Kaufmann, Michael},
  title =	{{Graph Product Structure for h-Framed Graphs}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.23},
  URN =		{urn:nbn:de:0030-drops-173086},
  doi =		{10.4230/LIPIcs.ISAAC.2022.23},
  annote =	{Keywords: Graph product structure theory, h-framed graphs, k-map graphs, queue number, twin-width}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.47
Finding a Cluster in Incomplete Data

Authors: Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, and Stefan Szeider

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

Abstract
We study two variants of the fundamental problem of finding a cluster in incomplete data. In the problems under consideration, we are given a multiset of incomplete d-dimensional vectors over the binary domain and integers k and r, and the goal is to complete the missing vector entries so that the multiset of complete vectors either contains (i) a cluster of k vectors of radius at most r, or (ii) a cluster of k vectors of diameter at most r. We give tight characterizations of the parameterized complexity of the problems under consideration with respect to the parameters k, r, and a third parameter that captures the missing vector entries.
Cite as

Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, and Stefan Szeider. Finding a Cluster in Incomplete Data. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{eiben_et_al:LIPIcs.ESA.2022.47,
  author =	{Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Ordyniak, Sebastian and Szeider, Stefan},
  title =	{{Finding a Cluster in Incomplete Data}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{47:1--47:14},
  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.47},
  URN =		{urn:nbn:de:0030-drops-169858},
  doi =		{10.4230/LIPIcs.ESA.2022.47},
  annote =	{Keywords: Parameterized complexity, incomplete data, clustering}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2022.1
Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms (Invited Talk)

Authors: Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov

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

Abstract
We discuss recent algorithmic extensions of two classic results of extremal combinatorics about long paths in graphs. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d > 1, is either Hamiltonian or contains a cycle of length at least 2d. Second, the theorem of Erdős-Gallai from 1959, states that a graph G with the average vertex degree D > 1, contains a cycle of length at least D. The proofs of these theorems are constructive, they provide polynomial-time algorithms constructing cycles of lengths 2d and D. We extend these algorithmic results by showing that each of the problems, to decide whether a 2-connected graph contains a cycle of length at least 2d+k or of a cycle of length at least D+k, is fixed-parameter tractable parameterized by k.
Cite as

Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms (Invited Talk). In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 1:1-1:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:LIPIcs.MFCS.2022.1,
  author =	{Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill},
  title =	{{Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{1:1--1:4},
  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.1},
  URN =		{urn:nbn:de:0030-drops-167999},
  doi =		{10.4230/LIPIcs.MFCS.2022.1},
  annote =	{Keywords: Longest path, longest cycle, fixed-parameter tractability, above guarantee parameterization, average degree, dense graph, Dirac theorem, Erd\H{o}s-Gallai theorem}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.6
Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets

Authors: Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi, and Saket Saurabh

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

Abstract
For a connected graph G = (V, E) and s, t ∈ V, a non-separating s-t path is a path P between s and t such that the set of vertices of P does not separate G, that is, G - V(P) is connected. An s-t path P is non-disconnecting if G - E(P) is connected. The problems of finding shortest non-separating and non-disconnecting paths are both known to be NP-hard. In this paper, we consider the problems from the viewpoint of parameterized complexity. We show that the problem of finding a non-separating s-t path of length at most k is W[1]-hard parameterized by k, while the non-disconnecting counterpart is fixed-parameter tractable (FPT) parameterized by k. We also consider the shortest non-separating path problem on several classes of graphs and show that this problem is NP-hard even on bipartite graphs, split graphs, and planar graphs. As for positive results, the shortest non-separating path problem is FPT parameterized by k on planar graphs and on unit disk graphs (where no s, t is given). Further, we give a polynomial-time algorithm on chordal graphs if k is the distance of the shortest path between s and t.
Cite as

Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi, and Saket Saurabh. Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{abhinav_et_al:LIPIcs.MFCS.2022.6,
  author =	{Abhinav, Ankit and Bandopadhyay, Susobhan and Banik, Aritra and Kobayashi, Yasuaki and Nagano, Shunsuke and Otachi, Yota and Saurabh, Saket},
  title =	{{Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{6:1--6: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.6},
  URN =		{urn:nbn:de:0030-drops-168041},
  doi =		{10.4230/LIPIcs.MFCS.2022.6},
  annote =	{Keywords: Non-separating path, Parameterized complexity}
}
  • Refine by Author
  • 11 Ganian, Robert
  • 6 Krauthgamer, Robert
  • 5 Eiben, Eduard
  • 4 Kleinberg, Robert
  • 4 Lhoták, Ondřej
  • Show More...

  • Refine by Classification
  • 13 Theory of computation → Parameterized complexity and exact algorithms
  • 7 Mathematics of computing → Graph algorithms
  • 7 Theory of computation → Graph algorithms analysis
  • 3 Mathematics of computing → Combinatorics
  • 3 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 4 Parameterized complexity
  • 4 fixed-parameter tractability
  • 4 parameterized complexity
  • 3 kernelization
  • 3 twin-width
  • Show More...

  • Refine by Type
  • 102 document

  • Refine by Publication Year
  • 28 2022
  • 19 2015
  • 10 2020
  • 10 2023
  • 8 2021
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact