Finding subdigraphs in digraphs of bounded directed treewidth

August 19, 2025 Β· Declared Dead Β· πŸ› Latin-American Algorithms, Graphs and Optimization Symposium

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Raul Lopes, Ignasi Sau arXiv ID 2508.13830 Category cs.DS: Data Structures & Algorithms Cross-listed math.CO Citations 0 Venue Latin-American Algorithms, Graphs and Optimization Symposium Last Checked 4 months ago
Abstract
It is well known that directed treewidth does not enjoy the nice algorithmic properties of its undirected counterpart. There exist, however, some positive results that, essentially, present XP algorithms for the problem of finding, in a given digraph $D$, a subdigraph isomorphic to a digraph $H$ that can be formed by the union of $k$ directed paths (with some extra properties), parameterized by $k$ and the directed treewidth of $D$. Our motivation is to tackle the following question: Are there subdigraphs, other than the directed paths, that can be found efficiently in digraphs of bounded directed treewidth? In a nutshell, the main message of this article is that, other than the directed paths, the only digraphs that seem to behave well with respect to directed treewidth are the stars. For this, we present a number of positive and negative results, generalizing several results in the literature, as well as some directions for further research.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted