Eulerian digraph cut problems become easier with new structure methods
Tractability of Hard Digraph Cut Problems on Eulerian Instances: Treewidth Reduction and Reducing CMSO to Unbreakable Eulerian Instances
Data Structures and Algorithms
Summary
Finding ways to cut or separate parts of directed networks can be very hard. The authors studied a special kind of network called an Eulerian digraph that has balanced connections. They discovered that these networks have special symmetrical properties that let them use powerful tools originally made for simpler, undirected networks. This means some difficult network-cutting problems can now be solved efficiently on these Eulerian digraphs, even though they remain hard on general networks.
What this means in practice
- •For network security engineers: Detect and efficiently isolate problematic connections in traffic flow models that form Eulerian digraphs using the new fixed-parameter algorithms.
- •For telecommunication network planners: Design routing plans that leverage Eulerian properties to quickly find minimal critical link removals for maintenance or upgrades.
A theory result. No direct application yet.
Authors
Esther Galby, Roohani Sharma, Bart van der Steenhoven
Abstract
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 beyond individual cuts to two fundamental techniques in parameterized algorithms for undirected cut problems: treewidth reduction and recursive understanding and randomized contractions. Both of these techniques have proved useful for dealing with undirected graph cut problems as each of them reduces the problem at hand on general undirected instances to ones that have bounded treewidth or that are highly connected, respectively. In this work we prove an edge-cut analogue of the treewidth-reduction theorem of Marx, O'Sullivan, and Razgon [ACM TALG 2013], and an Eulerian analogue of the reduction of CMSO model checking to unbreakable instances due to Lokshtanov, Ramanujan, Saurabh, and Zehavi [ICALP 2018]. Both these results allow us to reduce several problems on general Eulerian digraphs to Eulerian digraphs whose underlying undirected graph has bounded treewidth, or to Eulerian instances that are highly connected, thus bringing to Eulerian digraphs two fundamental tools from the undirected parameterized cut toolkit for which no counterparts are known on arbitrary digraphs. Beyond their structural significance, these results have substantial algorithmic consequences: they yield FPT algorithms for several directed cut problems that are W[1]-hard in general. We show that Directed Multicut and Directed Edge Odd Cycle Transversal are FPT on Eulerian digraphs when parameterized by the solution size and the number of terminal pairs, and just the solution size, respectively. This is in sharp contrast to general digraphs, where the first problem is W[1]-hard even for 4 terminal pairs, and the second is W[1]-hard in general. We also obtain FPT algorithms for Directed Edge Multiway Cut-Uncut and Directed Steiner Cut.