概要 - 禁止パターンと植えられた色を持つエッジ色付け問題

タイトル
禁止パターンと植えられた色を持つエッジ色付け問題

時間
2025-07-25 06:59:35

著者
{"Alexey Barsukov","Antoine Mottet","Davide Perinti"}

カテゴリ
{cs.CC,cs.DM}

リンク
http://arxiv.org/abs/2507.19000v1

PDF リンク
http://arxiv.org/pdf/2507.19000v1

概要

この論文は、禁止パターンと植えられた色を持つエッジ塗色問題を調査し、これらの問題の複雑さと表現不能性に焦点を当てています。 著者らは、禁止パターンを持つエッジ塗色問題を、グラフのエッジが特定の「障害物」を避けるように色付けできるかどうかを決定することを目指す問題として定義しています。これらの障害物はエッジ色付きグラフの集合によって定義され、挑戦は、これらの障害物のどれも色付きグラフに表現されない塗色を見つけることです。 この論文は以下のいくつかの主要な貢献を行っています： 1. **塗色と拡張問題の相当性**：ある特定の障害物の集合に対して、著者らは塗色問題（Col(F)）と拡張問題（Ext(F)）が多項式時間で相当することを示しています。Ext(F)は与えられた部分塗色を拡張して障害物を避けることを含みます。 2. **複雑性の二分法**：自然な障害物の集合に対して、著者らはエッジ塗色問題の複雑性の二分法を確立しています。つまり、これらの問題はP（多項式時間で解ける）またはNP-完全であるかのどちらかです。 3. **表現不能性の結果**：著者らは、MMSNPとGMSNPという特定の塗色問題のクラスを説明する論理の関係を調査しています。彼らは、Col(F)がどの顶点色付き構造の家族に対してもCol(G)と等しくないようなエッジ色付き構造の家族が存在することを証明し、分野における未解決の問題に答えています。 論文はまた、以下のような技術的な結果と構造を提供しています： - **色付き決定子**：これらはCol(F)とExt(F)の相当性を証明する助けになるグラフであり、ある特定の障害物の家族に対してそのような決定子の存在が示されています。 - **色同一性ガジェット**：これらは特定のエッジ塗色問題の難しさを証明するために使用されます。 - **無限制約満足問題**：著者らはこれらの問題を使用して、エッジ塗色問題と制約満足問題の相当性を示しています。 全体的に、この論文は禁止パターンと植えられた色を持つエッジ塗色問題を包括的かつ深く分析し、これらの問題の複雑さと表現可能な性についての理解に寄与しています。


推奨論文

非平衡データのためのコルモゴロフ・アーノルド・ネットワーク（KANs）-- 実証的視点

単一ソースパーソナライズドPageRankのためのより厳しい下界

エルク：深層学習コンパイラ技術を用いて、インターコア接続AIチップの効率を探求する

ランクベクトルクラスタリング：理論と応用

計算統計の難解性から生じるトレードオフ

「提案的帰納における断面説明の複雑さ」

任意の欠損モダリティを持つ多様な脳腫瘍セグメンテーションのためのセマンチックガイド付きマスク付き相互学習

多様な分子埋め込みの表現と統合のためのプラットフォーム

ベイズ的な異方分散ガウスプロセスのVecchia近似

クラウドにおけるHSMおよびTPMセキュリティの再考：現実の攻撃と次世代の防御策