TY - GEN

T1 - Exploiting Spanning Trees for Directed Acyclicity

AU - Харгелия, Сергей Олегович

AU - Сагунов, Данил Георгиевич

PY - 2026/8/25

Y1 - 2026/8/25

N2 - 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.

AB - 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.

KW - parameterized algorithms

KW - spanning tree

KW - above guarantee parameterizations

KW - perfect graph theorem

KW - feedback arc set

KW - maximum acyclic subgraph

KW - above guarantee parameterizations

KW - feedback arc set

KW - maximum acyclic subgraph

KW - parameterized algorithms

KW - perfect graph theorem

KW - spanning tree

UR - https://www.mendeley.com/catalogue/72de6033-1aa9-3ee1-a654-9a0cd88e85f0/

U2 - 10.4230/LIPIcs.ESA.2026.118

DO - 10.4230/LIPIcs.ESA.2026.118

M3 - Conference contribution

SN - 9783959774451

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

BT - 34th Annual European Symposium on Algorithms (ESA 2026)

T2 - 34th Annual European Symposium on Algorithms

Y2 - 31 August 2026 through 4 September 2026

ER -