MOMichal Opler

Michal Opler

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Michal Opler has a total of 17 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Solving Multiagent Path Finding on Highly Centralized Networks

    by Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan, Nikolaos Melissinos, Michal Opler, Tung Anh Vu

    The Mutliagent Path Finding (MAPF) problem consists of identifying the trajectories that a set of agents should follow inside a given network in order to reach their desired destinations as soon as possible, but without colliding with each other. We aim to minimize the maximum time any agent takes to reach their goal, ensuring optimal path length. In this work, we complement a recent thread of results that aim to systematically study the algorithmic behavior of this problem, through the parameterized complexity point of view. First, we show that MAPF is NP-hard when the given network has a star-like topology (bounded vertex cover number) or is a tree with 11 leaves. Both of these results fill important gaps in our understanding of the tractability of this problem that were left untreated in the recent work of Fioravantes et al., Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology, presented in AAAI'24. Nevertheless, our main contribution is an exact algorithm that scales well as the input grows (FPT) when the topology of the given network is highly centralized (bounded distance to clique). This parameter is significant as it mirrors real-world networks. In such environments, a bunch of central hubs or nodes (e.g., processing areas) are connected to peripheral nodes.


  • Open Access

    Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures

    by Foivos Fioravantes, Dušan Knop, Jan Matyáš Křišťan, Nikolaos Melissinos, Michal Opler

    Consider the scenario where multiple agents have to move in an optimal way through a network, each one towards their ending position, and while avoiding collisions. By optimal, we mean as fast as possible, which is evaluated by a measure known as the makespan of the proposed solution. This is the setting studied in the Multiagent Path Finding problem. In this work we additionally provide the agents with a way to communicate with each other. Due to size constraints, it is reasonable to assume that the range of the communication of each agent will be limited. What should be the trajectories of the agents to, additionally, maintain a backbone of communication? In this work we study this Multiagent Path Finding with Communication Constraint problem under the parameterized complexity framework. Our main contribution is three exact algorithms that are efficient when considering particular structures for the input network. We provide such algorithms for the case when the communication range and the number of agents (the makespan resp.) is provided in the input and the network has a tree topology, or bounded maximum degree (has a tree-like topology, i.e., bounded treewidth resp.). We complement these results by showing that it is highly unlikely to construct efficient algorithms when considering the number of agents as part of the input, even if the makespan is 3 and the communication range is 1.


  • Open Access

    Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology

    by Foivos Fioravantes, Dušan Knop, Jan Matyáš Křištan, Nikolaos Melissinos, Michal Opler

    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.


  • Improved Bounds for the Binary Paint Shop Problem

    by J. Hančl, A. Kabela, M. Opler, J. Sosnovec, R. Šámal, P. Valtr


  • Bounds on Functionality and Symmetric Difference – Two Intriguing Graph Parameters

    by Pavel Dvořák, Lukáš Folwarczný, Michal Opler, Pavel Pudlák, Robert Šámal, Tung Anh Vu