Решаема ли такая задача за полиномиальное время?

Дан полный взвешенный граф из n вершин. Веса рёбер даны. Два игрока по очереди удаляют из графа по 1 вершине, пока не останется 2 вершины. Цель первого игрока — максимизировать вес оставшегося ребра, а второго — минимизировать. Определить вес оставшегося ребра при условии, что оба игрока играют оптимально.