Partial Fitch Graphs: Characterization, Satisfiability and Complexity
Marc Hellmuth, Annachiara Korchmaros, José Antonio Ramírez-Rafael, Bruno Schmidt, Peter Florian Stadler, Sandhya Thekkumpadan Puthiyaveedu
The paper characterizes partial Fitch graphs, shows their satisfiability, and proves NP-hardness of recovering full Fitch graphs from partial data.
Journal of Combinatorial Optimization · Aug 1, 2026Peer-reviewedBioinformatics