7 Search Results for "Zych-Pawlewicz, Anna"

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.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.IPEC.2022.5
On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension

Authors: Johannes Blum, Yann Disser, Andreas Emil Feldmann, Siddharth Gupta, and Anna Zych-Pawlewicz

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

Abstract
We consider the Sparse Hitting Set (Sparse-HS) problem, where we are given a set system (V,ℱ,ℬ) with two families ℱ,ℬ of subsets of the universe V. The task is to find a hitting set for ℱ that minimizes the maximum number of elements in any of the sets of ℬ. This generalizes several problems that have been studied in the literature. Our focus is on determining the complexity of some of these special cases of Sparse-HS with respect to the sparseness k, which is the optimum number of hitting set elements in any set of ℬ (i.e., the value of the objective function). For the Sparse Vertex Cover (Sparse-VC) problem, the universe is given by the vertex set V of a graph, and ℱ is its edge set. We prove NP-hardness for sparseness k ≥ 2 and polynomial time solvability for k = 1. We also provide a polynomial-time 2-approximation algorithm for any k. A special case of Sparse-VC is Fair Vertex Cover (Fair-VC), where the family ℬ is given by vertex neighbourhoods. For this problem it was open whether it is FPT (or even XP) parameterized by the sparseness k. We answer this question in the negative, by proving NP-hardness for constant k. We also provide a polynomial-time (2-1/k)-approximation algorithm for Fair-VC, which is better than any approximation algorithm possible for Sparse-VC or the Vertex Cover problem (under the Unique Games Conjecture). We then switch to a different set of problems derived from Sparse-HS related to the highway dimension, which is a graph parameter modelling transportation networks. In recent years a growing literature has shown interesting algorithms for graphs of low highway dimension. To exploit the structure of such graphs, most of them compute solutions to the r-Shortest Path Cover (r-SPC) problem, where r > 0, ℱ contains all shortest paths of length between r and 2r, and ℬ contains all balls of radius 2r. It is known that there is an XP algorithm that computes solutions to r-SPC of sparseness at most h if the input graph has highway dimension h. However it was not known whether a corresponding FPT algorithm exists as well. We prove that r-SPC and also the related r-Highway Dimension (r-HD) problem, which can be used to formally define the highway dimension of a graph, are both W[1]-hard. Furthermore, by the result of Abraham et al. [ICALP 2011] there is a polynomial-time O(log k)-approximation algorithm for r-HD, but for r-SPC such an algorithm is not known. We prove that r-SPC admits a polynomial-time O(log n)-approximation algorithm.
Cite as

Johannes Blum, Yann Disser, Andreas Emil Feldmann, Siddharth Gupta, and Anna Zych-Pawlewicz. On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 5:1-5:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{blum_et_al:LIPIcs.IPEC.2022.5,
  author =	{Blum, Johannes and Disser, Yann and Feldmann, Andreas Emil and Gupta, Siddharth and Zych-Pawlewicz, Anna},
  title =	{{On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{5:1--5:23},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.5},
  URN =		{urn:nbn:de:0030-drops-173612},
  doi =		{10.4230/LIPIcs.IPEC.2022.5},
  annote =	{Keywords: sparse hitting set, fair vertex cover, highway dimension}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.25
Dynamic Coloring of Unit Interval Graphs with Limited Recourse Budget

Authors: Bartłomiej Bosek and Anna Zych-Pawlewicz

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

Abstract
In this paper we study the problem of coloring a unit interval graph which changes dynamically. In our model the unit intervals are added or removed one at the time, and have to be colored immediately, so that no two overlapping intervals share the same color. After each update only a limited number of intervals are allowed to be recolored. The limit on the number of recolorings per update is called the recourse budget. In this paper we show, that if the graph remains k-colorable at all times, the updates consist of insertions only, and the final instance consists of n intervals, then we can achieve an amortized recourse budget of 𝒪({k⁷ log n}) while maintaining a proper coloring with k colors. This is an exponential improvement over the result in [Bartłomiej Bosek et al., 2020] in terms of both k and n. We complement this result by showing the lower bound of Ω(n) on the amortized recourse budget in the fully dynamic setting. Our incremental algorithm can be efficiently implemented. As an additional application of our techniques we include a new combinatorial result on coloring unit circular arc graphs. Let L be the maximum number of arcs intersecting in one point for some set of unit circular arcs 𝒜. We show that if there is a set 𝒜' of non-intersecting unit arcs of size L²-1 such that 𝒜 ∪ 𝒜' does not contain L+1 arcs intersecting in one point, then it is possible to color 𝒜 with L colors. This complements the work on circular arc coloring [Belkale and Chandran, 2009; Tucker, 1975; Valencia-Pabon, 2003], which specifies sufficient conditions needed to color 𝒜 with L+1 colors or more.
Cite as

Bartłomiej Bosek and Anna Zych-Pawlewicz. Dynamic Coloring of Unit Interval Graphs with Limited Recourse Budget. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 25:1-25:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bosek_et_al:LIPIcs.ESA.2022.25,
  author =	{Bosek, Bart{\l}omiej and Zych-Pawlewicz, Anna},
  title =	{{Dynamic Coloring of Unit Interval Graphs with Limited Recourse Budget}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{25:1--25: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.25},
  URN =		{urn:nbn:de:0030-drops-169637},
  doi =		{10.4230/LIPIcs.ESA.2022.25},
  annote =	{Keywords: dynamic algorithms, unit interval graphs, coloring, recourse budget, parametrized dynamic algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.52
Compact Representation for Matrices of Bounded Twin-Width

Authors: Michał Pilipczuk, Marek Sokołowski, and Anna Zych-Pawlewicz

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
For every fixed d ∈ ℕ, we design a data structure that represents a binary n × n matrix that is d-twin-ordered. The data structure occupies 𝒪_d(n) bits, which is the least one could hope for, and can be queried for entries of the matrix in time 𝒪_d(log log n) per query.
Cite as

Michał Pilipczuk, Marek Sokołowski, and Anna Zych-Pawlewicz. Compact Representation for Matrices of Bounded Twin-Width. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 52:1-52:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{pilipczuk_et_al:LIPIcs.STACS.2022.52,
  author =	{Pilipczuk, Micha{\l} and Soko{\l}owski, Marek and Zych-Pawlewicz, Anna},
  title =	{{Compact Representation for Matrices of Bounded Twin-Width}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{52:1--52:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.52},
  URN =		{urn:nbn:de:0030-drops-158620},
  doi =		{10.4230/LIPIcs.STACS.2022.52},
  annote =	{Keywords: twin-width, compact representation, adjacency oracle}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.17
Recoloring Interval Graphs with Limited Recourse Budget

Authors: Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Jakub Pawlewicz, and Anna Zych-Pawlewicz

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
We consider the problem of coloring an interval graph dynamically. Intervals arrive one after the other and have to be colored immediately such that no two intervals of the same color overlap. In each step only a limited number of intervals may be recolored to maintain a proper coloring (thus interpolating between the well-studied online and offline settings). The number of allowed recolorings per step is the so-called recourse budget. Our main aim is to prove both upper and lower bounds on the required recourse budget for interval graphs, given a bound on the allowed number of colors. For general interval graphs with n vertices and chromatic number k it is known that some recoloring is needed even if we have 2k colors available. We give an algorithm that maintains a 2k-coloring with an amortized recourse budget of 𝒪(log n). For maintaining a k-coloring with k ≤ n, we give an amortized upper bound of 𝒪(k⋅ k! ⋅ √n), and a lower bound of Ω(k) for k ∈ 𝒪(√n), which can be as large as Ω(√n). For unit interval graphs it is known that some recoloring is needed even if we have k+1 colors available. We give an algorithm that maintains a (k+1)-coloring with at most 𝒪(k²) recolorings per step in the worst case. We also give a lower bound of Ω(log n) on the amortized recourse budget needed to maintain a k-coloring. Additionally, for general interval graphs we show that if one does not insist on maintaining an explicit coloring, one can have a k-coloring algorithm which does not incur a factor of 𝒪(k ⋅ k! ⋅ √n) in the running time. For this we provide a data structure, which allows for adding intervals in 𝒪(k² log³ n) amortized time per update and querying for the color of a particular interval in 𝒪(log n) time. Between any two updates, the data structure answers consistently with some optimal coloring. The data structure maintains the coloring implicitly, so the notion of recourse budget does not apply to it.
Cite as

Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Jakub Pawlewicz, and Anna Zych-Pawlewicz. Recoloring Interval Graphs with Limited Recourse Budget. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 17:1-17:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bosek_et_al:LIPIcs.SWAT.2020.17,
  author =	{Bosek, Bart{\l}omiej and Disser, Yann and Feldmann, Andreas Emil and Pawlewicz, Jakub and Zych-Pawlewicz, Anna},
  title =	{{Recoloring Interval Graphs with Limited Recourse Budget}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{17:1--17:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.17},
  URN =		{urn:nbn:de:0030-drops-122649},
  doi =		{10.4230/LIPIcs.SWAT.2020.17},
  annote =	{Keywords: Colouring, Dynamic Algorithms, Recourse Budget, Interval Graphs}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.24
An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs

Authors: Nikolai Karpov, Marcin Pilipczuk, and Anna Zych-Pawlewicz

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
Given an edge-weighted graph G with a set Q of k terminals, a mimicking network is a graph with the same set of terminals that exactly preserves the sizes of minimum cuts between any partition of the terminals. A natural question in the area of graph compression is to provide as small mimicking networks as possible for input graph G being either an arbitrary graph or coming from a specific graph class. In this note we show an exponential lower bound for cut mimicking networks in planar graphs: there are edge-weighted planar graphs with k terminals that require 2^(k-2) edges in any mimicking network. This nearly matches an upper bound of O(k * 2^(2k)) of Krauthgamer and Rika [SODA 2013, arXiv:1702.05951] and is in sharp contrast with the O(k^2) upper bound under the assumption that all terminals lie on a single face [Goranci, Henzinger, Peng, arXiv:1702.01136]. As a side result we show a hard instance for the double-exponential upper bounds given by Hagerup, Katajainen, Nishimura, and Ragde [JCSS 1998], Khan and Raghavendra [IPL 2014], and Chambers and Eppstein [JGAA 2013].
Cite as

Nikolai Karpov, Marcin Pilipczuk, and Anna Zych-Pawlewicz. An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 24:1-24:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{karpov_et_al:LIPIcs.IPEC.2017.24,
  author =	{Karpov, Nikolai and Pilipczuk, Marcin and Zych-Pawlewicz, Anna},
  title =	{{An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{24:1--24:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.24},
  URN =		{urn:nbn:de:0030-drops-85603},
  doi =		{10.4230/LIPIcs.IPEC.2017.24},
  annote =	{Keywords: mimicking networks, planar graphs}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2010.61
Vertex Disjoint Paths for Dispatching in Railways

Authors: Holger Flier, Matús Mihalák, Anita Schöbel, Peter Widmayer, and Anna Zych

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
We study variants of the vertex disjoint paths problem in planar graphs where paths have to be selected from a given set of paths. We study the problem as a decision, maximization, and routing-in-rounds problem. Although all considered variants are NP-hard in planar graphs, restrictions on the location of the terminals, motivated by railway applications, lead to polynomially solvable cases for the decision and maximization versions of the problem, and to a $p$-approximation algorithm for the routing-in-rounds problem, where $p$ is the maximum number of alternative paths for a terminal pair.
Cite as

Holger Flier, Matús Mihalák, Anita Schöbel, Peter Widmayer, and Anna Zych. Vertex Disjoint Paths for Dispatching in Railways. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 61-73, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{flier_et_al:OASIcs.ATMOS.2010.61,
  author =	{Flier, Holger and Mihal\'{a}k, Mat\'{u}s and Sch\"{o}bel, Anita and Widmayer, Peter and Zych, Anna},
  title =	{{Vertex Disjoint Paths for Dispatching in Railways}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{61--73},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.61},
  URN =		{urn:nbn:de:0030-drops-27508},
  doi =		{10.4230/OASIcs.ATMOS.2010.61},
  annote =	{Keywords: algorithms, approximation, complexity, graph theory, railways, routing, transportation}
}
  • Refine by Author
  • 6 Zych-Pawlewicz, Anna
  • 2 Bosek, Bartłomiej
  • 2 Disser, Yann
  • 2 Feldmann, Andreas Emil
  • 2 Pilipczuk, Michał
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Fixed parameter tractability
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Data structures design and analysis
  • 1 Theory of computation → Dynamic graph algorithms
  • Show More...

  • Refine by Keyword
  • 1 Closest String
  • 1 Colouring
  • 1 Disjoint Factors
  • 1 Dynamic Algorithms
  • 1 Dynamic data structures
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 3 2022
  • 1 2010
  • 1 2018
  • 1 2020
  • 1 2023

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact