20.500.12556/RUP-21902 Perfect phylogenies via the minimum uncovering branching problem efficiently solvable cases In this paper, we present new efficiently solvable cases of the Minimum Uncovering Branching problem, an optimization problem with applications in cancer genomics introduced by Hujdurovi´c, Husi´c, Milaniˇc, Rizzi, and Tomescu in 2018. The problem involves a family of finite sets, and the goal is to map each non-maximal set to exactly one set that contains it, minimizing the sum of uncovered elements across all sets in the family. Hujdurovi´c et al. formulated the problem in terms of branchings of the digraph formed by the proper set inclusion relation on the input sets and studied the problem complexity based on properties of the corresponding partially ordered set, in particular, with respect to its height and width, defined respectively as the maximum cardinality of a chain and an antichain. They showed that the problem is APX-complete for instances of bounded height and that a constant-factor approximation algorithm exists for instances of bounded width, but left the exact complexity for bounded-width instances open. In this paper, we answer this question by proving that the problem is solvable in polynomial time. We derive this result by examining the structural properties of optimal solutions and reducing the problem to computing maximum matchings in bipartite graphs and maximum weight antichains in partially ordered sets. We also introduce a new polynomially computable lower bound and identify another condition for polynomial-time solvability. perfect phylogeny branching partially ordered set antichain width popolna filogenija vejitev delno urejena množica antiveriga širina true false true Angleški jezik Slovenski jezik Članek v reviji 2025-10-13 08:14:45 2025-10-13 08:14:47 2025-11-05 03:03:02 0000-00-00 00:00:00 2025 0 0 str. 2043-2056 iss. 5 Vol. 22 Sep./Oct. 2025 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.179.1 2998-4165 10.1109/TCBBIO.2025.3580476 252020739 RAZ_Baghirova_Narmina_2025.pdf RAZ_Baghirova_Narmina_2025.pdf 1 89F43B43A1953AF28E8231F96CB5235A 3e086cdc61b4cd7996876acb0b1915372567f23eedc2863596898c73815db471 96a30824-a7fc-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=31815 https://ieeexplore.ieee.org/document/11037632 1 15240955-a7fc-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=31814 Inštitut Andrej Marušič 0 0 0