3 papers
cs.DS2025
Pathfinding in Self-Deleting Graphs
Michal Dvořák, Dušan Knop, Michal Opler +3
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 st…
cs.CC2023
Treewidth is NP-Complete on Cubic Graphs (and related results)
Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke +6
In this paper, we give a very simple proof that Treewidth is NP-complete; this proof also shows NP-completeness on the class of co-bipartite graphs. We then improve the result by B…
cs.DS2021
Balancing the Spread of Two Opinions in Sparse Social Networks
Dušan Knop, Šimon Schierreich, Ondřej Suchý
Inspired by the famous Target Set Selection problem, we propose a new discrete model to simultaneously spread two opinions within a social network and perform an initial study of i…