Mgr. Michal Opler, Ph.D.

Proceedings paper

Department of Theoretical Computer Science

In the Multiagent Path Finding (MAPF for short) problem, we focus on efficiently finding non-colliding paths for a set of k agents on a given graph G, where each agent seeks a path from its source vertex to a target. An important measure of the quality of the solution is the length of the proposed schedule l, that is, the length of a longest path (including the waiting time). In this work, we propose a systematic study under the parameterized complexity framework. The hardness results we provide align with many heuristics used for this problem, whose running time could potentially be improved based on our Fixed-Parameter Tractability (FPT) results. We show that MAPF is W[1]-hard with respect to k (even if k is combined with the maximum degree of the input graph). The problem remains NP-hard in planar graphs even if the maximum degree and the makespan l are fixed constants. On the positive side, we show an FPT algorithm for k+l. As we continue, the structure of G comes into play. We give an FPT algorithm for parameter k plus the diameter of the graph G. The MAPF problem is W[1]-hard for cliquewidth of G plus l while it is FPT for treewidth of G plus l.

Proceedings paper

10.1137/1.9781611977912.59

Department of Theoretical Computer Science

We consider the following general model of a sorting procedure: we fix a hereditary permutation class C, which corresponds to the operations that the procedure is allowed to perform in a single step. The input of sorting is a permutation π of the set [n] = {1, 2,…,n}, i.e., a sequence where each element of [n] appears once. In every step, the sorting procedure picks a permutation σ of length n from C, and rearranges the current permutation of numbers by composing it with σ. The goal is to transform the input π into the sorted sequence 1, 2,…,n in as few steps as possible. Formally, for a hereditary permutation class C and a permutation π of [n], we say that C can sort π in k steps, if the inverse of π can be obtained by composing k (not necessarily distinct) permutations from C. The C-sorting time of π, denoted st(C; π), is the smallest k such that C can sort π in k steps; if no such k exists, we put st(C; π) = +∞. For an integer n, the worst-case C-sorting time, denoted wst(C; n), is the maximum of st(C; π) over all permutations π of [n]. This model of sorting captures not only classical sorting algorithms, like insertion sort or bubble sort, but also sorting by series of devices, like stacks or parallel queues, as well as sorting by block operations commonly considered, e.g., in the context of genome rearrangement. Our goal is to describe the possible asymptotic behavior of the function wst(C; n), and relate it to structural properties of C. As the main result, we show that any hereditary permutation class C falls into one of the following five categories: • wst(C; n) = +∞ for n large enough, • wst(C; n) = Θ(n2), • Ω(√n) ≤ wst(C; n) ≤ O(n), • Ω(log n) ≤ wst(C; n) ≤ O(log2 n), or • wst(C; n) = 1 for all n ≥ 2. In addition, we characterize the permutation classes in each of the five categories.

Proceedings paper

10.1007/978-3-031-43380-1_22

Department of Theoretical Computer Science

[Alecu et al.: Graph functionality, JCTB2021] define functionality, a graph parameter that generalizes graph degeneracy. They research the relation of functionality to many other graph parameters (tree-width, clique-width, VC-dimension, etc.). Extending their research, we prove logarithmic lower bound for functionality of the random graph~$G(n,1/2)$. Previously known graphs have functionality logarithmic in number of vertices. We show that for every graph~$G$ on~$n$ vertices we have $\mathrm{fun}(G) \le O(\sqrt{n \log n})$ and we give a nearly matching $\Omega(\sqrt{n})$-lower bound provided by projective planes. Further, we study a related graph parameter \emph{symmetric difference}, the minimum of $|N(u) \Delta N(v)|$ over all pairs of vertices of the ``worst possible'' induced subgraph. It was observed by Alecu et al. that $\mathrm{fun}(G) \le \mathrm{sd}(G)+1$ for every graph~$G$. We compare $\mathrm{fun}$ and $\mathrm{sd}$ for the class~$\mathrm{INT}$ of interval graphs and $\mathrm{CA}$ of circular-arc graphs. We let $\mathrm{INT}_n$ denote the $n$-vertex interval graphs, similarly for $\mathrm{CA}_n$. Alecu et al. ask, whether $\mathrm{fun}(\mathrm{INT})$ is bounded. Dallard et al. answer this positively in a recent preprint. On the other hand, we show that $\Omega(\sqrt[4]{n}) \leq \sd(\mathrm{INT}_n) \leq O(\sqrt[3]{n})$. For the related class $\mathrm{CA}$ we show that $\mathrm{sd}(\mathrm{CA}_n) = \Theta(\sqrt{n})$. We propose a follow-up question: is $\mathrm{fun}(\mathrm{CA})$ bounded?

Proceedings paper

10.1007/978-3-031-49193-1_16

Department of Theoretical Computer Science

We improve bounds for the binary paint shop problem posed by Meunier and Neveu [Computing solutions of the paintshop-necklace problem. Comput. Oper. Res. 39, 11 (2012), 2666-2678]. In particular, we disprove their conjectured upper bound for the number of color changes by giving a linear lower bound. We show that the recursive greedy heuristics is not optimal by providing a tiny improvement. We also introduce a new heuristics, recursive star greedy, that a preliminary analysis shows to be 10% better.