Partial Fitch graphs: characterization, satisfiability and complexity

DOI10.1007/S10878-026-01452-1MaRDI QIDQ7346914zbMATH OpenFDO

Authors Marc Hellmuth, Annachiara Korchmaros, José Antonio Ramírez-Rafael, Bruno J. Schmidt, Peter F. Stadler, Sandhya Thekkumpadan Puthiyaveedu

Publication date 11 September 2026

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10878-026-01452-1

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites work

• A Linear Recognition Algorithm for Cographs
• Alternative characterizations of Fitch's xenology relation
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• Complement reducible graphs
• Fitch graph completion
• Fully dynamic recognition algorithm and certificate for directed cographs
• Linear-time modular decomposition of directed graphs
• Orientation of Fitch Graphs and Reconciliation-Free Inference of Horizontal Gene Transfer in Gene Trees
• Partial homology relations -- satisfiability in terms of di-cographs
• Reconstructing gene trees from Fitch's xenology relation
• Recovering symbolically dated, rooted trees from symbolic ultrametrics
• Reducibility among combinatorial problems
• Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs
• Topological sorting of large networks

This page was built for publication: Partial Fitch graphs: characterization, satisfiability and complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346914)