Ing. Jan Matyáš Křišťan, Ph.D.

Článek

10.1613/jair.1.19325

Katedra teoretické informatiky

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.

Stať ve sborníku

10.4230/LIPIcs.DISC.2025.23

Katedra teoretické informatiky

Payment channel networks (PCNs) are a promising technology that alleviates blockchain scalability by shifting the transaction load from the blockchain to the PCN. Nevertheless, the network topology has to be carefully designed to maximise the transaction throughput in PCNs. Additionally, users in PCNs also have to make optimal decisions on which transactions to forward and which to reject to prolong the lifetime of their channels. In this work, we consider an input sequence of transactions over parties. Each transaction consists of a transaction size, source, and target, and can be either accepted or rejected (entailing a cost). The goal is to design a PCN topology among the cooperating parties, along with the channel capacities, and then output a decision for each transaction in the sequence to minimise the cost of creating and augmenting channels, as well as the cost of rejecting transactions. Our main contribution is an approximation algorithm for the problem with parties. We further show that with some assumptions on the distribution of transactions, we can reduce the approximation ratio to . We complement our theoretical analysis with an empirical study of our assumptions and approach in the context of the Lightning Network.

Článek

10.1016/j.tcs.2025.115520

Katedra teoretické informatiky

This paper deals with local certification, specifically locally checkable proofs: given a graph property, the task is to certify whether a graph satisfies the property. The verification of this certification needs to be done locally without the knowledge of the whole graph. More precisely, a distributed algorithm, called a verifier, is executed on each vertex. The verifier observes the local neighborhood up to a constant distance and either accepts or rejects. We examine the trade-off between the visibility radius and the size of certificates. We describe a procedure that decreases the radius by encoding the neighborhood of each vertex into its certificate. We also provide a corresponding lower bound on the required certificate size increase, showing that such an approach is close to optimal.

Stať ve sborníku

10.1609/aaai.v39i22.34483

Katedra teoretické informatiky

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 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.) 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.

Stať ve sborníku

10.3233/FAIA250951

Katedra teoretické informatiky

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.

Stať ve sborníku

10.1007/978-981-96-2845-2_16

Katedra teoretické informatiky

In reconfiguration, we are given two solutions to a graph problem, such as VERTEX COVER or DOMINATING SET, with each solution represented by a placement of tokens on vertices of the graph. Our task is to reconfigure one into the other using small steps while ensuring the intermediate configurations of tokens are also valid solutions. The two commonly studied settings are TOKEN JUMPING and TOKEN SLIDING, which allows moving a single token to an arbitrary or an adjacent vertex, respectively. We introduce new rules that generalize TOKEN JUMPING, parameterized by the number of tokens allowed to move at once and by the maximum distance of each move. Our main contribution is identifying minimal rules that allow reconfiguring any possible given solution into any other for INDEPENDENT SET, VERTEX COVER, and DOMINATING SET. For each minimal rule, we also provide an efficient algorithm that finds a corresponding reconfiguration sequence. We further focus on the rule that allows each token to move to an adjacent vertex in a single step. This natural variant turns out to be the minimal rule that guarantees reconfigurability for VERTEX COVER. We determine the computational complexity of deciding whether a (shortest) reconfiguration sequence exists under this rule for the three studied problems. While reachability for VERTEX COVER is shown to be in P, finding a shortest sequence is shown to be NP-complete. For INDEPENDENT SET and DOMINATING SET, even reachability is shown to be PSPACE-complete.

Stať ve sborníku

10.1609/aaai.v39i22.34484

Katedra teoretické informatiky

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. 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 (e.g., processing areas) are connected to only few peripheral nodes.

Stať ve sborníku

10.4230/LIPIcs.DISC.2024.49

Katedra teoretické informatiky

This paper deals with local certification, specifically locally checkable proofs: given a graph property, the task is to certify whether a graph satisfies the property. The verification of this certification needs to be done locally without the knowledge of the whole graph. We examine the trade-off between the visibility radius and the size of certificates. We describe a procedure that decreases the radius by encoding the neighbourhood of each vertex into its certificate. We also provide a corresponding lower bound on the required certificate size increase, showing that such an approach is close to optimal.

Stať ve sborníku

10.1007/978-3-031-74580-5_14

Katedra teoretické informatiky

This paper deals with local certification, specifically locally checkable proofs: given a graph property, the task is to certify whether a graph satisfies the property. The verification of this certification needs to be done locally without the knowledge of the whole graph. More precisely, a distributed algorithm, called a verifier, is executed on each vertex. The verifier observes the local neighborhood up to a constant distance and either accepts or rejects. We examine the trade-off between the visibility radius and the size of certificates. We describe a procedure that decreases the radius by encoding the neighbourhood of each vertex into its certificate. We also provide a corresponding lower bound on the required certificate size increase, showing that such an approach is close to optimal.

Stať ve sborníku

10.1609/aaai.v38i16.29686

Katedra teoretické informatiky

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.

Stať ve sborníku

10.4230/LIPIcs.MFCS.2024.54

Katedra teoretické informatiky

Romeo and Juliet is a two player Rendezvous game played on graphs where one player controls two agents, Romeo (ℛ) and Juliet (𝒥) who aim to meet at a vertex against k adversaries, called dividers, controlled by the other player. The optimization in this game lies at deciding the minimum number of dividers sufficient to restrict ℛ and 𝒥 from meeting in a graph, called the dynamic separation number. We establish that Romeo and Juliet is EXPTIME-complete, settling a conjecture of Fomin, Golovach, and Thilikos [Inf. and Comp., 2023] positively. We also consider the game for directed graphs and establish that although the game is EXPTIME-complete for general directed graphs, it is PSPACE-complete and co-W[2]-hard for directed acyclic graphs.

Článek

10.1016/j.disopt.2022.100756

Katedra teoretické informatiky

Consider a vertex-weighted graph G with a source s and a target t. TRACKING PATHS requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from s to t is unique. In this work, we derive a factor 6-approximation algorithm for TRACKING PATHS in 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 related r-FAULT TOLERANT FEEDBACK VERTEX SET problem. There, for a fixed integer r and a given vertex-weighted graph G, the task is to find a minimum weight set of vertices intersecting every cycle of G in at least r+1 vertices. We give a factor O(r) approximation algorithm for r-FAULT TOLERANT FEEDBACK VERTEX SET if r is a constant.

Článek

10.1016/j.ipl.2022.106315

Katedra teoretické informatiky

Given an undirected graph G = (V , E), vertices s,t ∈ V , and an integer k, Tracking Shortest Paths requires deciding whether there exists a set of k vertices T ⊆ V such that for any two distinct shortest paths between s and t, say P1 and P2, we have T ∩ V (P1) != T ∩ V (P2). In this paper, we give the first polynomial size kernel for the problem. Specifically we show the existence of a kernel with O(k2) vertices and edges in general graphs and a kernel with O(k) vertices and edges in planar graphs for the Tracking Paths in DAG problem. This problem admits a polynomial parameter transformation to Tracking Shortest Paths, and this implies a kernel with O(k4) vertices and edges for Tracking Shortest Paths in general graphs and a kernel with O(k2) vertices and edges in planar graphs. Based on the above we also give a single exponential algorithm for Tracking Shortest Paths in planar graphs.

Stať ve sborníku

10.1007/978-3-031-43587-4_24

Katedra teoretické informatiky

In this paper, we present novel algorithms that efficiently compute a shortest reconfiguration sequence between two given dominating sets in trees and interval graphs under the Token Sliding model. In this problem, a graph is provided along with its two dominating sets, which can be imagined as tokens placed on vertices. The objective is to find a shortest sequence of dominating sets that transforms one set into the other, with each set in the sequence resulting from sliding a single token in the previous set. While identifying any sequence has been well studied, our work presents the first polynomial algorithms for this optimization variant in the context of dominating sets.

Stať ve sborníku

10.1007/978-3-030-92702-8_2

Katedra teoretické informatiky

Consider a vertex-weighted graph G with a source s and a target t. Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from s to t is unique. In this work, we derive a factor 66-approximation algorithm for Tracking Paths in 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 related r -Fault Tolerant Feedback Vertex Set problem. There, for a fixed integer r and a given vertex-weighted graph G, the task is to find a minimum weight set of vertices intersecting every cycle of G in at least r+1 vertices. We give a factor O(r^2) approximation algorithm for r -Fault Tolerant Feedback Vertex Set if r is a constant.

Stať ve sborníku

10.1007/978-3-030-30806-3_4

Katedra teoretické informatiky

Given a graph $G$, guards are placed on vertices of $G$. Then vertices are subject to an infinite sequence of attacks so that each attack must be defended by a guard moving from a neighboring vertex. The m-eternal domination number is the minimum number of guards such that the graph can be defended indefinitely. In this paper we study the m-eternal domination number of cactus graphs, that is, connected graphs where each edge lies in at most two cycles, and we consider three variants of the m-eternal domination number: first variant allows multiple guards to occupy a single vertex, second variant does not allow it, and in the third variant additional ``eviction'' attacks must be defended. We provide a new upper bound for the m-eternal domination number of cactus graphs, and for a subclass of cactus graphs called Christmas cactus graphs, where each vertex lies in at most two cycles, we prove that these three numbers are equal. Moreover, we present a linear-time algorithm for computing them.