Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology
Authors
Year
2024
Published
Proceedings of the 38th AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press, 2024. p. 17380-17388. ISSN 2159-5399.
Type
Proceedings paper
Departments
Annotation
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.
The Hierarchy of Hereditary Sorting Operators
Authors
Jelínek, V.; Opler, M.; Pekárek, J.
Year
2024
Published
Proceedings of the 35th ACM-SIAM Symposium on Discrete Algorithms, SODA ’24. Philadelphia: SIAM, 2024. p. 1447-1464. ISBN 978-1-61197-791-2.
Type
Proceedings paper
Departments
Annotation
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.
Bears with Hats and Independence Polynomials
Authors
Blažej, V.; Dvořák, P.; Opler, M.
Year
2023
Published
Discrete Mathematics and Theoretical Computer Science. 2023, 25(2), ISSN 1365-8050.
Type
Article
Departments
Annotation
Consider the following hat guessing game. A bear sits on each vertex of a graph G, and a demon puts on each bear a hat colored by one of h colors. Each bear sees only the hat colors of his neighbors. Based on this information only, each bear has to guess g colors and he guesses correctly if his hat color is included in his guesses. The bears win if at least one bear guesses correctly for any hat arrangement. We introduce a new parameter - fractional hat chromatic number μ^, arising from the hat guessing game. The parameter μ^ is related to the hat chromatic number which has been studied before. We present a surprising connection between the hat guessing game and the independence polynomial of graphs. This connection allows us to compute the fractional hat chromatic number of chordal graphs in polynomial time, to bound fractional hat chromatic number by a function of maximum degree of G, and to compute the exact value of μ^ of cliques, paths, and cycles.
Bounds on Functionality and Symmetric Difference – Two Intriguing Graph Parameters
Authors
Dvořák, P.; Folwarczný, L.; Opler, M.; Pudlák, P.; Šámal, R.; Vu, T.A.
Year
2023
Published
Proceedings of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science. Cham: Springer, 2023. p. 305-318. Lecture Notes in Computer Science. vol. 14093. ISSN 0302-9743. ISBN 978-3-031-43379-5.
Type
Proceedings paper
Departments
Annotation
[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?
Improved Bounds for the Binary Paint Shop Problem
Authors
Hančl, J.; Kabela, A.; Opler, M.; Sosnovec, J.; Šámal, R.; Valtr, V.
Year
2023
Published
Computing and Combinatorics - 29th International Conference, COCOON 2023, Hawaii, HI, USA, December 15–17, 2023, Proceedings, Part II. Cham: Springer, 2023. p. 210-221. Lecture Notes in Computer Science. vol. 14423. ISSN 0302-9743. ISBN 978-3-031-49192-4.
Type
Proceedings paper
Departments
Annotation
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.