Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem

Mohammad T. Hajiaghayi, Mahdi JafariRaviz, Alireza Kaviani +1

We give the first polynomial-time algorithm, after half a century, for the celebrated Győri-Lovász theorem, which resolved a conjecture of Frank (1975). The theorem, one of the sim…