2026-07-26T16:19:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25126 2026-02-09T08:06:31Z ddc:004 open_access

Finding Small Dijoins in Transitive Closure Time Nalam, Chaitanya Saranurak, Thatchaphol Graph algorithms Dijoin Submodular flow We present a faster algorithm for finding a minimum dijoin, a smallest set of edges whose contraction makes a directed graph strongly connected. This problem has been studied since the 1960s [Seshu and Reed 1961] and is dual to finding a maximum sized family of disjoint dicuts [Lucchesi and Younger 1978]. Given a directed graph G with n vertices and m edges whose minimum dijoin has size d, our algorithm outputs both a minimum dijoin and a maximum sized family of disjoint dicuts in O(TC⋅ d) time, where TC = min(mn,n^ω) is the time to compute the transitive closure. This improves upon the state of the art of [Gabow 1993], which requires O(TC ⋅ min(m^{1/2},n^{2/3})) time when d = o(min(m^{1/2},n^{2/3})). Our result extends to finding a minimum weighted dijoin. We achieve this by observing that Frank’s algorithm [Frank 1981] can be sped up when warm-started with a 2-approximation solution, which we observed can be computed in near-linear time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chaitanya Nalam and Thatchaphol Saranurak 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.46 urn:nbn:de:0030-drops-251265 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.46 eng https://creativecommons.org/licenses/by/4.0/legalcode