89 Search Results for "Kotrbc�k, Michal"

Document
DOI: 10.4230/LIPIcs.STACS.2024.47
Parameterized and Approximation Algorithms for Coverings Points with Segments in the Plane

Authors: Katarzyna Kowalska and Michał Pilipczuk

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

Abstract
We study parameterized and approximation algorithms for a variant of Set Cover, where the universe of elements to be covered consists of points in the plane and the sets with which the points should be covered are segments. We call this problem Segment Set Cover. We also consider a relaxation of the problem called δ-extension, where we need to cover the points by segments that are extended by a tiny fraction, but we compare the solution’s quality to the optimum without extension. For the unparameterized variant, we prove that Segment Set Cover does not admit a PTAS unless P=NP, even if we restrict segments to be axis-parallel and allow 1/2-extension. On the other hand, we show that parameterization helps for the tractability of Segment Set Cover: we give an FPT algorithm for unweighted Segment Set Cover parameterized by the solution size k, a parameterized approximation scheme for Weighted Segment Set Cover with k being the parameter, and an FPT algorithm for Weighted Segment Set Cover with δ-extension parameterized by k and δ. In the last two results, relaxing the problem is probably necessary: we prove that Weighted Segment Set Cover without any relaxation is W[1]-hard and, assuming ETH, there does not exist an algorithm running in time f(k)⋅ n^{o(k / log k)}. This holds even if one restricts attention to axis-parallel segments.
Cite as

Katarzyna Kowalska and Michał Pilipczuk. Parameterized and Approximation Algorithms for Coverings Points with Segments in the Plane. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kowalska_et_al:LIPIcs.STACS.2024.47,
  author =	{Kowalska, Katarzyna and Pilipczuk, Micha{\l}},
  title =	{{Parameterized and Approximation Algorithms for Coverings Points with Segments in the Plane}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{47:1--47:16},
  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.47},
  URN =		{urn:nbn:de:0030-drops-197572},
  doi =		{10.4230/LIPIcs.STACS.2024.47},
  annote =	{Keywords: Geometric Set Cover, fixed-parameter tractability, weighted parameterized problems, parameterized approximation scheme}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.10
Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs

Authors: Juhi Chaudhary, Harmender Gahlawat, Michal Włodarczyk, and Meirav Zehavi

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

Abstract
Given an undirected graph G and a multiset of k terminal pairs 𝒳, the Vertex-Disjoint Paths (VDP) and Edge-Disjoint Paths (EDP) problems ask whether G has k pairwise internally vertex-disjoint paths and k pairwise edge-disjoint paths, respectively, connecting every terminal pair in 𝒳. In this paper, we study the kernelization complexity of VDP and EDP on subclasses of chordal graphs. For VDP, we design a 4k vertex kernel on split graphs and an 𝒪(k²) vertex kernel on well-partitioned chordal graphs. We also show that the problem becomes polynomial-time solvable on threshold graphs. For EDP, we first prove that the problem is NP-complete on complete graphs. Then, we design an 𝒪(k^{2.75}) vertex kernel for EDP on split graphs, and improve it to a 7k+1 vertex kernel on threshold graphs. Lastly, we provide an 𝒪(k²) vertex kernel for EDP on block graphs and a 2k+1 vertex kernel for clique paths. Our contributions improve upon several results in the literature, as well as resolve an open question by Heggernes et al. [Theory Comput. Syst., 2015].
Cite as

Juhi Chaudhary, Harmender Gahlawat, Michal Włodarczyk, and Meirav Zehavi. Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chaudhary_et_al:LIPIcs.IPEC.2023.10,
  author =	{Chaudhary, Juhi and Gahlawat, Harmender and W{\l}odarczyk, Michal and Zehavi, Meirav},
  title =	{{Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{10:1--10:22},
  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.10},
  URN =		{urn:nbn:de:0030-drops-194296},
  doi =		{10.4230/LIPIcs.IPEC.2023.10},
  annote =	{Keywords: Kernelization, Parameterized Complexity, Vertex-Disjoint Paths Problem, Edge-Disjoint Paths Problem}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.33
A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items

Authors: Mathieu Mari, Timothé Picavet, and Michał Pilipczuk

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

Abstract
We study a natural geometric variant of the classic Knapsack problem called 2D-Knapsack: we are given a set of axis-parallel rectangles and a rectangular bounding box, and the goal is to pack as many of these rectangles inside the box without overlap. Naturally, this problem is NP-complete. Recently, Grandoni et al. [ESA'19] showed that it is also 𝖶[1]-hard when parameterized by the size k of the sought packing, and they presented a parameterized approximation scheme (PAS) for the variant where we are allowed to rotate the rectangles by 90° before packing them into the box. Obtaining a PAS for the original 2D-Knapsack problem, without rotation, appears to be a challenging open question. In this work, we make progress towards this goal by showing a PAS under the following assumptions: - both the box and all the input rectangles have integral, polynomially bounded sidelengths; - every input rectangle is wide - its width is greater than its height; and - the aspect ratio of the box is bounded by a constant. Our approximation scheme relies on a mix of various parameterized and approximation techniques, including color coding, rounding, and searching for a structured near-optimum packing using dynamic programming.
Cite as

Mathieu Mari, Timothé Picavet, and Michał Pilipczuk. A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{mari_et_al:LIPIcs.IPEC.2023.33,
  author =	{Mari, Mathieu and Picavet, Timoth\'{e} and Pilipczuk, Micha{\l}},
  title =	{{A Parameterized Approximation Scheme for the Geometric Knapsack Problem with Wide Items}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{33:1--33:20},
  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.33},
  URN =		{urn:nbn:de:0030-drops-194529},
  doi =		{10.4230/LIPIcs.IPEC.2023.33},
  annote =	{Keywords: Parameterized complexity, Approximation scheme, Geometric knapsack, Color coding, Dynamic programming, Computational geometry}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.22
Languages Given by Finite Automata over the Unary Alphabet

Authors: Wojciech Czerwiński, Maciej Dębski, Tomasz Gogasz, Gordon Hoi, Sanjay Jain, Michał Skrzypczak, Frank Stephan, and Christopher Tan

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
This paper studies the complexity of operations on finite automata and the complexity of their decision problems when the alphabet is unary and n the number of states of the finite automata considered. The following main results are obtained: 1) Equality and inclusion of NFAs can be decided within time 2^O((n log n)^{1/3}); previous upper bound 2^O((n log n)^{1/2}) was by Chrobak (1986) via DFA conversion. 2) The state complexity of operations of UFAs (unambiguous finite automata) increases for complementation and union at most by quasipolynomial; however, for concatenation of two n-state UFAs, the worst case is an UFA of at least 2^Ω(n^{1/6}) states. Previously the upper bounds for complementation and union were exponential-type and this lower bound for concatenation is new.
Cite as

Wojciech Czerwiński, Maciej Dębski, Tomasz Gogasz, Gordon Hoi, Sanjay Jain, Michał Skrzypczak, Frank Stephan, and Christopher Tan. Languages Given by Finite Automata over the Unary Alphabet. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{czerwinski_et_al:LIPIcs.FSTTCS.2023.22,
  author =	{Czerwi\'{n}ski, Wojciech and D\k{e}bski, Maciej and Gogasz, Tomasz and Hoi, Gordon and Jain, Sanjay and Skrzypczak, Micha{\l} and Stephan, Frank and Tan, Christopher},
  title =	{{Languages Given by Finite Automata over the Unary Alphabet}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.22},
  URN =		{urn:nbn:de:0030-drops-193959},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.22},
  annote =	{Keywords: Nondeterministic Finite Automata, Unambiguous Finite Automata, Upper Bounds on Runtime, Conditional Lower Bounds, Languages over the Unary Alphabet}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.42
Single-Exponential FPT Algorithms for Enumerating Secluded ℱ-Free Subgraphs and Deleting to Scattered Graph Classes

Authors: Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
The celebrated notion of important separators bounds the number of small (S,T)-separators in a graph which are "farthest from S" in a technical sense. In this paper, we introduce a generalization of this powerful algorithmic primitive, tailored to undirected graphs, that is phrased in terms of k-secluded vertex sets: sets with an open neighborhood of size at most k. In this terminology, the bound on important separators says that there are at most 4^k maximal k-secluded connected vertex sets C containing S but disjoint from T. We generalize this statement significantly: even when we demand that G[C] avoids a finite set ℱ of forbidden induced subgraphs, the number of such maximal subgraphs is 2^𝒪(k) and they can be enumerated efficiently. This enumeration algorithm allows us to make significant improvements for two problems from the literature. Our first application concerns the Connected k-Secluded ℱ-free subgraph problem, where ℱ is a finite set of forbidden induced subgraphs. Given a graph in which each vertex has a positive integer weight, the problem asks to find a maximum-weight connected k-secluded vertex set C ⊆ V(G) such that G[C] does not contain an induced subgraph isomorphic to any F ∈ ℱ. The parameterization by k is known to be solvable in triple-exponential time via the technique of recursive understanding, which we improve to single-exponential. Our second application concerns the deletion problem to scattered graph classes. A scattered graph class is defined by demanding that every connected component is contained in at least one of the prescribed graph classes Π_1, …, Π_d. The deletion problem to a scattered graph class is to find a vertex set of size at most k whose removal yields a graph from the class. We obtain a single-exponential algorithm whenever each class Π_i is characterized by a finite number of forbidden induced subgraphs. This generalizes and improves upon earlier results in the literature.
Cite as

Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk. Single-Exponential FPT Algorithms for Enumerating Secluded ℱ-Free Subgraphs and Deleting to Scattered Graph Classes. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ISAAC.2023.42,
  author =	{Jansen, Bart M. P. and de Kroon, Jari J. H. and W{\l}odarczyk, Micha{\l}},
  title =	{{Single-Exponential FPT Algorithms for Enumerating Secluded ℱ-Free Subgraphs and Deleting to Scattered Graph Classes}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{42:1--42:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.42},
  URN =		{urn:nbn:de:0030-drops-193440},
  doi =		{10.4230/LIPIcs.ISAAC.2023.42},
  annote =	{Keywords: fixed-parameter tractability, important separators, secluded subgraphs}
}
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.ESA.2023.66
5-Approximation for ℋ-Treewidth Essentially as Fast as ℋ-Deletion Parameterized by Solution Size

Authors: Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk

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

Abstract
The notion of ℋ-treewidth, where ℋ is a hereditary graph class, was recently introduced as a generalization of the treewidth of an undirected graph. Roughly speaking, a graph of ℋ-treewidth at most k can be decomposed into (arbitrarily large) ℋ-subgraphs which interact only through vertex sets of size 𝒪(k) which can be organized in a tree-like fashion. ℋ-treewidth can be used as a hybrid parameterization to develop fixed-parameter tractable algorithms for ℋ-deletion problems, which ask to find a minimum vertex set whose removal from a given graph G turns it into a member of ℋ. The bottleneck in the current parameterized algorithms lies in the computation of suitable tree ℋ-decompositions. We present FPT-approximation algorithms to compute tree ℋ-decompositions for hereditary and union-closed graph classes ℋ. Given a graph of ℋ-treewidth k, we can compute a 5-approximate tree ℋ-decomposition in time f(𝒪(k)) ⋅ n^𝒪(1) whenever ℋ-deletion parameterized by solution size can be solved in time f(k) ⋅ n^𝒪(1) for some function f(k) ≥ 2^k. The current-best algorithms either achieve an approximation factor of k^𝒪(1) or construct optimal decompositions while suffering from non-uniformity with unknown parameter dependence. Using these decompositions, we obtain algorithms solving Odd Cycle Transversal in time 2^𝒪(k) ⋅ n^𝒪(1) parameterized by bipartite-treewidth and Vertex Planarization in time 2^𝒪(k log k) ⋅ n^𝒪(1) parameterized by planar-treewidth, showing that these can be as fast as the solution-size parameterizations and giving the first ETH-tight algorithms for parameterizations by hybrid width measures.
Cite as

Bart M. P. Jansen, Jari J. H. de Kroon, and Michał Włodarczyk. 5-Approximation for ℋ-Treewidth Essentially as Fast as ℋ-Deletion Parameterized by Solution Size. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 66:1-66:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ESA.2023.66,
  author =	{Jansen, Bart M. P. and de Kroon, Jari J. H. and W{\l}odarczyk, Micha{\l}},
  title =	{{5-Approximation for ℋ-Treewidth Essentially as Fast as ℋ-Deletion Parameterized by Solution Size}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{66:1--66:16},
  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.66},
  URN =		{urn:nbn:de:0030-drops-187195},
  doi =		{10.4230/LIPIcs.ESA.2023.66},
  annote =	{Keywords: fixed-parameter tractability, treewidth, graph decompositions}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.22
Streaming k-Edit Approximate Pattern Matching via String Decomposition

Authors: Sudatta Bhattacharya and Michal Koucký

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

Abstract
In this paper we give an algorithm for streaming k-edit approximate pattern matching which uses space Õ(k²) and time Õ(k²) per arriving symbol. This improves substantially on the recent algorithm of Kociumaka, Porat and Starikovskaya [Kociumaka et al., 2022] which uses space Õ(k⁵) and time Õ(k⁸) per arriving symbol. In the k-edit approximate pattern matching problem we get a pattern P and text T and we want to identify all substrings of the text T that are at edit distance at most k from P. In the streaming version of this problem both the pattern and the text arrive in a streaming fashion symbol by symbol and after each symbol of the text we need to report whether there is a current suffix of the text with edit distance at most k from P. We measure the total space needed by the algorithm and time needed per arriving symbol.
Cite as

Sudatta Bhattacharya and Michal Koucký. Streaming k-Edit Approximate Pattern Matching via String Decomposition. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ICALP.2023.22,
  author =	{Bhattacharya, Sudatta and Kouck\'{y}, Michal},
  title =	{{Streaming k-Edit Approximate Pattern Matching via String Decomposition}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{22:1--22:14},
  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.22},
  URN =		{urn:nbn:de:0030-drops-180741},
  doi =		{10.4230/LIPIcs.ICALP.2023.22},
  annote =	{Keywords: Approximate pattern matching, edit distance, streaming algorithms}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.135
Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes

Authors: Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, and Szymon Toruńczyk

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

Abstract
We use model-theoretic tools originating from stability theory to derive a result we call the Finitary Substitute Lemma, which intuitively says the following. Suppose we work in a stable graph class 𝒞, and using a first-order formula φ with parameters we are able to define, in every graph G ∈ 𝒞, a relation R that satisfies some hereditary first-order assertion ψ. Then we are able to find a first-order formula φ' that has the same property, but additionally is finitary: there is finite bound k ∈ ℕ such that in every graph G ∈ 𝒞, different choices of parameters give only at most k different relations R that can be defined using φ'. We use the Finitary Substitute Lemma to derive two corollaries about the existence of certain canonical decompositions in classes of well-structured graphs. - We prove that in the Splitter game, which characterizes nowhere dense graph classes, and in the Flipper game, which characterizes monadically stable graph classes, there is a winning strategy for Splitter, respectively Flipper, that can be defined in first-order logic from the game history. Thus, the strategy is canonical. - We show that for any fixed graph class 𝒞 of bounded shrubdepth, there is an 𝒪(n²)-time algorithm that given an n-vertex graph G ∈ 𝒞, computes in an isomorphism-invariant way a structure H of bounded treedepth in which G can be interpreted. A corollary of this result is an 𝒪(n²)-time isomorphism test and canonization algorithm for any fixed class of bounded shrubdepth.
Cite as

Pierre Ohlmann, Michał Pilipczuk, Wojciech Przybyszewski, and Szymon Toruńczyk. Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 135:1-135:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ohlmann_et_al:LIPIcs.ICALP.2023.135,
  author =	{Ohlmann, Pierre and Pilipczuk, Micha{\l} and Przybyszewski, Wojciech and Toru\'{n}czyk, Szymon},
  title =	{{Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{135:1--135: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.135},
  URN =		{urn:nbn:de:0030-drops-181874},
  doi =		{10.4230/LIPIcs.ICALP.2023.135},
  annote =	{Keywords: Model Theory, Stability Theory, Shrubdepth, Nowhere Dense, Monadically Stable}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.24
On Rational Recursive Sequences

Authors: Lorenzo Clemente, Maria Donten-Bury, Filip Mazowiecki, and Michał Pilipczuk

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

Abstract
We study the class of rational recursive sequences (ratrec) over the rational numbers. A ratrec sequence is defined via a system of sequences using mutually recursive equations of depth 1, where the next values are computed as rational functions of the previous values. An alternative class is that of simple ratrec sequences, where one uses a single recursive equation, however of depth k: the next value is defined as a rational function of k previous values. We conjecture that the classes ratrec and simple ratrec coincide. The main contribution of this paper is a proof of a variant of this conjecture where the initial conditions are treated symbolically, using a formal variable per sequence, while the sequences themselves consist of rational functions over those variables. While the initial conjecture does not follow from this variant, we hope that the introduced algebraic techniques may eventually be helpful in resolving the problem. The class ratrec strictly generalises a well-known class of polynomial recursive sequences (polyrec). These are defined like ratrec, but using polynomial functions instead of rational ones. One can observe that if our conjecture is true and effective, then we can improve the complexities of the zeroness and the equivalence problems for polyrec sequences. Currently, the only known upper bound is Ackermanian, which follows from results on polynomial automata. We complement this observation by proving a PSPACE lower bound for both problems for polyrec. Our lower bound construction also implies that the Skolem problem is PSPACE-hard for the polyrec class.
Cite as

Lorenzo Clemente, Maria Donten-Bury, Filip Mazowiecki, and Michał Pilipczuk. On Rational Recursive Sequences. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 24:1-24:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{clemente_et_al:LIPIcs.STACS.2023.24,
  author =	{Clemente, Lorenzo and Donten-Bury, Maria and Mazowiecki, Filip and Pilipczuk, Micha{\l}},
  title =	{{On Rational Recursive Sequences}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{24:1--24:21},
  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.24},
  URN =		{urn:nbn:de:0030-drops-176763},
  doi =		{10.4230/LIPIcs.STACS.2023.24},
  annote =	{Keywords: recursive sequences, polynomial automata, zeroness problem, equivalence problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.46
Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex Number

Authors: Konrad Majewski, Michał Pilipczuk, and Marek Sokołowski

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

Abstract
Let 𝜑 be a sentence of CMSO₂ (monadic second-order logic with quantification over edge subsets and counting modular predicates) over the signature of graphs. We present a dynamic data structure that for a given graph G that is updated by edge insertions and edge deletions, maintains whether 𝜑 is satisfied in G. The data structure is required to correctly report the outcome only when the feedback vertex number of G does not exceed a fixed constant k, otherwise it reports that the feedback vertex number is too large. With this assumption, we guarantee amortized update time O_{𝜑,k}(log n). By combining this result with a classic theorem of Erdős and Pósa, we give a fully dynamic data structure that maintains whether a graph contains a packing of k vertex-disjoint cycles with amortized update time O_k(log n). Our data structure also works in a larger generality of relational structures over binary signatures.
Cite as

Konrad Majewski, Michał Pilipczuk, and Marek Sokołowski. Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex Number. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{majewski_et_al:LIPIcs.STACS.2023.46,
  author =	{Majewski, Konrad and Pilipczuk, Micha{\l} and Soko{\l}owski, Marek},
  title =	{{Maintaining CMSO₂ Properties on Dynamic Structures with Bounded Feedback Vertex Number}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{46:1--46:13},
  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.46},
  URN =		{urn:nbn:de:0030-drops-176981},
  doi =		{10.4230/LIPIcs.STACS.2023.46},
  annote =	{Keywords: feedback vertex set, CMSO₂ formula, data structure, dynamic graphs, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.50
Dynamic Data Structures for Parameterized String Problems

Authors: Jędrzej Olkowski, Michał Pilipczuk, Mateusz Rychlicki, Karol Węgrzycki, and Anna Zych-Pawlewicz

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

Abstract
We revisit classic string problems considered in the area of parameterized complexity, and study them through the lens of dynamic data structures. That is, instead of asking for a static algorithm that solves the given instance efficiently, our goal is to design a data structure that efficiently maintains a solution, or reports a lack thereof, upon updates in the instance. We first consider the CLOSEST STRING problem, for which we design randomized dynamic data structures with amortized update times d^𝒪(d) and |Σ|^𝒪(d), respectively, where Σ is the alphabet and d is the assumed bound on the maximum distance. These are obtained by combining known static approaches to CLOSEST STRING with color-coding. Next, we note that from a result of Frandsen et al. [J. ACM'97] one can easily infer a meta-theorem that provides dynamic data structures for parameterized string problems with worst-case update time of the form 𝒪_k(log log n), where k is the parameter in question and n is the length of the string. We showcase the utility of this meta-theorem by giving such data structures for problems DISJOINT FACTORS and EDIT DISTANCE. We also give explicit data structures for these problems, with worst-case update times 𝒪(k 2^k log log n) and 𝒪(k²log log n), respectively. Finally, we discuss how a lower bound methodology introduced by Amarilli et al. [ICALP'21] can be used to show that obtaining update time 𝒪(f(k)) for DISJOINT FACTORS and EDIT DISTANCE is unlikely already for a constant value of the parameter k.
Cite as

Jędrzej Olkowski, Michał Pilipczuk, Mateusz Rychlicki, Karol Węgrzycki, and Anna Zych-Pawlewicz. Dynamic Data Structures for Parameterized String Problems. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 50:1-50:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{olkowski_et_al:LIPIcs.STACS.2023.50,
  author =	{Olkowski, J\k{e}drzej and Pilipczuk, Micha{\l} and Rychlicki, Mateusz and W\k{e}grzycki, Karol and Zych-Pawlewicz, Anna},
  title =	{{Dynamic Data Structures for Parameterized String Problems}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{50:1--50:22},
  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.50},
  URN =		{urn:nbn:de:0030-drops-177026},
  doi =		{10.4230/LIPIcs.STACS.2023.50},
  annote =	{Keywords: Parameterized algorithms, Dynamic data structures, String problems, Closest String, Edit Distance, Disjoint Factors, Predecessor problem}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.14
Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws

Authors: Michał Dębski, Zbigniew Lonc, Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski

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

Abstract
For graphs G and H, an H-coloring of G is an edge-preserving mapping from V(G) to V(H). In the H-Coloring problem the graph H is fixed and we ask whether an instance graph G admits an H-coloring. A generalization of this problem is H-ColoringExt, where some vertices of G are already mapped to vertices of H and we ask if this partial mapping can be extended to an H-coloring. We study the complexity of variants of H-Coloring in F-free graphs, i.e., graphs excluding a fixed graph F as an induced subgraph. For integers a,b,c ⩾ 1, by S_{a,b,c} we denote the graph obtained by identifying one endvertex of three paths on a+1, b+1, and c+1 vertices, respectively. For odd k ⩾ 5, by W_k we denote the graph obtained from the k-cycle by adding a universal vertex. As our main algorithmic result we show that W_5-ColoringExt is polynomial-time solvable in S_{2,1,1}-free graphs. This result exhibits an interesting non-monotonicity of H-ColoringExt with respect to taking induced subgraphs of H. Indeed, W_5 contains a triangle, and K_3-Coloring, i.e., classical 3-coloring, is NP-hard already in claw-free (i.e., S_{1,1,1}-free) graphs. Our algorithm is based on two main observations: 1) W_5-ColoringExt in S_{2,1,1}-free graphs can be in polynomial time reduced to a variant of the problem of finding an independent set intersecting all triangles, and 2) the latter problem can be solved in polynomial time in S_{2,1,1}-free graphs. We complement this algorithmic result with several negative ones. In particular, we show that W_5-Coloring is NP-hard in P_t-free graphs for some constant t and W_5-ColoringExt is NP-hard in S_{3,3,3}-free graphs of bounded degree. This is again uncommon, as usually problems that are NP-hard in S_{a,b,c}-free graphs for some constant a,b,c are already hard in claw-free graphs
Cite as

Michał Dębski, Zbigniew Lonc, Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski. Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{debski_et_al:LIPIcs.ISAAC.2022.14,
  author =	{D\k{e}bski, Micha{\l} and Lonc, Zbigniew and Okrasa, Karolina and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Computing Homomorphisms in Hereditary Graph Classes: The Peculiar Case of the 5-Wheel and Graphs with No Long Claws}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{14:1--14:16},
  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.14},
  URN =		{urn:nbn:de:0030-drops-172996},
  doi =		{10.4230/LIPIcs.ISAAC.2022.14},
  annote =	{Keywords: graph homomorphism, forbidden induced subgraphs, precoloring extension}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2022.6
On the Complexity of Problems on Tree-Structured Graphs

Authors: Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Michał Pilipczuk

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

Abstract
In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in f(k)n^O(1) time and f(k)log n space on a non-deterministic Turing Machine with access to an auxiliary stack (with only top element lookup allowed). Various natural problems on "tree-structured graphs" are complete for this class: we show that List Coloring and All-or-Nothing Flow parameterized by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set parameterized by treewidth divided by log n, and Max Cut parameterized by cliquewidth are also XALP-complete. Besides finding a "natural home" for these problems, we also pave the road for future reductions. We give a number of equivalent characterisations of the class XALP, e.g., XALP is the class of problems solvable by an Alternating Turing Machine whose runs have tree size at most f(k)n^O(1) and use f(k)log n space. Moreover, we introduce "tree-shaped" variants of Weighted CNF-Satisfiability and Multicolor Clique that are XALP-complete.
Cite as

Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Michał Pilipczuk. On the Complexity of Problems on Tree-Structured Graphs. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2022.6,
  author =	{Bodlaender, Hans L. and Groenland, Carla and Jacob, Hugo and Pilipczuk, Marcin and Pilipczuk, Micha{\l}},
  title =	{{On the Complexity of Problems on Tree-Structured Graphs}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.6},
  URN =		{urn:nbn:de:0030-drops-173626},
  doi =		{10.4230/LIPIcs.IPEC.2022.6},
  annote =	{Keywords: Parameterized Complexity, Treewidth, XALP, XNLP}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.54
The Hamilton Compression of Highly Symmetric Graphs

Authors: Petr Gregor, Arturo Merino, and Torsten Mütze

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

Abstract
We say that a Hamilton cycle C = (x₁,…,x_n) in a graph G is k-symmetric, if the mapping x_i ↦ x_{i+n/k} for all i = 1,…,n, where indices are considered modulo n, is an automorphism of G. In other words, if we lay out the vertices x₁,…,x_n equidistantly on a circle and draw the edges of G as straight lines, then the drawing of G has k-fold rotational symmetry, i.e., all information about the graph is compressed into a 360^∘/k wedge of the drawing. We refer to the maximum k for which there exists a k-symmetric Hamilton cycle in G as the Hamilton compression of G. We investigate the Hamilton compression of four different families of vertex-transitive graphs, namely hypercubes, Johnson graphs, permutahedra and Cayley graphs of abelian groups. In several cases we determine their Hamilton compression exactly, and in other cases we provide close lower and upper bounds. The cycles we construct have a much higher compression than several classical Gray codes known from the literature. Our constructions also yield Gray codes for bitstrings, combinations and permutations that have few tracks and/or that are balanced.
Cite as

Petr Gregor, Arturo Merino, and Torsten Mütze. The Hamilton Compression of Highly Symmetric Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.MFCS.2022.54,
  author =	{Gregor, Petr and Merino, Arturo and M\"{u}tze, Torsten},
  title =	{{The Hamilton Compression of Highly Symmetric Graphs}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{54:1--54:14},
  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.54},
  URN =		{urn:nbn:de:0030-drops-168529},
  doi =		{10.4230/LIPIcs.MFCS.2022.54},
  annote =	{Keywords: Hamilton cycle, Gray code, hypercube, permutahedron, Johnson graph, Cayley graph, abelian group, vertex-transitive}
}
  • Refine by Author
  • 16 Pilipczuk, Michał
  • 10 Pilipczuk, Michal
  • 8 Koucký, Michal
  • 6 Pilipczuk, Marcin
  • 6 Włodarczyk, Michał
  • Show More...

  • Refine by Classification
  • 22 Theory of computation → Parameterized complexity and exact algorithms
  • 13 Theory of computation → Fixed parameter tractability
  • 11 Mathematics of computing → Graph algorithms
  • 10 Theory of computation → Graph algorithms analysis
  • 8 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 11 fixed-parameter tractability
  • 9 parameterized complexity
  • 5 kernelization
  • 4 Parameterized Complexity
  • 4 treewidth
  • Show More...

  • Refine by Type
  • 89 document

  • Refine by Publication Year
  • 29 2019
  • 12 2021
  • 11 2022
  • 11 2023
  • 8 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact