Complexity and algorithms for constant diameter augmentation problems

We study the following problem: for given integers d, k and graph G, can we obtain a graph with diameter d via at most k edge deletions? We determine the computational complexity of this and related problems for different values of d.

Authors

• Eun Jung Kim LAMSADE-CNRS, Université de Paris-Dauphine
• Martin Milanič
• Jérôme Monnot University of Paris-Dauphine
• Christophe Picouleau

Keywords

• Graph diameter
• Blocker problem
• Polynomial algorithm
• NP-complete