arXiv preprint ·
Tractability of Hard Digraph Cut Problems on Eulerian Instances: Treewidth Reduction and Reducing CMSO to Unbreakable Eulerian Instances
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Online Batching with Lookahead: Adversarial Limits and Stochastic Gains
Improved Combinatorial Auctions with and without Samples
QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Stochastic Weighted Caching with Per-Request Predictions
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.