エルデシュ数の最小化はどうすればできるのか？

あんまり意味のある話題ではないけど、「エルデシュ数のような数を最小化するには、どのように共著者を増やしていくべきか？」というのが頭の中に浮かんで、なんだかよくわからない状態になっている。

「どういう論文を書くべきか？」という話なのではなくて、「グラフ最適化問題として定式化したときにどうすると最適解が得られるとかあるんだろうか？」という話。より正確には、共著者を n 人までとしたときに、エルデシュ数の最大値 k を最小化するにはどうすればいいのか？という話。

単純に考えると「その時点でエルデシュ数が最大の人と共著すればよい」というような greedy なアルゴリズムがパッと浮かぶけど、果たしてそれで最適な解が得られるのか？のか、それとも、ちゃんと反例が浮かぶのかどうか、も気になる。
また別に単純に考えても、NP-hard な気がする。

例えば、ビジネスの世界だと人と人をつなげる人というのは重要だろうから、こういう計算ができるのは、それなりに意味があるようにも思う。
たぶん、「●●問題」とか名前のついている最適化問題に定式化できるんだろうなぁ、と推測はしている。