Parameterized Algorithms for Computing MAD Trees
This work addresses the parameterized complexity of the MAD tree problem for researchers in algorithmic graph theory, offering incremental progress by establishing new tractability results for specific graph parameters.
The paper tackles the problem of finding a spanning tree with minimum average distance between vertex pairs (MAD tree), a classic NP-hard network design problem, by initiating a parameterized complexity analysis. It provides linear-time and polynomial-time algorithms for graphs with constant modular width and bounded treewidth, respectively, showing the problem is in FPT with respect to modular width and in XP with respect to treewidth, and also proves NP-hardness on split graphs.
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 it is in FPT when parameterized by vertex integrity or by an above-guarantee parameter. We complement these algorithms with NP-hardness on split graphs.