Source author record

Wojciech Nadara

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Discrete Mathematics math.CO

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Computing treedepth in polynomial space and linear fpt time

The treedepth of a graph $G$ is the least possible depth of an elimination forest of $G$ : a rooted forest on the same vertex set where every pair of vertices adjacent in $G$ is bound by the ancestor/descendant relation. We propose an algorithm that given a graph $G$ and an integer $d$ , either finds an elimination forest of $G$ of depth at most $d$ or concludes that no such forest exists; thus the algorithm decides whether the treedepth of $G$ is at most $d$ . The running time is $2^{O(d^2)}\cdot n^{O(1)}$ and the space usage is polynomial in $n$ . Further, by allowing randomization, the time and space complexities can be improved to $2^{O(d^2)}\cdot n$ and $d^{O(1)}\cdot n$ , respectively. This improves upon the algorithm of Reidl et al. [ICALP 2014], which also has time complexity $2^{O(d^2)}\cdot n$ , but uses exponential space.

preprint2020arXiv

Decreasing the maximum average degree by deleting an independent set or a d-degenerate subgraph

The maximum average degree $\mathrm{mad}(G)$ of a graph $G$ is the maximum average degree over all subgraphs of $G$ . In this paper we prove that for every $G$ and positive integer $k$ such that $\mathrm{mad}(G) \ge k$ there exists $S \subseteq V(G)$ such that $\mathrm{mad}(G - S) \le \mathrm{mad}(G) - k$ and $G[S]$ is $(k-1)$ -degenerate. Moreover, such $S$ can be computed in polynomial time. In particular there exists an independent set $I$ in $G$ such that $\mathrm{mad}(G-I) \le \mathrm{mad}(G)-1$ and an induced forest $F$ such that $\mathrm{mad}(G-F) \le \mathrm{mad}(G) - 2$ .

preprint2020arXiv

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

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 $2^{{\cal O}(d^2)}$ , 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^{{\cal 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 $2^{{\cal O}(k^2)}$ . In the second case, the amortized update time is $2^{{\cal O}(k^4)} + {\cal O}(k \log n)$ . In both cases we assume access to a dictionary on the edges of $G$ .

preprint2020arXiv

Many visits TSP revisited

We study the Many Visits TSP problem, where given a number $k(v)$ for each of $n$ cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that visits each city $v$ exactly $k(v)$ times. The currently fastest algorithm is due to Berger, Kozma, Mnich and Vincze [SODA 2019, TALG 2020] and runs in time and space $\mathcal{O}^*(5^n)$ . They also show a polynomial space algorithm running in time $\mathcal{O}^*(16^{n+o(n)})$ . In this work, we show three main results: (i) A randomized polynomial space algorithm in time $\mathcal{O}^*(2^nD)$ , where $D$ is the maximum distance between two cities. By using standard methods, this results in $(1+ε)$ -approximation in time $\mathcal{O}^*(2^nε^{-1})$ . Improving the constant $2$ in these results would be a major breakthrough, as it would result in improving the $\mathcal{O}^*(2^n)$ -time algorithm for Directed Hamiltonian Cycle, which is a 50 years old open problem. (ii) A tight analysis of Berger et al.'s exponential space algorithm, resulting in $\mathcal{O}^*(4^n)$ running time bound. (iii) A new polynomial space algorithm, running in time $\mathcal{O}(7.88^n)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Wojciech Nadara

Research overview

Is this your work?

4 publications

Computing treedepth in polynomial space and linear fpt time

Decreasing the maximum average degree by deleting an independent set or a d-degenerate subgraph

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

Many visits TSP revisited

See the researcher in context

Building this map preview