2人のコンピューター科学者が、非常に予想外の場所で、グラフ理論の突破口として役立つアイデアを見つけました。
2019年10月、ジェイコブホルムとエヴァローゼンバーグは数か月前に公開した作品をめくっていましたが、突然、何か深刻なことに遭遇したことに気づきました。
何十年もの間、コンピューターサイエンティストは、エッジが「平面」のままになるように、つまりエッジが交差しないように、特定のグラフにエッジを追加できるかどうかを判断するための迅速なアルゴリズムを考案しようとしてきました。しかし、20年以上前に公開されたアルゴリズムの改善に成功した人は誰もいません。
ホルムとローゼンバーグは彼らの仕事の中でそれを見つけて驚いたこのアルゴリズムを非常に強力に改善することを可能にしたアイデアがあります。コペンハーゲン大学のコンピューター科学者であるホルム氏は、「実際のアルゴリズムに対する主要な障害の1つを整理した」と述べた。 「おそらく、この問題を完全に開示しました。」
カップルは急いで新しい記事に取り組みました。彼らは6月に計算理論に関する計算機械協会シンポジウムでそれを発表しました。そこでは、以前のバージョンよりも指数関数的に優れた平面性についてグラフをチェックする方法を詳しく説明しました。
「新しいアルゴリズムは本当に見事です」と、ルイ大学のコンピューター科学者で、現在2番目に速いアルゴリズムについて説明している1996年の論文の共著者であるジュゼッペイタリアーノは述べています。 「私がその作品の執筆に関わったとき、私はこれが起こり得るとは思いませんでした。」
グラフは、エッジで接続された頂点のコレクションです。ソーシャルメディアから道路網やボード上の電気導体まで、あらゆるものにラベルを付けるために使用できます。後者の場合、グラフが平面でない場合、2つの導体が互いに交差し、短絡が発生します。
1913年に、平面グラフは、ストランドマガジンに掲載された、3つの家に関する複雑な「共同」パズルに登場しました。この出版物は、通信が互いに交差しないように、3つの家の通信を敷設し、それぞれを3つのエネルギーキャリア（水、ガス、電気）で接続するように読者に求めました。このタスクが克服できないことを理解するのに時間はかかりません。
ただし、より複雑なグラフの場合、それらが平面であるかどうかは必ずしも明らかではありません。新しい道路を計画する場合のように、複雑なグラフにエッジを追加し始めたときに、複雑なグラフが平面のままであるかどうかを判断するのはさらに困難です。
コンピュータ科学者は、グラフのごく一部だけが変更されたときにグラフの各部分を通過することなく、グラフが平面のままであるように、必要な変更を行うことができるかどうかをすばやく判断できるアルゴリズムを長い間探していました。 1996年のアルゴリズムでは、これにいくつかのステップが必要でした。これは、グラフ内の頂点の数の平方根にほぼ比例します。
「毎回すべてを最初からチェックするよりもはるかに優れていますが、完璧ではありません」とホルム氏は言います。
新しいアルゴリズムは、グラフ内の頂点の数の対数の3乗に比例するステップ数で平面性をチェックします-改善は指数関数的です。デンマーク工科大学のHolmとRothenbergは、昨年発見した平面グラフの特殊な特性を利用して、このスピードアップを達成しました。
それらの方法を理解するには、最初に同じ平面グラフをさまざまな方法で描画できることに注意する必要があります。これらのオプションのすべての接続は同じままですが、エッジはさまざまな方法で相互に相対的に配置できます。
たとえば、図Aは、頂点2と3を接続するエッジに対して、頂点1、2、3を構成する三角形を反転することにより、図Bに変更できます。図Bの上部は、頂点4と5に対して反転することもでき、図Cになります。異なるが、同じグラフを示します。
ここで、平面グラフの2つの頂点（たとえば、頂点1と6）を接続する新しいエッジを挿入するとします。これを行うには、一連のフリップを実行します。左側の開始位置から、2回のフリップで、頂点1を、他のエッジと交差することなく頂点6に接続できる場所に転送できます。
2019年の論文で、HolmとRothenbergは、一部の図面が他の図面よりもエッジ挿入に有利であることを発見しました。これらの「良い」パターンは、平面性を損なうことなく新しいエッジを追加するために数回のフリップを必要とするだけです。
彼らが10月に遅ればせながら気付いたのは、新しいエッジを追加できる位置に近づくフリップによって、グラフがすでに定義されている優れたパターンの1つに近づくことです。フリップのシーケンスが必然的にグラフを優先パターンに近づけることを示すことにより、エッジを追加する方法を見つけるために必要なフリップの数を制限する新しいアルゴリズムを作成できます（可能な場合）。
「この新しい分析で問題を解決できることにすぐに気づきました。
概念が非常に単純なアルゴリズムです」とHolm氏は述べています。
JacobHolmとEvaRothenberg
新しいアルゴリズムは、解決策を探すために一度に1つのフリップを実行します。その結果、次の2つのいずれかが発生します。アルゴリズムが必要なエッジを挿入する方法を見つけるか、次のフリップが前のエッジをキャンセルします。その後、アルゴリズムは新しいエッジを追加する方法がないと結論付けます。
「このアルゴリズムを怠惰な貪欲と呼びます」とRotenbergは説明しました。 「新しいリブに対応するために必要な変更を加えるだけです。」
彼らの新しい方法は、そのようなタスクに可能な限り最高のアルゴリズムのパフォーマンスを概算しますが、一致しません。新しいアルゴリズムはまた、ほとんどの実際のアプリケーションで使用するにはあまりにも多くのステップを経る必要があります-通常、グラフはブルートフォーステストを行うのに十分単純です。
しかし、ホルムとローゼンバーグにとって、アルゴリズムの速度は、それを加速させたアイデアほど重要ではありません。 「この理解からすぐに結果があります」とローテンバーグは言いました。
Italianoは、最終的には実際の用途が見つかると考えています。 「遅かれ早かれ、それは数学を使ったコンピュータサイエンスの外にあるものに確実に影響を与えるでしょう」と彼は言いました。
さらに高速なアルゴリズムがいつ登場するかは誰にもわかりません。これには、まったく新しいブレークスルーが必要な場合もあれば、秘密の要素がすでにどこかに存在していて、古い研究の山の中で待っている場合もあります。