Parameterized algorithms for the Steiner arborescence problem on a hypercube

期刊论文
发表日期：

2024年12月7日

查看全文

Sugyani Mahapatra,
Manikandan Narayanan,
N. S. Narayanaswamy

摘要

Motivated by a phylogeny reconstruction problem in evolutionary biology, we study the minimum Steiner arborescence problem on directed hypercubes (MSA-DH). Given m, representing the directed hypercube $\vec {Q}_m$ ${\vec{Q}}_{m}$ , and a set of terminals $R$ $R$ , the problem asks to find a Steiner arborescence that spans $R$ $R$ with minimum cost. As $m$ $m$ implicitly represents $\vec {Q}_{m}$ ${\vec{Q}}_{m}$ comprising $2^{m}$ $2^{m}$ vertices, the running time analyses of traditional Steiner tree algorithms on general graphs does not give a clear understanding of the actual complexity of this problem. We present algorithms that exploit the structure of the hypercube and run in FPT time. We explore the MSA-DH problem on three natural parameters— $|R|$ $| R |$ , and two above-guarantee parameters, number of Steiner nodes p and penalty q (defined as the extra cost above m incurred by the solution). For above-guarantee parameters, the parameterized MSA-DH problem take $p \ge 0$ $p \geq 0$ or $q\ge 0$ $q \geq 0$ as input, and outputs a Steiner arborescence with at most $|R|+ p - 1$ $| R | + p - 1$ or $m+ q$ $m + q$ edges respectively. We present the following results ( $\tilde{{\mathcal {O}}}$ $\tilde{O}$ hides the polynomial factors): 1.

An exact algorithm that runs in $\tilde{{\mathcal {O}}}(3^{|R|})$ $\tilde{O} (3^{| R |})$ time.

A randomized algorithm that runs in $\tilde{{\mathcal {O}}}(9^q)$ $\tilde{O} (9^{q})$ time with success probability $\ge 4^{-q}$ $\geq 4^{- q}$ .

An exact algorithm that runs in $\tilde{{\mathcal {O}}}(36^q)$ $\tilde{O} (36^{q})$ time.

A $(1+q)$ $(1 + q)$ -approximation algorithm that runs in $\tilde{{\mathcal {O}}}(1.25284^q)$ $\tilde{O} (1 . 25284^{q})$ time.

An ${\mathcal {O}}\left( p\ell _{\textrm{max}}\right) $ $O (p, ℓ_{max})$ -additive approximation algorithm that runs in $\tilde{{\mathcal {O}}}(\ell _{\textrm{max}}^{p+2})$ $\tilde{O} (ℓ_{max}^{p + 2})$ time, where $\ell _{\textrm{max}}$ $ℓ_{max}$ is the maximum distance of any terminal from the root.