2025-11-19T14:49:14.164403

Graph Irregularity via Edge Deletions

Bensmail, Catherinot, Fioravantes et al.
We pursue the study of edge-irregulators of graphs, which were recently introduced in [Fioravantes et al. Parametrised Distance to Local Irregularity. IPEC, 2024]. That is, we are interested in the parameter Ie(G), which, for a given graph G, denotes the smallest k >= 0 such that G can be made locally irregular (i.e., with no two adjacent vertices having the same degree) by deleting k edges. We exhibit notable properties of interest of the parameter Ie, in general and for particular classes of graphs, together with parameterized algorithms for several natural graph parameters. Despite the computational hardness previously exhibited by this problem (NP-hard, W[1]-hard w.r.t. feedback vertex number, W[1]-hard w.r.t. solution size), we present two FPT algorithms, the first w.r.t. the solution size plus Delta and the second w.r.t. the vertex cover number of the input graph. Finally, we take important steps towards better understanding the behaviour of this problem in dense graphs. This is crucial when considering some of the parameters whose behaviour is still uncharted in regards to this problem (e.g., neighbourhood diversity, distance to clique). In particular, we identify a subfamily of complete graphs for which we are able to provide the exact value of Ie(G). These investigations lead us to propose a conjecture that Ie(G) should always be at most m/3 + c, where $m$ is the number of edges of the graph $G$ and $c$ is some constant. This conjecture is verified for various families of graphs, including trees.
academic

グラフ不規則性とエッジ削除

基本情報

  • 論文ID: 2511.14514
  • タイトル: Graph Irregularity via Edge Deletions
  • 著者: Julien Bensmail, Noémie Catherinot, Foivos Fioravantes, Clara Marcille, Nacim Oijid
  • 分類: math.CO（組合数学）、cs.CC（計算複雑性）、cs.DM（離散数学）
  • 発表日: 2025年11月18日（arXiv プレプリント）
  • 論文リンク: https://arxiv.org/abs/2511.14514

要約

本論文は、グラフのエッジ不規則化問題、すなわちパラメータIe(G)を研究する。これは、グラフGを局所不規則グラフ（任意の隣接する2つの頂点の次数が異なる）に変換するために削除する必要がある最小エッジ数kを表す。この問題はNP困難かつW1困難であることが証明されているにもかかわらず、著者らは2つのFPTアルゴリズムを提案している。1つは解のサイズと最大次数Δに関するもの、もう1つは頂点被覆数に関するものである。さらに、著者らは密グラフ、特に完全グラフについて詳細に研究し、重要な予想を提案している：任意の連結グラフGに対して、Ie(G) ≤ m/3 + cが成り立つ。ここで、mはエッジ数、cは定数である。この予想は、木を含む複数のグラフクラスで検証されている。

研究背景と動機

問題定義

グラフ理論において、正則グラフはすべての頂点の次数が同じグラフを表す。双対概念として、研究者らは複数の不規則性定義を提案している：

  1. 不規則グラフ：すべての頂点の次数が互いに異なる
  2. 高度不規則グラフ：各頂点の隣接頂点の次数がすべて異なる
  3. 局所不規則グラフ：任意の隣接する2つの頂点の次数が異なる

本論文は局所不規則グラフの概念に焦点を当てている。

研究の重要性

  1. 理論的意義：局所不規則性はグラフ論における重要な構造的性質であり、有名な1-2-3予想と密接に関連している
  2. 操作的視点：従来の研究は主にエッジの追加（エッジの多重性の増加など）を通じて不規則化を実現していたが、本論文はエッジ削除というより制限的な操作を探索している
  3. パラメータ複雑性：この問題は豊かな計算複雑性の階層を示しており、パラメータ化アルゴリズム研究に適している

既存方法の限界

  • Fioravantesら10は最近、エッジ不規則化部分グラフの概念を導入し、最適なエッジ不規則化部分グラフの計算がNP困難であることを証明した
  • この問題は解のサイズ、フィードバック頂点集合に関してW1困難である
  • 密グラフ（完全グラフなど）や特定の構造パラメータ（近傍多様性、クリークへの距離）に対する動作はまだ明確ではない

研究動機

著者らの目的は以下の通りである：

  1. 特定のパラメータに対する効率的なFPTアルゴリズムを設計する
  2. 異なるグラフクラスのIe(G)の正確な値または上界を理解する
  3. Ie(G)とグラフのエッジ数mの間の普遍的な関係を探索する

核心的貢献

  1. パラメータ化アルゴリズム：
    • 解のサイズkと最大次数Δに関するFPTアルゴリズムを提案。核サイズはO(k∆^(2k+2))
    • 頂点被覆数vcに関するFPTアルゴリズムを提案。時間複雑度は2^O(vc^4)·n^O(1)で、従来のILPベースの方法より優れている
  2. 構造的結果：
    • 経路と環に対してIeの正確な公式を証明
    • 完全二部グラフKn,mに対して：n≠mのときIe = 0、n=mのときIe = n
    • 木Tに対して：Ie(T) ≤ |E(T)|/3（Tが経路でない場合）
    • 位数が三角数tk = k(k+1)/2である完全グラフに対して、正確な公式を提供：Ie(Ktk) = |E(Ktk)| - k(k+1)(k-1)(3k+2)/24
  3. 重要な予想（予想1）： 定数cが存在して、m本のエッジを持つ任意の連結グラフGに対してIe(G) ≤ m/3 + cが成り立つ
  4. 理論的洞察：
    • Ie(G)の一般的な下界を提供：Ie(G) ≥ ⌈conf(G)/(2∆-1)⌉
    • 最適なエッジ不規則化部分グラフ内のエッジは競合エッジの近くにある必要があることを証明（補題1）

方法の詳細

タスク定義

入力：グラフG = (V, E)と正整数k ≥ 1
出力：Ie(G) ≤ kであるかを判定する（判定版）または最適なエッジ不規則化部分グラフを計算する（最適化版）

定義：

  • グラフGは局所不規則である。任意のエッジuv ∈ Eに対してdG(u) ≠ dG(v)の場合
  • エッジ不規則化部分グラフ：エッジ集合S ⊆ Eで、G-Sが局所不規則となるもの
  • Ie(G)：最小エッジ不規則化部分グラフのサイズ
  • conf(G)：競合数。dG(u) = dG(v)を満たすエッジuvの数

核心的技術方法

1. k+Δに関する核化アルゴリズム（定理2）

主要補題1：Gの最適なエッジ不規則化部分グラフをSとすると、Sの任意のエッジeから何らかの競合エッジまでの距離は最大2|S|-1である。

証明の概要（帰納法）：

  • 基礎：k=1の場合、削除される唯一のエッジは何らかの競合に隣接している必要がある
  • 帰納：k≥2に対して、任意の競合uvについて、e∈Sが存在してeはuまたはvに隣接している。G-{e}に帰納仮説を適用する

核化ルール：

  1. conf(G) ≥ k(2∆+1)の場合、否定インスタンスを返す
  2. 各競合エッジeに対して、球B(e, 2k+1)を定義。eの端点から最大2k+1の距離にあるすべての頂点を含む
  3. 部分グラフH = G∪e∈EC Veを構築。ここでVeはeの球
  4. Hの頂点次数をGの次数と一致するように調整（葉を追加することで）

核サイズ分析：

  • 競合数|EC| ≤ k(2∆+1)
  • 各球は最大2∆^(2k)個の頂点を含む
  • 総頂点数：|V(H)| ≤ 2k(2∆+1)∆^(2k+1) = O(k∆^(2k+2))

2. 頂点被覆数に関するアルゴリズム（定理5）

アルゴリズムフレームワーク：

  1. C = {u1,...,uvc}を最小頂点被覆、I = V\Cを独立集合とする
  2. Iを2つの部分に分割：
    • I1：Cの何らかの次数≤5vcの頂点に隣接する独立集合の頂点
    • I2：その他の独立集合の頂点
  3. G1 = GC∪I1、G2 = GC∪I2を定義
  4. S1 = S∩E(G1)のすべての可能性を列挙（最大2^O(vc^4)種類）
  5. 各S1に対して、G-(S1∪S2)が局所不規則となるような最小S2⊆E2を計算

主要な観察（請求項7）： S1と一致する任意の最適なエッジ不規則化部分グラフSに対して、|S∩E2| ≤ vc^2

最適化技法（請求項8）： u∈Cおよびv1,v2∈I2に対して、uv1∈Sだがuv2∉Sの場合、交換して等価な最適解を得ることができる。したがって、各u∈Cについて削除されるエッジ数kiを推測するだけで十分で、Σki ≤ vc^2を満たす。

時間複雑度：2^(vc+5vc^2)^2 · vc^(vc^2) · n^2 = 2^O(vc^4) · n^O(1)

技術的革新点

  1. 距離制限技術：補題1は最適解内のエッジと競合の空間関係を確立し、これが核化の鍵である
  2. 次数保持戦略：葉を追加することで次数を保持し、部分問題が元の問題と等価であることを確保
  3. 独立集合の階層化：独立集合を隣接頂点の次数で階層化し、グラフの二部構造を利用
  4. 交換補題：独立集合に削除する具体的なエッジが重要ではなく、削除数のみが重要であることを証明

実験設定

本論文は理論研究であり、主に数学的証明を通じて結果を検証している。ただし、複数のグラフクラスに対して構成的分析を実施している：

研究対象のグラフクラス

  1. 経路Pnと環Cn
  2. 完全二部グラフKn,m
  3. 木
  4. 完全グラフKn（特に位数が三角数の場合）
  5. 一般的な連結二部グラフ
  6. 一般的な連結グラフ

分析方法

  • 正確な公式の導出：経路、環、特定の完全グラフに対して
  • 上界の証明：木、二部グラフ、一般グラフに対して
  • 構成的証明：界に達する具体的なエッジ不規則化部分グラフを提示
  • 再帰的アルゴリズム：木に対してO(n∆^3)の正確な計算アルゴリズムを提供

実験結果

主要な結果

1. 経路と環（定理9）

n≥2の経路Pnに対して：

  • Ie(Pn) = (n-1)/3、n≡1 (mod 3)の場合
  • Ie(Pn) = ⌈(n-1)/3⌉、n≡2 (mod 3)の場合
  • Ie(Pn) = ⌊(n-1)/3⌋、その他の場合

n≥3の環に対して：Ie(Cn) = Ie(Pn) + 1

証明戦略：経路を連続する3エッジのグループに分割し、各グループから少なくとも1つのエッジを削除

2. 完全二部グラフ（定理10）

  • Ie(Kn,m) = 0、n≠mの場合（既に局所不規則）
  • Ie(Kn,n) = n（1つの頂点のすべてのエッジを削除）

3. 木（定理13）

主定理：任意の木Tに対して、Tが経路であるか、またはIe(T) ≤ |E(T)|/3のいずれかが成り立つ

証明の概要：

  • 星と双星の細分グラフに対して、中心から距離2のエッジを削除することで
  • 一般的な木に対して、帰納法を使用し、最も深い次数≥3の頂点を選択
  • 詳細な場合分析（部分木構造と次数による）

アルゴリズム結果（定理15）：木のIe(G)をO(n∆^3)時間で正確に計算できる

4. 完全グラフ（定理16）

位数n = tk = k(k+1)/2（第k番目の三角数）の場合：

Ie(Ktk) = |E(Ktk)| - mk

ここで mk = k(k+1)(k-1)(3k+2)/24

構成：最大エッジ数を持つ局所不規則グラフTkは次数列を持つ：1個の次数n-1の頂点、2個の次数n-2の頂点、...、k個の次数n-kの頂点

5. 一般グラフの上界

二部グラフ（定理11）： 最小次数が1の連結二部グラフに対して：Ie(G) ≤ n-1

一般グラフ（定理12）： 任意の連結グラフに対して：Ie(G) ≤ ⌊m/2⌋ + n + ∆ - 2

予想の検証

予想1：定数cが存在して、m本のエッジを持つ任意の連結グラフGに対してIe(G) ≤ m/3 + cが成り立つ

検証済みのグラフクラス：

  • ✓ 環（c≥2）
  • ✓ 木
  • ✓ 位数が三角数の完全グラフ
  • ✓ 完全二部グラフ
  • ✓ 定理12を通じて、一般グラフはより弱い界を満たす

タイトネス（定理1）： グラフHの各エッジを2回細分して得られるグラフGに対して：Ie(G) ≥ m/3 したがって、1/3係数はタイトである。

主要な洞察

  1. 競合解決効率：1つのエッジを削除すると最大2∆-1個の競合が解決される（注釈1）
  2. 連結性要件：予想1の連結性は必須である（完全マッチングはすべてのエッジを削除する必要がある）
  3. 疎vs密：疎グラフ（木など）はm/3界に達しやすく、密グラフ（完全グラフなど）は複雑な動作を示す

関連研究

グラフ不規則性研究の系統

  1. 不規則グラフ6：Chartrandらが導入した不規則強度。エッジの多重性を増加させることですべての次数を異なるものにする
  2. 高度不規則グラフ1,5：Alaviらが研究。各頂点の隣接頂点の次数がすべて異なるグラフ
  3. 局所不規則グラフ2,12：
    • Karoński, Luczak, Thomasonが1-2-3予想を提案（最近Keuschが解決13）
    • Baudonらが正則グラフを局所不規則部分グラフに分解することを研究

削除操作を通じた性質の導入

  1. 正則性の導入3,4：
    • Bazganらがエッジ回転を通じて次数匿名化を実現
    • Belmonte と Sauが大きな奇導出部分グラフの探索を研究
  2. 頂点不規則化部分グラフ11：
    • Fioravantesらが頂点削除を通じて局所不規則性を導入
    • 木幅と最大次数に関するFPTアルゴリズムを証明
  3. エッジ不規則化部分グラフ10：
    • 最近導入された概念（本論文の直接的な前駆）
    • NP困難性と複数のW1困難結果を証明

本論文の独自の貢献

関連研究と比較して：

  • 初めてk+ΔおよびVCに関するFPTアルゴリズムを提案
  • 初めて複数のグラフクラスの正確な値を体系的に研究
  • 初めてm/3+c予想を提案し、大規模に検証
  • 完全グラフを深く研究し、密グラフパラメータの理解の基礎を確立

結論と考察

主要な結論

  1. アルゴリズム層：問題が複数のパラメータでW1困難であるにもかかわらず、複合パラメータ（k+Δ）または構造パラメータ（頂点被覆数）を通じてFPTアルゴリズムを得ることができる
  2. 構造層：
    • 複数のグラフクラスのIe(G)を正確に決定またはタイトに界定できる
    • 木と疎グラフの動作は比較的単純
    • 完全グラフは三角数に関連する精妙な構造を示す
  3. 理論層：予想1が成立すれば、Ie(G)の漸近的動作を統一的に特徴付けることができる

限界

  1. 完全グラフの不完全性：位数が三角数の場合のみ解決され、一般的な完全グラフKnの正確な値はまだ不明である
  2. 予想1の定数：複数のグラフクラスで検証されているが、定数cの正確な値と一般的な証明はまだ欠けている
  3. アルゴリズム効率：
    • k+ΔのFPTアルゴリズムは指数的にΔ^(2k)に依存し、実際の応用は制限される
    • 頂点被覆アルゴリズムはILP方法を改善しているが、2^O(vc^4)の依存性がある
  4. 密グラフパラメータ：近傍多様性、クリークへの距離などのパラメータのFPT性はまだ未解決

今後の方向

著者が明確に提案している方向：

  1. 動的競合パラメータ：静的confパラメータを改善して、競合の進化を動的に捉える
  2. 完全グラフと立方グラフ：
    • 一般的な完全グラフKnのIeの正確な値を決定
    • 立方グラフの界を改善
  3. k-退化グラフへの拡張：類似の技術を使用して(k-1)n + ⌊n/3⌋の上界を得る
  4. 木幅パラメータ化：文献11の頂点版アルゴリズムをエッジ版に適応させるべき
  5. 近傍多様性：完全グラフ問題を完全に解決した後に処理する必要がある

深い評価

利点

  1. 理論的深さ：
    • 証明技術は精妙。特に補題1の距離制限と木の帰納的証明
    • 核化アルゴリズムはパラメータ化複雑性の深い理解を示す
    • 完全グラフの三角数結果は深い組合せ構造を明らかにする
  2. 体系性：
    • 疎から密へ複数のグラフクラスをカバー
    • アルゴリズム結果と構造結果の両方を含む
    • 理論分析と構成的証明を組み合わせ
  3. 予想の提案：
    • 予想1は強い統一性と示唆性を持つ
    • 複数のグラフクラスでの検証は信頼性を高める
    • 定理1は1/3係数のタイトネスを証明
  4. 執筆品質：
    • 構造が明確で、単純から複雑へ段階的に展開
    • 証明は詳細だが冗長ではない
    • 図（図3、図4など）が理解を補助
  5. 実用的アルゴリズム：
    • 木のO(n∆^3)アルゴリズムは多項式時間複雑度
    • FPTアルゴリズムは実際の応用に理論的保証を提供

不足

  1. 完全性のギャップ：
    • 完全グラフの一般的な場合は未解決で、密グラフの理解を制限
    • 予想1は一般的な証明を欠く
  2. アルゴリズムの実用性：
    • k+Δアルゴリズムの二重指数依存は実際の応用を制限
    • アルゴリズムの実際のパフォーマンスについて実験的評価がない
  3. 定数の最適化：
    • 定理12の界⌊m/2⌋+n+∆-2はタイトでない可能性
    • 各グラフクラスの定数c値は正確に決定されていない
  4. 下界分析：
    • conf(G)/(2∆-1)以外に、より精細な下界技術を欠く
    • 近似アルゴリズムについての議論がない
  5. パラメータ階層：
    • FPTとW1困難の間の境界を完全に特徴付けていない
    • 特定の自然なパラメータ（木幅+Δなど）は未探索

影響力

  1. 理論的貢献：
    • エッジ不規則化部分グラフ研究に堅実な基礎を確立
    • 予想1が成立すれば、重要な組合せ結果となる
    • 方法（特に補題1）は他のグラフ修正問題に適用可能
  2. 後続研究：
    • 完全グラフ問題は組合せ論者の注目を集める
    • FPTアルゴリズム技術は他の局所的性質に一般化可能
    • グラフの局所不規則性の理解に新しい視点を提供
  3. 実用的価値：
    • 木アルゴリズムはネットワーク分析に直接応用可能
    • グラフ匿名化、ネットワーク堅牢性などの応用に理論的支援を提供
  4. 開放性：
    • 明確で魅力的な開放問題を残す
    • 異なる難易度レベルが異なる研究者に適している

適用シーン

  1. ネットワーク設計：隣接ノードが同じ次数を持つことを避ける必要があるシーン（負荷分散など）
  2. グラフ匿名化：エッジ削除を通じて次数パターンを破壊し、プライバシーを保護
  3. 理論計算機科学：
    • パラメータ化複雑性の教育事例
    • グラフ修正問題研究の範例
  4. 組合せ最適化：より複雑な最適化問題の部分問題として

参考文献（主要な引用）

2 Baudon et al. (2015): 正則グラフを局所不規則部分グラフに分解
6 Chartrand et al. (1988): 不規則ネットワーク、不規則強度を導入
10 Fioravantes et al. (2024): エッジ不規則化部分グラフを導入、基本的な難度結果を証明
11 Fioravantes et al. (2025): 頂点不規則化部分グラフの複雑性
12 Karoński et al. (2004): 1-2-3予想
13 Keusch (2024): 1-2-3予想を解決

総合評価：これはパラメータ化複雑性とグラフ論の交差領域における高品質な理論計算機科学論文である。特定の問題（特に完全グラフ）が完全に解決されていないにもかかわらず、論文はエッジ不規則化部分グラフの理解を体系的に推進し、提案された予想は重要な理論的意義を持つ。方法は新規で、証明は厳密で、後続研究に明確な方向を提供する。組合せ数学または理論計算機科学のトップジャーナルへの掲載を推奨する。