Tractability of Hard Digraph Cut Problems on Eulerian Instances: Treewidth Reduction and Reducing CMSO to Unbreakable Eulerian Instances

Esther Galby, Roohani Sharma, Bart van der Steenhoven

Eulerian digraphs retain the directional structure of general digraphs while exhibiting a symmetry of cuts reminiscent of undirected graphs. We show that this symmetry extends beyo…