Dušan Knop
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Dušan Knop has a total of 105 co-authors. Here are the top co-authors by number of shared publications:
- Robert Bredereck
Institut für Informatik TU Clausthal Clausthal-Zellerfeld Germany
11 shared publications - Martin Koutecký
Computer Science Institute, Charles University, Prague, Czech Republic
10 shared publications - Ondřej Suchý
Czech Technical University in Prague
9 shared publications - Tomáš Masařík
University of Warsaw, Warsaw, Poland
9 shared publications - Robert Ganian
TU Wien Vienna Austria
8 shared publications - Šimon Schierreich
AGH University of Krakow
8 shared publications
Latest Publications
- Open Access
- 15 October 2026
- Published by Elsevier in SSRN Electronic Journal
Pathfinding in Self-Deleting Graphs
In this paper, we study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices.In particular, we study \emph{self-deleting graphs}, introduced by Carmesin et al. (JoCS 2023)~\cite{carmesin2023hamiltonian}, which consist of a graph $G=(V, E)$ and a function $f\colon V\rightarrow 2^E$, where $f(v)$ is the set of edges that will be deleted after visiting the vertex $v$.In the \textsc{(Shortest)} \SDpath problem we are given a self-deleting graph and its vertices $s$ and $t$, and we are asked to find a path from $s$ to $t$ (of at most a given length), such that it does not traverse an edge in $f(v)$ after visiting $v$ for any vertex $v$.We prove that \SDpath is \NP-hard even if the given graph is outerplanar, bipartite, has maximum degree $3$, bandwidth $2$ and satisfies $|f(v)|\leq 1$ for each vertex $v$.We show that \SSDpath is \W{1}-complete parameterized by the length of the sought path and that both problems are \W{1}-complete parameterized by the vertex cover number, feedback vertex set number and treedepth.In order to obtain algorithmic results, we parameterize the problem by $\mu=\max_v |f(v)|$ -- the maximum size of $f(v)$ and the length of the sought path. By a nontrivial application of the color coding technique, we obtain \FPT algorithm with respect to this parameter combination. This result allows us to obtain several \FPT algorithms parameterized by a combination of $\mu$ and a structural parameter, such as shrub-depth or modular-width.Next, we show that, unless $\NP\subseteq \coNP/_{\poly}$, \SSDpath does not admit a polynomial kernel even parameterized by the combination of vertex cover number, length of sought path, and $\mu$ already on 2-outerplanar graphs.Lastly, we study the parameterized complexity of \SSDpath when the size of each $f(v)$ is at most logarithmic in the number of vertices of the underlying graph. While the problem becomes \FPT parameterized by the length of the sought path, it becomes {\sf WK}[1]-hard under the same parameterization (hence it does not admit a polynomial kernel unless $\NP\subseteq \coNP/_{\poly}$). From the structural side, the problem becomes \FPT parameterized by treedepth, but it becomes \W{1}-hard parameterized by neighborhood diversity and cluster vertex deletion number.We provide tight lower bounds based on the Exponential Time Hypothesis (ETH) for most of our algorithmic results.- 15 October 2026
- Published by Elsevier in SSRN Electronic Journal
Open AccessPathfinding in Self-Deleting Graphs
In this paper, we study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices.In particular, we study \emph{self-deleting graphs}, introduced by Carmesin et al. (JoCS 2023)~\cite{carmesin2023hamiltonian}, which consist of a graph $G=(V, E)$ and a function $f\colon V\rightarrow 2^E$, where $f(v)$ is the set of edges that will be deleted after visiting the vertex $v$.In the \textsc{(Shortest)} \SDpath problem we are given a self-deleting graph and its vertices $s$ and $t$, and we are asked to find a path from $s$ to $t$ (of at most a given length), such that it does not traverse an edge in $f(v)$ after visiting $v$ for any vertex $v$.We prove that \SDpath is \NP-hard even if the given graph is outerplanar, bipartite, has maximum degree $3$, bandwidth $2$ and satisfies $|f(v)|\leq 1$ for each vertex $v$.We show that \SSDpath is \W{1}-complete parameterized by the length of the sought path and that both problems are \W{1}-complete parameterized by the vertex cover number, feedback vertex set number and treedepth.In order to obtain algorithmic results, we parameterize the problem by $\mu=\max_v |f(v)|$ -- the maximum size of $f(v)$ and the length of the sought path. By a nontrivial application of the color coding technique, we obtain \FPT algorithm with respect to this parameter combination. This result allows us to obtain several \FPT algorithms parameterized by a combination of $\mu$ and a structural parameter, such as shrub-depth or modular-width.Next, we show that, unless $\NP\subseteq \coNP/_{\poly}$, \SSDpath does not admit a polynomial kernel even parameterized by the combination of vertex cover number, length of sought path, and $\mu$ already on 2-outerplanar graphs.Lastly, we study the parameterized complexity of \SSDpath when the size of each $f(v)$ is at most logarithmic in the number of vertices of the underlying graph. While the problem becomes \FPT parameterized by the length of the sought path, it becomes {\sf WK}[1]-hard under the same parameterization (hence it does not admit a polynomial kernel unless $\NP\subseteq \coNP/_{\poly}$). From the structural side, the problem becomes \FPT parameterized by treedepth, but it becomes \W{1}-hard parameterized by neighborhood diversity and cluster vertex deletion number.We provide tight lower bounds based on the Exponential Time Hypothesis (ETH) for most of our algorithmic results. - Open Access
- 7 September 2026
- Published by Elsevier in European Journal of Operational Research
Parameterized complexity of scheduling problems in robotic process automation
- 7 September 2026
- Published by Elsevier in European Journal of Operational Research
Open AccessParameterized complexity of scheduling problems in robotic process automation
- 2 July 2026
- Published by Springer Nature
- p. 161-178
Controlling the Spread of Two Secrets in Diverse Social Networks
- 2 July 2026
- Published by Springer Nature
- p. 161-178
Controlling the Spread of Two Secrets in Diverse Social Networks
- Open Access
- 22 May 2026
- Published by Elsevier in Artificial Intelligence
- Vol. 357
Balancing the spread of two opinions in sparse social networks
- 22 May 2026
- Published by Elsevier in Artificial Intelligence
- Vol. 357
Open AccessBalancing the spread of two opinions in sparse social networks
- Open Access
- 31 March 2026
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 85
Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures
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.
- 31 March 2026
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 85
Open AccessExact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures
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.
- 20 February 2026
- Published by Elsevier in Games and Economic Behavior
- Vol. 157, 322-350
Adapting stable matchings to evolving preferences
- 20 February 2026
- Published by Elsevier in Games and Economic Behavior
- Vol. 157, 322-350
Adapting stable matchings to evolving preferences
- Open Access
Participatory Budgeting Project Strength via Candidate Control
We study the complexity of candidate control in participatory budgeting elections. The goal of constructive candidate control is to ensure that a given candidate wins by either adding or deleting candidates from the election (in the destructive setting, the goal is to prevent a given candidate from winning). We show that such control problems are NP-hard to solve for many participatory budgeting voting rules, including Phragmén and Method of Equal Shares, but there are natural cases with polynomial-time algorithms (e.g., for the GreedyAV rule and projects with costs encoded in unary). We also argue that control by deleting candidates is a useful tool for assessing the performance (or, strength) of initially losing projects, and we support this view with experiments.
Open AccessParticipatory Budgeting Project Strength via Candidate Control
We study the complexity of candidate control in participatory budgeting elections. The goal of constructive candidate control is to ensure that a given candidate wins by either adding or deleting candidates from the election (in the destructive setting, the goal is to prevent a given candidate from winning). We show that such control problems are NP-hard to solve for many participatory budgeting voting rules, including Phragmén and Method of Equal Shares, but there are natural cases with polynomial-time algorithms (e.g., for the GreedyAV rule and projects with costs encoded in unary). We also argue that control by deleting candidates is a useful tool for assessing the performance (or, strength) of initially losing projects, and we support this view with experiments.
- Open Access
Parameterized Complexity of Scheduling Problems in Robotic Process Automation
This paper studies the growing domain of Robotic Process Automation (RPA) problems. Motivated by scheduling problems arising in RPA, we study the parameterized complexity of the single-machine problem $1|\text{prec},r_j,d_j|*$. We focus on parameters naturally linked to RPA systems, including chain-like precedences, the number of distinct processing times, and the structure of the time windows. We show that the problem is W[2]-hard parameterized by the number of chains, even with only two prescribed processing times and two distinct time-window lengths. This hardness remains even for distinct processing times and time windows under prec-consistent time windows. On the positive side, we obtain polynomial-time algorithm when all jobs share a single time-window length and FPT when the processing times, release times and deadlines are chain-uniform. We also show that the problem lies in XP when parameterized by the width of the precedence relation.Open AccessParameterized Complexity of Scheduling Problems in Robotic Process Automation
This paper studies the growing domain of Robotic Process Automation (RPA) problems. Motivated by scheduling problems arising in RPA, we study the parameterized complexity of the single-machine problem $1|\text{prec},r_j,d_j|*$. We focus on parameters naturally linked to RPA systems, including chain-like precedences, the number of distinct processing times, and the structure of the time windows. We show that the problem is W[2]-hard parameterized by the number of chains, even with only two prescribed processing times and two distinct time-window lengths. This hardness remains even for distinct processing times and time windows under prec-consistent time windows. On the positive side, we obtain polynomial-time algorithm when all jobs share a single time-window length and FPT when the processing times, release times and deadlines are chain-uniform. We also show that the problem lies in XP when parameterized by the width of the precedence relation. - Open Access
Dividing Indivisible Items for the Benefit of All: It is Hard to Be Fair Without Social Awareness
In standard fair division models, we assume that all agents are selfish. However, in many scenarios, division of resources has a direct impact on the whole group or even society. Therefore, we study fair allocations of indivisible items that, at the same time, maximize social impact. In this model, each agent is associated with two additive functions that define their value and social impact for each item. The goal is to allocate items so that the social impact is maximized while maintaining some fairness criterion. We reveal that the complexity of the problem heavily depends on whether the agents are socially aware, i.e., they take into consideration the social impact functions. For socially unaware agents, we prove that the problem is NP-hard for a variety of fairness notions, and that it is tractable only for very restricted cases, e.g., if, for every agent, the valuation equals social impact and it is binary. On the other hand, social awareness allows for fair allocations that maximize social impact, and such allocations can be computed in polynomial time. Interestingly, the problem becomes again intractable as soon as the definition of social awareness is relaxed.
Open AccessDividing Indivisible Items for the Benefit of All: It is Hard to Be Fair Without Social Awareness
In standard fair division models, we assume that all agents are selfish. However, in many scenarios, division of resources has a direct impact on the whole group or even society. Therefore, we study fair allocations of indivisible items that, at the same time, maximize social impact. In this model, each agent is associated with two additive functions that define their value and social impact for each item. The goal is to allocate items so that the social impact is maximized while maintaining some fairness criterion. We reveal that the complexity of the problem heavily depends on whether the agents are socially aware, i.e., they take into consideration the social impact functions. For socially unaware agents, we prove that the problem is NP-hard for a variety of fairness notions, and that it is tractable only for very restricted cases, e.g., if, for every agent, the valuation equals social impact and it is binary. On the other hand, social awareness allows for fair allocations that maximize social impact, and such allocations can be computed in polynomial time. Interestingly, the problem becomes again intractable as soon as the definition of social awareness is relaxed.
- Open Access
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 5, 3821-3829
Participatory Budgeting Project Strength via Candidate Control
We study the complexity of candidate control in participatory budgeting elections. The goal of constructive candidate control is to ensure that a given candidate wins by either adding or deleting candidates from the election (in the destructive setting, the goal is to prevent a given candidate from winning). We show that such control problems are NP-hard to solve for many participatory budgeting voting rules, including Phragmén and Equal-Shares, but there are natural cases with polynomial-time algorithms. We also argue that control by deleting candidates is a useful tool for assessing the performance (or, strength) of initially losing projects, and we support this view with experiments on real-life PB instances.
- 1 September 2025
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 5, 3821-3829
Open AccessParticipatory Budgeting Project Strength via Candidate Control
We study the complexity of candidate control in participatory budgeting elections. The goal of constructive candidate control is to ensure that a given candidate wins by either adding or deleting candidates from the election (in the destructive setting, the goal is to prevent a given candidate from winning). We show that such control problems are NP-hard to solve for many participatory budgeting voting rules, including Phragmén and Equal-Shares, but there are natural cases with polynomial-time algorithms. We also argue that control by deleting candidates is a useful tool for assessing the performance (or, strength) of initially losing projects, and we support this view with experiments on real-life PB instances.