Anna Zych

SODA Conference 2023 Conference Paper

Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours

• François Dross
• Krzysztof Fleszar 0001
• Karol Wegrzycki
• Anna Zych

In this paper, we study problems of connecting classes of points via noncrossing structures. Given a set of colored terminal points, we want to find a graph for each color that connects all terminals of its color with the restriction that no two graphs cross each other. We consider these problems both on the Euclidean plane and in planar graphs. On the algorithmic side, we give a Gap-ETH-tight EPTAS for the bicolored noncrossing travelling salesman tours problem as well as for the red-blue-green separation problem (in which we want to separate terminals of three colors with two noncrossing polygons of minimum length), both on the Euclidean plane. This improves the work of Arora and Chang (ICALP 2003) who gave a slower PTAS for the simpler red-blue separation problem. For the case of unweighted plane graphs, we also show a PTAS for the bicolored noncrossing travelling salesman tours problem. All these results are based on our new patching procedure that might be of independent interest. On the negative side, we show that the problem of connecting terminal pairs with noncrossing paths is NP-hard on the Euclidean plane, and that the problem of finding two noncrossing spanning trees is NP-hard in plane graphs.

SODA Conference 2021 Conference Paper

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles

• Jiehua Chen 0001
• Wojciech Czerwinski
• Yann Disser
• Andreas Emil Feldmann
• Danny Hermelin
• Wojciech Nadara
• Marcin Pilipczuk
• Michal Pilipczuk

We present a data structure that in a dynamic graph of treedepth at most d, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case update time, which matches the best known parameter dependency in the running time of a static fpt algorithm for computing the treedepth of a graph. This improves a result of Dvořák et al. [ESA 2014], who for the same problem achieved update time f ( d ) for some non-elementary (i. e. tower-exponential) function f. As a by-product, we improve known upper bounds on the sizes of minimal obstructions for having treedepth d from doubly-exponential in d to d O ( d ). As applications, we design new fully dynamic parameterized data structures for detecting long paths and cycles in general graphs. More precisely, for a fixed parameter k and a dynamic graph G, modified over time by edge insertions and deletions, our data structures maintain answers to the following queries: Does G contain a simple path on k vertices? Does G contain a simple cycle on at least k vertices? In the first case, the data structure achieves amortized update time. In the second case, the amortized update time is. In both cases we assume access to a dictionary on the edges of G.

STOC Conference 2015 Conference Paper

The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree

• Jakub Lacki
• Jakub Ocwieja
• Marcin Pilipczuk
• Piotr Sankowski
• Anna Zych

FOCS Conference 2014 Conference Paper

Online Bipartite Matching in Offline Time

• Bartlomiej Bosek
• Dariusz Leniowski
• Piotr Sankowski
• Anna Zych

This paper investigates the problem of maintaining maximum size matchings in incremental bipartite graphs. In this problem a bipartite graph G between n clients and n servers is revealed online. The clients arrive in an arbitrary order and request to be matched to a subset of servers. In our model we allow the clients to switch between servers and want to maximize the matching size between them, i. e. , after a client arrives we find an augmenting path from a client to a free server. Our goals in this model are twofold. First, we want to minimize the number of times clients are reallocated between the servers. Second, we want to give fast algorithms that recompute such reallocation. As for the number of changes, we propose a greedy algorithm that chooses an augmenting path π that minimizes the maximum number of times each server in π was used by augmenting paths so far. We show that in this algorithm each server has its client reassigned O(√n) times. This gives an O(n 3/2 ) bound on the total number of changes, what gives a progress towards the main open question risen by Chaudhuri et al. (INFOCOM'09) who asked to prove O(n log n) upper bound. Next, we argue that the same bound holds in the decremental case. Moreover, we show incremental and decremental algorithms that maintain (1 - ε)-approximate matching with total of O(ε -1 n) reallocations, for any ε > 0. Finally, we address the question of how to efficiently compute paths given by this greedy algorithm. We show that by introducing proper amortization we can obtain an incremental algorithm that maintains the maximum size matching in total O(√nm) time. This matches the running time of one of the fastest static maximum matching algorithms that was given by Hopcroft and Karp (SIAM J. Comput '73). We extend our result to decremental case where we give the same total bound on the running time. Additionally, we show O(ε -1 m) time incremental and decremental algorithms that maintain (1 - ε)-approximate matching for any ε > 0. Observe that this bound matches the running time of the fastest approximate static solution as well.

MFCS Conference 2012 Conference Paper

New Advances in Reoptimizing the Minimum Steiner Tree Problem

• Davide Bilò
• Anna Zych

Abstract In this paper we improve the results in the literature concerning the problem of computing the minimum Steiner tree given the minimum Steiner tree for a similar problem instance. Using a σ -approximation algorithm computing the minimum Steiner tree from scratch, we provide a \(\left(\frac{3 \sigma-1}{2 \sigma-1}+\epsilon\right)\) and a \(\left(\frac{2 \sigma-1}{\sigma}+\epsilon\right)\) -approximation algorithm for altering the instance by removing a vertex from the terminal set and by increasing the cost of an edge, respectively. If we use the best up to date σ = ln 4 + ε, our ratios equal 1. 218 and 1. 279 respectively.