В октябре 2019 Якоб Хольм и Ева Ротенберг пролистывали работу, опубликованную ими за несколько месяцев до этого – и вдруг поняли, что наткнулись на нечто серьёзное. Десятилетиями специалисты по информатике пытались разработать быстрый алгоритм для определения того, можно ли добавить к определённому графу рёбра так, чтобы он остался «планарным» – то есть, чтобы его рёбра не пересекались. Однако ни у кого не получалось улучшить алгоритм, опубликованный более 20 лет назад.

Хольм и Ротенберг с удивлением обнаружили, что в их работе есть идея, позволявшая достаточно сильно улучшить этот алгоритм. Она «разобралась с одним из главных препятствий на пути к реальному алгоритму, — сказал Хольм, специалист по информатике из Копенгагенского университета. – Возможно, мы полностью раскрыли этот вопрос».

Парочка поспешила приступить к работе над новой статьёй. Они представили её в июне на симпозиуме по вычислительной теории, проводимом Ассоциацией вычислительной техники, где подробно описали метод проверки графа на планарность, превосходящий предыдущий вариант экспоненциально.

«Новый алгоритм устроен поистине мастерски, — сказал Джузеппе Италиано, специалист по информатике из Луисского университета, соавтор работы от 1996 года, где описывается уже теперь второй по скорости алгоритм. – Когда я участвовал в написании той работы, я не думал, что такое может случиться».

Графы – это наборы вершин, соединённых рёбрами. С их помощью можно обозначать всё – от социальных сетей до дорожных сетей и электрических проводников на плате. Если в последнем случае граф не будет планарным, то два проводника пересекут друг друга, что приведёт к короткому замыканию.

Ещё в 1913 году планарные графы появились в сложной «коммунальной» задачке про три домика, опубликованной в журнале The Strand Magazine. Издание попросило читателей проложить коммуникации для трёх домов, соединяющие каждый из них с тремя энергоносителями – водой, газом и электричеством – так, чтобы коммуникации не пересекались друг с другом. Не нужно много времени, чтобы понять, что эта задача неразрешима.

Однако в случаях с более сложными графами не всегда очевидно, являются ли они планарными. Ещё сложнее сказать, останется ли сложный граф планарным, когда вы начнёте добавлять к нему рёбра – как бывает при планировке новых дорог.

Специалисты по информатике давно ищут алгоритм, способный быстро определить, можно ли внести нужное изменение так, чтобы граф оставался планарным, не перебирая при этом каждую из частей графа, когда изменениям подвергается лишь малая его часть. Алгоритму от 1996 года требовалось для этого количество шагов, примерно пропорциональное квадратному корню от количества вершин графа.

«Это гораздо лучше, чем каждый раз проверять всё с нуля, но не идеально», — сказал Хольм.

Новый алгоритм проверяет планарность за количество шагов, пропорциональное кубу логарифма от количества вершин графа – улучшение получается экспоненциальным. Хольм и Ротенберг из Датского технического университета достигли этого ускорения, воспользовавшись преимуществом особого свойства планарных графов, открытого ими в прошлом году.