2021/10/06 by Sugyani Mahapatra, Mahapatra, Sugyani, Manikandan Narayanan +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #Advanced biosensing and bioanalysis techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Chromatin Dynamics
paper · pdf · doi:10.48550/arxiv.2110.02830
openalex publication_date 2021/10/06 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
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 Qm, and a set of terminals R, the problem asks to find a Steiner arborescence that spans R with minimum cost. As m implicitly represents Qm comprising 2m 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 time polynomial in |R| and m. We explore the MSA-DH problem on three natural parameters - R, and two above-guarantee parameters, number of Steiner nodes p and penalty q. For above-guarantee parameters, the parameterized MSA-DH problem takes p ≥ 0 or q≥ 0 as input, and outputs a Steiner arborescence with at most |R| + p - 1 or m + q edges respectively. We present the following results (O hides the polynomial factors): 1. An exact algorithm that runs in O(3|R|) time. 2. A randomized algorithm that runs in O(9q) time with success probability ≥ 4-q. 3. An exact algorithm that runs in O(36q) time. 4. A (1+q)-approximation algorithm that runs in O(1.25284q) time. 5. An O(pℓmax )-additive approximation algorithm that runs in O(ℓmaxp+2) time, where ℓmax is the maximum distance of any terminal from the root.