arXiv:2603.29381 · v2

Parameterized Algorithms for Computing MAD Trees

首次提交 2026-03-31 15:50

版本更新 2026-10-29 18:11

雷达观测 2026-10-30 13:28

摘要

We consider the well-studied problem of finding a spanning tree with minimum average distance between vertex pairs (called a MAD tree). This is a classic network design problem which is known to be NP-hard. While approximation algorithms and polynomial-time algorithms for some graph classes are known, the parameterized complexity of the problem has not been investigated so far. We start a parameterized complexity analysis with the goal of determining the border of algorithmic tractability for the MAD tree problem. To this end, we provide a linear-time algorithm for graphs of constant modular width and a polynomial-time algorithm for graphs of bounded treewidth; the degree of the polynomial depends on the treewidth. That is, the problem is in FPT with respect to modular width and in XP with respect to treewidth. Moreover, we show that it is in FPT when parameterized by vertex integrity, by maximum leaf number, or by an above-guarantee parameter. We complement these algorithms with NP-hardness on split graphs.

作者备注：A conference version of this work was published at IWOCA 2026