Search Results

Documents authored by Pekárek, Jakub

Document
DOI: 10.4230/LIPIcs.SoCG.2022.39
Weak Coloring Numbers of Intersection Graphs

Authors: Zdeněk Dvořák, Jakub Pekárek, Torsten Ueckerdt, and Yelena Yuditsky

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Weak and strong coloring numbers are generalizations of the degeneracy of a graph, where for a positive integer k, we seek a vertex ordering such that every vertex can (weakly respectively strongly) reach in k steps only few vertices that precede it in the ordering. Both notions capture the sparsity of a graph or a graph class, and have interesting applications in structural and algorithmic graph theory. Recently, Dvořák, McCarty, and Norin observed a natural volume-based upper bound for the strong coloring numbers of intersection graphs of well-behaved objects in ℝ^d, such as homothets of a compact convex object, or comparable axis-aligned boxes. In this paper, we prove upper and lower bounds for the k-th weak coloring numbers of these classes of intersection graphs. As a consequence, we describe a natural graph class whose strong coloring numbers are polynomial in k, but the weak coloring numbers are exponential. We also observe a surprising difference in terms of the dependence of the weak coloring numbers on the dimension between touching graphs of balls (single-exponential) and hypercubes (double-exponential).
Cite as

Zdeněk Dvořák, Jakub Pekárek, Torsten Ueckerdt, and Yelena Yuditsky. Weak Coloring Numbers of Intersection Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.SoCG.2022.39,
  author =	{Dvo\v{r}\'{a}k, Zden\v{e}k and Pek\'{a}rek, Jakub and Ueckerdt, Torsten and Yuditsky, Yelena},
  title =	{{Weak Coloring Numbers of Intersection Graphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.39},
  URN =		{urn:nbn:de:0030-drops-160477},
  doi =		{10.4230/LIPIcs.SoCG.2022.39},
  annote =	{Keywords: geometric intersection graphs, weak and strong coloring numbers}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2021.22
Long Paths Make Pattern-Counting Hard, and Deep Trees Make It Harder

Authors: Vít Jelínek, Michal Opler, and Jakub Pekárek

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
We study the counting problem known as #PPM, whose input is a pair of permutations π and τ (called pattern and text, respectively), and the task is to find the number of subsequences of τ that have the same relative order as π. A simple brute-force approach solves #PPM for a pattern of length k and a text of length n in time O(n^{k+1}), while Berendsohn, Kozma and Marx have recently shown that under the exponential time hypothesis (ETH), it cannot be solved in time f(k) n^{o(k/log k)} for any function f. In this paper, we consider the restriction of #PPM, known as 𝒞-Pattern #PPM, where the pattern π must belong to a hereditary permutation class 𝒞. Our goal is to identify the structural properties of 𝒞 that determine the complexity of 𝒞-Pattern #PPM. We focus on two such structural properties, known as the long path property (LPP) and the deep tree property (DTP). Assuming ETH, we obtain these results: 1) If 𝒞 has the LPP, then 𝒞-Pattern #PPM cannot be solved in time f(k)n^{o(√k)} for any function f, and 2) if 𝒞 has the DTP, then 𝒞-Pattern #PPM cannot be solved in time f(k)n^{o(k/log² k)} for any function f. Furthermore, when 𝒞 is one of the so-called monotone grid classes, we show that if 𝒞 has the LPP but not the DTP, then 𝒞-Pattern #PPM can be solved in time f(k)n^{O(√ k)}. In particular, the lower bounds above are tight up to the polylog terms in the exponents.
Cite as

Vít Jelínek, Michal Opler, and Jakub Pekárek. Long Paths Make Pattern-Counting Hard, and Deep Trees Make It Harder. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jelinek_et_al:LIPIcs.IPEC.2021.22,
  author =	{Jel{\'\i}nek, V{\'\i}t and Opler, Michal and Pek\'{a}rek, Jakub},
  title =	{{Long Paths Make Pattern-Counting Hard, and Deep Trees Make It Harder}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.22},
  URN =		{urn:nbn:de:0030-drops-154050},
  doi =		{10.4230/LIPIcs.IPEC.2021.22},
  annote =	{Keywords: Permutation pattern matching, subexponential algorithm, conditional lower bounds, tree-width}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.65
Griddings of Permutations and Hardness of Pattern Matching

Authors: Vít Jelínek, Michal Opler, and Jakub Pekárek

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We study the complexity of the decision problem known as Permutation Pattern Matching, or PPM. The input of PPM consists of a pair of permutations τ (the "text") and π (the "pattern"), and the goal is to decide whether τ contains π as a subpermutation. On general inputs, PPM is known to be NP-complete by a result of Bose, Buss and Lubiw. In this paper, we focus on restricted instances of PPM where the text is assumed to avoid a fixed (small) pattern σ; this restriction is known as Av(σ)-PPM. It has been previously shown that Av(σ)-PPM is polynomial for any σ of size at most 3, while it is NP-hard for any σ containing a monotone subsequence of length four. In this paper, we present a new hardness reduction which allows us to show, in a uniform way, that Av(σ)-PPM is hard for every σ of size at least 6, for every σ of size 5 except the symmetry class of 41352, as well as for every σ symmetric to one of the three permutations 4321, 4312 and 4231. Moreover, assuming the exponential time hypothesis, none of these hard cases of Av(σ)-PPM can be solved in time 2^o(n/log n). Previously, such conditional lower bound was not known even for the unconstrained PPM problem. On the tractability side, we combine the CSP approach of Guillemot and Marx with the structural results of Huczynska and Vatter to show that for any monotone-griddable permutation class 𝒞, PPM is polynomial when the text is restricted to a permutation from 𝒞.
Cite as

Vít Jelínek, Michal Opler, and Jakub Pekárek. Griddings of Permutations and Hardness of Pattern Matching. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 65:1-65:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jelinek_et_al:LIPIcs.MFCS.2021.65,
  author =	{Jel{\'\i}nek, V{\'\i}t and Opler, Michal and Pek\'{a}rek, Jakub},
  title =	{{Griddings of Permutations and Hardness of Pattern Matching}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{65:1--65:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.65},
  URN =		{urn:nbn:de:0030-drops-145050},
  doi =		{10.4230/LIPIcs.MFCS.2021.65},
  annote =	{Keywords: Permutation, pattern matching, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.52
A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes

Authors: Vít Jelínek, Michal Opler, and Jakub Pekárek

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Permutation Pattern Matching (PPM) is the problem of deciding for a given pair of permutations π and τ whether the pattern π is contained in the text τ. Bose, Buss and Lubiw showed that PPM is NP-complete. In view of this result, it is natural to ask how the situation changes when we restrict the pattern π to a fixed permutation class 𝒞; this is known as the 𝒞-Pattern PPM problem. There have been several results in this direction, namely the work of Jelínek and Kynčl who completely resolved the hardness of 𝒞-Pattern PPM when 𝒞 is taken to be the class of σ-avoiding permutations for some σ. Grid classes are special kind of permutation classes, consisting of permutations admitting a grid-like decomposition into simpler building blocks. Of particular interest are the so-called monotone grid classes, in which each building block is a monotone sequence. Recently, it has been discovered that grid classes, especially the monotone ones, play a fundamental role in the understanding of the structure of general permutation classes. This motivates us to study the hardness of 𝒞-Pattern PPM for a (monotone) grid class 𝒞. We provide a complexity dichotomy for 𝒞-Pattern PPM when 𝒞 is taken to be a monotone grid class. Specifically, we show that the problem is polynomial-time solvable if a certain graph associated with 𝒞, called the cell graph, is a forest, and it is NP-complete otherwise. We further generalize our results to grid classes whose blocks belong to classes of bounded grid-width. We show that the 𝒞-Pattern PPM for such a grid class 𝒞 is polynomial-time solvable if the cell graph of 𝒞 avoids a cycle or a certain special type of path, and it is NP-complete otherwise.
Cite as

Vít Jelínek, Michal Opler, and Jakub Pekárek. A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 52:1-52:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{jelinek_et_al:LIPIcs.MFCS.2020.52,
  author =	{Jel{\'\i}nek, V{\'\i}t and Opler, Michal and Pek\'{a}rek, Jakub},
  title =	{{A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{52:1--52:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.52},
  URN =		{urn:nbn:de:0030-drops-127186},
  doi =		{10.4230/LIPIcs.MFCS.2020.52},
  annote =	{Keywords: permutations, pattern matching, grid classes}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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