3 papers
cs.DM2025
On the hardness of recognizing graphs of small mim-width and its variants
Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye
The mim-width of a graph is a powerful structural parameter that, when bounded by a constant, allows several hard problems to be polynomial-time solvable - with a recent meta-theor…
math.CO2025
Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete
Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye
Leaf powers and pairwise compatibility graphs were introduced over twenty years ago as simplified graph models for phylogenetic trees. Despite significant research, several propert…
cs.DM2025
Galled Perfect Transfer Networks
Alitzel López Sánchez, Manuel Lafond
Predicting horizontal gene transfers often requires comparative sequence data, but recent work has shown that character-based approaches could also be useful for this task. Notably…