2026-09-21T04:27:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27254 2026-09-05T20:16:34Z ddc:004 open_access

Exploiting Spanning Trees for Directed Acyclicity Khargeliia, Sergei Sagunov, Danil parameterized algorithms spanning tree above guarantee parameterizations perfect graph theorem feedback arc set maximum acyclic subgraph We study the weighted case of the Maximum Acyclic Subgraph (MAS) problem, where each edge of a given directed graph has a positive weight assigned, and the task is to find a maximum-weight acyclic edge set. The famous and well-studied random ordering lower bound guarantees the existence of an acyclic set that gives at least the half of the total edge weight. The maximum spanning tree (MaxST) guarantee, which is the weight of a maximum-weight acyclic subgraph of the underlying undirected graph of G, is another natural lower bound for the weight of an acyclic subgraph. A solution of this weight dominates the random ordering solution on instances where MaxST spans the most of the total edge weight. Our main contribution are two parameterized algorithms that find acyclic subgraphs of total weight larger than the weight of the MaxST of G. Both our algorithms find a solution of total weight at least MaxST(G)+k, for a given integer k ≥ 0, or report that it does not exist, and - First of our algorithms runs in time 2^{k^𝒪(1)}⋅|ℐ|^𝒪(1) and works when all weights are integers; - Our second algorithm handles rational weights not less than 1, and its running time is upper-bounded by n^{k^𝒪(1)}⋅|ℐ|^𝒪(1). This positive result is rather surprising since solving MAS above the random ordering lower bound is NP-hard in the same rational weights scenario, when k = 1. Our findings unravel intricate connections between structure of MaxSTs and directed cycles, use perfect graph theorem to tackle rational weights, and raise graph-theoretic questions that are interesting on their own. Of another importance, this is one of the few examples of positive "above guarantee" results for a weighted problem on directed graphs, especially for rational weights. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sergei Khargeliia and Danil Sagunov 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.118 urn:nbn:de:0030-drops-272540 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.118 eng https://creativecommons.org/licenses/by/4.0/legalcode