Consider the scenario where multiple agents have to move in an optimal way through a network, each one towards their ending position 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 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 the Multiagent Path Finding with Communication Constraints 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.) are 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.

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.

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.

We study the heterogeneous facility location game model of n selfish agents on a line, where each agent’s reachable range is a closed subinterval of the line. From two possible facilities, f1 and f2, exactly one is chosen to be built on some point of the line, and the agents have their own preferences p1, p2∈[0,1], p1+p2=1, over these two facilities. The utility of the agent is pi if the placement of the chosen facility fi is inside her reachable range, and zero otherwise. The task is to design mechanisms which get the input from the agents and select the type and placement point of the facility to be built, such that it maximizes the social welfare (defined as the total utility of all agents) while ensuring truthfulness, i.e., incentivizing agents to report their preferences (both facility type and placement) honestly as a dominant strategy. We analyze various scenarios with different setting of privacy of agents’ positional and preference information. When the information is private to the agent, they have the option to misreport it, and hence, we will distinguish between reported information and public information. Initially, we consider the case where all facility preferences are 0 or 1 and we design an optimal mechanism for this case. We then study the case with fractional facility preferences. For the case of public preferences and reported positions, we obtain a mechanism yielding a 3-approximation of the optimum social welfare, and we prove that no deterministic mechanism can achieve approximation ratio better than 4/3. Next, we study the case with public positions and reported preferences. In this setting we design a randomized 2-approximation, obtain lower bounds 3 and 3/2 for the approximation factor of deterministic and randomized strategyproof mechanisms, respectively, and show that a dictator-based approach is a 16/7-approximation mechanism, where the 16/7 factor is tight. Finally, we extend our results to the case of m facilities.

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.

Abstract Consider a vertex-weighted graphGwith a sourcesand a targett.Tracking Pathsrequires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path fromstotis unique. In this work, we derive a factor 66-approximation algorithm forTracking Pathsin weighted graphs and a factor 4-approximation algorithm if the input is unweighted. This is the first constant factor approximation for this problem. While doing so, we also study approximation of the closely relatedr-Fault Tolerant Feedback Vertex Setproblem. There, for a fixed integer rand a given vertex-weighted graphG, the task is to find a minimum weight set of vertices intersecting every cycle of Gin at least $$r+1$$ r+1 vertices. We give a factor $$\mathcal {O}(r^2)$$ O(r2) approximation algorithm forr-Fault Tolerant Feedback Vertex Setifris a constant.