Цель 0-расширения состоит в том, чтобы минимизировать общую взвешенную стоимость ребер с различными цветными конечными точками, а не максимизировать ее, поэтому 0-расширение действительно является проблемой кластеризации, а не проблемой раскраски.Я вообще скептически отношусь к тому, что использование алгоритма кластеризации для цветопередачи даст хорошие результаты.Если вы хотите что-то с теоретической гарантией, вы можете посмотреть приближения к задаче MAXCUT (действительно, обобщение, если существует более двух цветов), но я подозреваю, что алгоритм локального поиска будет работать лучше на практике.