Maximizing edge-ratio is NP-complete - Noble, SD; Hansen, Pierre; Mladenović, Nenad (Discrete Applied Mathematics, 2011)