Computing $\vec\mathcalS$-DAGs and Parity Games
<|reference_start|>Computing $\vec\mathcalS$-DAGs and Parity Games: Treewidth on undirected graphs is known to have many algorithmic applications. When considering directed width-measures there are much less results on their deployment for algorithmic results. In 2022 the first author, Rabinovich and Wiederrecht introduced a new directed width measure, $\vec{\mathcal{S}}$-DAG-width, using directed separations and obtained a structural duality for it. In 2012 Berwanger~et~al.~solved Parity Games in polynomial time on digraphs of bounded DAG-width. With generalising this result to digraphs of bounded $\vec{\mathcal{S}}$-DAG-width and also providing an algorithm to compute the $\vec{\mathcal{S}}$-DAG-width of a given digraphs we give first algorithmical results for this new parameter.<|reference_end|>
@article{hatzel2024computing,
    title={Computing $\vec{\mathcal{S}}$-DAGs and Parity Games},
    author={Meike Hatzel, Johannes Schr"oder},
    journal={arXiv preprint arXiv:2405.05571},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.05571},
    primaryClass={math.CO cs.DM}
}