Source author record

Marcin Smulewicz

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

3works

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

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.