3 papers
cs.CC2026
A Parameterized-Complexity Framework for Finding Local Optima
Robert Ganian, Hung P. Hoang, Christian Komusiewicz +1
Local search is a fundamental optimization technique that is both widely used in practice and deeply studied in theory, yet its computational complexity remains poorly understood.…
cs.DS2025
Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
Narek Bojikian, Alexander Firbas, Robert Ganian +2
We investigate the computation of minimum-cost spanning trees satisfying prescribed vertex degree constraints: Given a graph and a constraint function , we ask for a (minimu…
math.CO2025
Minimum maximal matchings in permutahedra
Sofia Brenner, Jiří Fink, Hung. P. Hoang +2
We prove that the minimal size of a maximal matching in the permutahedron is asymptotically . On the one hand, we obtain a lower bound $M(π_n) \ge n! (n-1) / (…