技術的要約：なぜ多数派の錯覚（Majority Illusion）の検出は容易なのか？

問題の定義

本論文は、社会ネットワークにおける**多数派の錯覚（Majority Illusion）**を検出する計算複雑性を調査している。形式的には、社会ネットワークは、頂点がエージェントを表し、エッジが社会的関係を表す無向グラフ $G = (N, E)$ としてモデル化される。エージェントにはバイナリのラベル（例：「赤」または「青」）が割り当てられる。エージェントは、自身の局所的な近傍において少数派のラベルが支配的であると認識する場合、「多数派の錯覚」の下にあるとされる。

中心となる決定問題は、$q$-多数派の錯覚問題である。グラフ $G$ と有理数 $q \in [0, 1]$ が与えられたとき、エージェントのバイナリ・ラベリングが存在し、かつ全体の多数派の色が特定のラベル（例えば「青」）であり、かつ少なくとも $q$ 分率のエージェントが、少数派のラベル（「赤」）を持つ隣接ノードの厳密な過半数を持っているか否かを問うものである。

Grandiら（2025年）による先行研究では、この問題が一般的なグラフにおいてNP完全であり、二部グラフ、平面グラフ、あるいは最大次数6のグラフといった制限されたグラフクラスにおいてもNP完全であることが確立されている。彼らは、頂点被覆数や近傍多様性のようなパラメータに対する固定パラメータ許容（FPT）アルゴリズムを提供し、木幅（treewidth）に対してはXPであることを示したが、どの構造的制限が問題を効率的に解ける（FPT）か、あるいは困難にするかという問いを未解決のまま残した。

手法

著者らは、**パラメータ化複雑性（parameterized complexity）**の枠組みを用いて、$q$-多数派の錯覚問題の計算可能性を分析している。彼らは、以下の様々な構造的グラフパラメータに関して、この問題を体系的に研究している：

• 頂点完全性（Vertex Integrity, $vi(G)$）: 除去した際に成分のサイズが有界な残りの部分を残すような頂点集合の最小サイズ。
• フィードバック・エッジ集合（Feedback Edge Set, $fes(G)$）およびフィードバック・頂点集合（Feedback Vertex Set, $fvs(G)$）: グラフを非巡回にするために除去すべき最小のエッジ数または頂点数。
• グラフクラスへの距離: 離散的なスターグラフ、離散的なパス、およびクラスターグラフ（クリークの非連結和）といった特定のクラスへの頂点またはエッジの距離を測るパラメータ。
• 木深さ（Treedepth, $td(G)$）および木幅（Treewidth, $tw(G)$）: 標準的な構造的パラメータ。

手法には、主に2つのアルゴリズム技術が含まれる：

1. N-fold 整数線形計画法（N-fold ILP）: 頂点完全性のようなパラメータに対するFPT結果を証明するために使用される。問題は、グローバルな制約（全体の多数派と錯覚を起こしているエージェントの総数を保証するもの）と、ローカルな制約（特定の成分に対する局所的な近傍条件を保証するもの）に分離されたN-fold IPとして定式化される。
2. 動的計画法（DP）: 木のような構造（木、パス）およびそれらに近い構造に対して使用される。木に対して、著者らは関連する「Max List Majority Illusion」問題に対する多項式時間アルゴリズムを設計しており、これがフィードバック・エッジ集合に基づくFPTアルゴリズムのサブルーチンとして機能する。

困難性の結果については、既知のW[1]-困難問題、具体的には多次元部分集合和（Multidimensional Subset Sum）（およびそのHalfset変種）および**容量付き頂点被覆（Capacitated Vertex Cover）**からのパラメータ化還元を提供している。

主な貢献と結果

1. 固定パラメータ許容（FPT）

本論文は、いくつかの新しいパラメータ化に対してFPTアルゴリズムを確立している：

• **頂点完全性（$vi(G)$）:** 著者らは、$q$-多数派の錯覚が頂点完全性によってパラメータ化された場合にFPTであることを証明している。アルゴリズムは「セパレータ」集合 $M$ のラベリングを推測し、N-fold ILPを用いて、残りの小さな成分に対してこのラベリングを拡張する。この結果は、**頂点被覆数（$vc(G)$）**に対する改善された実行時間を実現し、複雑さを二重指数関数的（$2^{2^{O(vc)}}$）から単一指数関数的（$2^{O(vc^2 \log vc)}$）へと減少させている。
• フィードバック・エッジ集合（$fes(G)$）: この問題は、フィードバック・エッジ集合数によってパラメータ化された場合にFPTであることが示されている。このアプローチは、フィードバック・エッジに接する頂点のラベリングを推測し、グラフを「ガジェット」（ペンダントリーフ）を持つ木へと変換し、その結果得られるインスタンスを木上の多項式時間動的計画法を用いて解くものである。
• クラスター・エッジ削除数（$cdn(G)$）: 制限された数のエッジを除去することで離散的なクリークの和となるグラフに対して、問題はFPTである。アルゴリズムは、除去されたエッジの端点のラベリングを推測し、クリーク内でのエージェントの状態が、赤色のエージェントの数と固定された外部接続のみに依存するという事実を利用して、クリーク上の動的計画法を用いる。

2. W[1]-困難性と困難性

本論文は、単純な構造に近いグラフであっても問題が困難であることを示す、強力な負の結果を提供している：

• 離散スターグラフへの頂点距離（$dds(G)$）: 多次元Halfset Sumからの還元を通じて、問題は離散スターグラフへの頂点距離によってパラメータ化された場合にW[1]-困難であることが証明されている。
• 離散パスへの頂点距離（$ddp(G)$）: 同様に、問題は離散パスへの頂点距離によってパラメータ化された場合にW[1]-困難である。
• 木深さ（$td(G)$）: 木深さによってパラメータ化された場合、問題はW[1]-困難である。これはGrandiら（2025年）の重要な未解決問題を解決しており、木幅（木深さによって制限される）に対するFPTアルゴリズムは、標準的な計算量仮定の下では起こり得ないことを示唆している。
• クラスターグラフへの頂点距離（$dcg(G)$）: 問題は、クラスターグラフへの頂点距離によってパラメータ化された場合、XPではあるがW[1]-困難である。これは、クラスター・エッジ削除数（$cdn(G)$）によるFPTの結果とは対照的である。

3. 特定のクラスにおける多項式時間解法

著者らは、離散的なパスの和であるグラフに対する線形時間アルゴリズムを提供している。彼らは、パスにおける多数派の錯覚を起こしているエージェントの最大数を、エージェント数のみに基づいた閉形式の式として導出し、パスおよび離散パス上の問題が自明に解けることを示している。

重要性と結論

本論文の主要な貢献は、多数派の錯覚検出問題の計算複雑性の景観に関する包括的な「マップ」を提供したことである。それは、効率的な検出を可能にする特定の構造的特性を特定することで、計算可能なインスタンスと困難なインスタンスの境界を明確にしている。

著者らは、問題が計算可能（FPT）であるためには、社会ネットワークが以下の3つの条件のいずれかを満たさなければならないと結論付けている：

1. 問題が多項式時間で解けるクラス（例：フィードバック・エッジ集合による木、またはクラスター・エッジ削除によるクラスターグラフ）に対して、限定されたエッジ距離内にあること。
2. サイズが限定された成分に対して、限定された頂点距離内にあること（例：頂点完全性による）。
3. 限定された数の、よく構造化されたブロックで構成されていること（例：限定された近傍多様性）。

これらの結果は、鋭い二分法を浮き彫りにしている。すなわち、単純な構造に到達するために少数のエッジを取り除くことはしばしばFPTアルゴリズムをもたらすが、同じ構造に対して少数の頂点を取り除くことは、しばしばW[1]-困難をもたらす。本論文は、**ツイン被覆数（twin-cover number）**によってパラメータ化された場合の複雑性は、クラスターグラフへの頂点距離（XP）とクラスターグラフへのエッジ距離（FPT）の間にあることを指摘し、追加のツイン構造がFPTアルゴリズムを可能にするかどうかという問いを残している。