Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.13830 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915451445968896 |
|---|---|
| author | Lopes, Raul Sau, Ignasi |
| author_facet | Lopes, Raul Sau, Ignasi |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_13830 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Finding subdigraphs in digraphs of bounded directed treewidth Lopes, Raul Sau, Ignasi Data Structures and Algorithms Combinatorics 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. |
| title | Finding subdigraphs in digraphs of bounded directed treewidth |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2508.13830 |