Perfect phylogenies via the Minimum Uncovering Branching Problem: Efficiently Solvable Cases.

Area of Science:

• Computational biology
• Optimization theory
• Genomics

Background:

• The Minimum Uncovering Branching problem, introduced in 2018, is crucial for cancer genomics.
• It involves selecting covering sets to minimize uncovered elements, with complexity studied concerning set properties like height and width.
• Previous work showed APX-completeness for bounded height and approximation for bounded width, leaving exact complexity for bounded width open.

Purpose of the Study:

• To determine the exact computational complexity of the Minimum Uncovering Branching problem for instances with bounded width.
• To develop efficient algorithms for solving this problem in specific, practically relevant cases.

Main Methods:

• Analysis of the structural properties of optimal solutions.
• Reduction of the problem to computing maximum matchings in bipartite graphs.
• Reduction to computing maximum weight antichains in partially ordered sets.
• Development of a new polynomially computable lower bound.

Main Results:

• The Minimum Uncovering Branching problem is proven to be solvable in polynomial time for instances of bounded width.
• New conditions for polynomial-time solvability are identified.
• A novel lower bound for the problem is introduced.

Conclusions:

• The exact complexity for bounded-width instances of the Minimum Uncovering Branching problem is resolved, establishing polynomial-time solvability.
• The findings provide efficient computational tools for applications in cancer genomics.
• This research advances the understanding of optimization problems on partially ordered sets.