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.MA2024
Eliminating Majority Illusion is Easy
Jack Dippel, Max Dupré la Tour, April Niu +2
Majority Illusion is a phenomenon in social networks wherein the decision by the majority of the network is not the same as one's personal social circle's majority, leading to an i…