DKDušan Knop

Dušan Knop

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

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:


Latest Publications

  • Open Access

    Pathfinding in Self-Deleting Graphs

    by Michal Dvořák, Dusan Knop, Michal Opler, Jan Pokorný, OndřEj Suchý, Krisztina Szilágyi

    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

    Parameterized complexity of scheduling problems in robotic process automation

    by Michal Dvořák, Antonín Novák, PřEmysl Šůcha, Dušan Knop, Claire Hanen

  • Controlling the Spread of Two Secrets in Diverse Social Networks

    by Václav Blažej, Dušan Knop, Šimon Schierreich

  • Open Access

    Balancing the spread of two opinions in sparse social networks

    by Dušan Knop, Šimon Schierreich, OndřEj Suchý

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

  • Adapting stable matchings to evolving preferences

    by Robert Bredereck, Jiehua Chen, Dušan Knop, Junjie Luo, Rolf Niedermeier


  • Open Access

    Participatory Budgeting Project Strength via Candidate Control

    by Piotr Faliszewski, Łukasz Janeczko, Dušan Knop, Jan Pokorný, Šimon Schierreich, Mateusz Słuszniak, Krzysztof Sornat

    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

    by Michal Dvořák, Antonín Novák, PřEmysl Šůcha, Dušan Knop, Claire Hanen

    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

    by Argyris Deligkas, Eduard Eiben, Tiger-Lily Goldsmith, Dušan Knop, Šimon Schierreich

    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

    Participatory Budgeting Project Strength via Candidate Control

    by Piotr Faliszewski, Łukasz Janeczko, Dušan Knop, Jan Pokorný, Šimon Schierreich, Mateusz Słuszniak, Krzysztof Sornat

    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.