先週国際会議 IWOCA 2026 に参加しました． 面白かった発表をいくつか軽く共有します．

宣伝

共著論文を浜田俊祐さん（M2）が発表しました． Best Student Paper も受賞しました！

Minimum Clique Bicoloring
Shunsuke Hamada, Yuto Okada, Hirotaka Ono, Yota Otachi
📗会議版

「任意の極大クリークが二色以上含む」頂点の（properとは限らない）彩色をクリーク彩色といい，理想グラフ（perfect graph）周辺のクラスの多くがクリーク2彩色可能という面白い事実が知られています． この論文ではクリーク2彩色の中で片側の色の数を最小化してくださいという問題を導入し，色々なクラス/パラメータでアルゴリズム/困難性を示しました．

個人的に面白かった発表

順番は発表順です．

Parameterized Algorithms for Computing MAD Trees
Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann, André Nichterlein, Camille Richer
📗会議版 📕arXiv版

Minimum Average Distance を達成する全域木を MAD Tree と呼ぶらしいです． つまり，全域木 $T$ で $\sum_{u, v \in V} \mathrm{dist}_T (u, v) / \binom{n}{2}$ を最小化するものです． 結構古くからある問題で，色々なグラフクラスでアルゴリズムが与えられているらしいです． これのパラメータ化計算量を考えましたという論文で，木幅で XP，vertex integrity とモジュラ幅で FPT，スプリットグラフで NP 完全あたりを示していました．

Minimizing the Weighted Makespan with Restarts on a Single Machine
Aflatoun Amouzandeh, Klaus Jansen, Lis Pirotton, Rob van Stee, Corinna Wambsganz
📗会議版 📕arXiv版

（理解が怪しめです）

単一マシンのスケジューリング問題で，以下の設定です．

  • 一度に 1 つのジョブを処理できる機械が 1 つあります．
  • ジョブ $j$ が時間 $r_j$ に来ます．
  • ジョブ $j$ は完了に $p_j$ 単位時間かかります．
  • ジョブ $j$ には重み $w_j$ があります．
  • すべてのジョブを完了してください．
  • ジョブ $j$ が終了した時間を $C_j$ として，重み付き総所要時間（weighted makespan） $\max_j \{w_j C_j\}$ を最小化してください．
  • 処理中のジョブは中断・再実行できますが，やり直しになって $p_j$ 単位時間かかります．
    • これが restart と呼ばれていて， preemption では中断したところから再開可能です．

これのオンライン版（時間 $r_j$ にジョブが来る）を考えて，競合比解析を行っていました．

Removable Online Knapsack: Exploiting Recourse and Bounded Item Sizes
Dimitris Fotakis, Laurent Gourvès, Aris Pagourtzis, Panagiotis Patsilinakos
📗会議版

これもオンラインアルゴリズムで，オンライン版のナップサック問題です． オンラインナップサック問題では一般的に（？）価値 $=$ 重みになっていて，以下のような設定で考えるようです．

  • 順にアイテムが来ます．
  • $i$ 番目のアイテムは，重みが $w_i \in (0,1]$ で，価値も $w_i$ です．
  • アイテムごとにその場でバッグ（容量 $1$ ） に入れるか入れないかを決定します．
  • 最終的なバッグの中の価値（重み）の総和を最大化してください．

ただこれだけだと，以下の敵対的なケースで競合比がいくらでも小さくなります：

  • 重み $=$ 価値が $\varepsilon > 0$ のアイテムをまず出します．
  • バッグに入れる → 次に重み $1$ のアイテムを出して終了（競合比 $\varepsilon / 1 = \varepsilon$）
  • バッグに入れない → アイテムを出さずに終了（競合比 $0 / \varepsilon = 0$）

なので大体追加の設定があり， [Iwama & Taketomi, ICALP 2002] が代表的な例らしいです： この先行研究では，バッグにすでに入れたアイテムを捨てられる設定を考えて，その最適競合比 $(\sqrt{5}+1)/2 \approx 1.618$ が示されました．

今回の論文では，削除に加えて

  • (bound awareness) アイテムの重みの上界が事前知識として与えられる
  • (recourse) 過去に入れなかったアイテムを $k$ 回まで復活させられる（多分）

二つの要素を追加した版を考えて競合比解析をしていました． あとは，そのオンラインアルゴリズムを使って適応的なアルゴリズム（重みの上界が事前知識として与えられないが，上界を仮定して動作→仮定が違ったら更新を繰り返してある程度の競合比を保つ）も与えていました．

One Sequence to Rule them All: O(1)-Time Parallel Generation of Mixed-Radix Gray Codes
Lucia Moura, Prangya Parida, Brett Stevens, Aaron Williams
📗会議版

（理解が怪しめです）

基数が複数混ざった列を通常のグレイコード的に列挙する問題の研究でした． たとえば，$\{0, 1\} \times \{0, 1\} \times \{0, 1, 2\}$ は 000 → 001 → 002 → 012 → 012 → 010 → 011 → 111 → 112 → 110 → 100 → 101 → 102 のように列挙できます（アブスト参照）．

000… から始めて最悪 $O(1)$ 時間ずつで列挙するアルゴリズムが知られていて，Knuth 先生の The Art of Computer Programming にも載っている？らしいです．

この論文の貢献は「特定の？グレイコードに対して $k$ 番目の列（と追加で実行に必要な $O(n)$ メモリ部分）を計算するアルゴリズム」を与えたことで，これによりたとえば $p$ 並列で $N / p$ 個ずつ列挙して試すみたいなことが可能になりました．（多分）

Realizing Planar Linkages in Polygonal Domains
Thomas Depian, Carolina Haase, Martin Nöllenburg, André Schulz
📗会議版 📕arXiv版

平面的グラフ $G$ と各辺の長さ $\ell \colon E \to \mathbb{R}$ が与えられるので，頂点集合 $V$ を平面的かつ辺長制約を満たすように $\mathbb{R}^2$ に埋め込んでくださいというタイプの問題です． この問題は [ADDELS, SoCG 2016] (JoCG, 2025) で unit-length （つまり辺長がすべて $1$）の場合でも $\exists \mathbb{R}$ 完全であることが示されていました．

今回の論文では，追加で多角形が与えられるのでその内部にグラフを描いてくださいという制約が加わった版の問題を考えています． 発表は困難性の話がメインで，

  • $|G|$ をパラメータとして XP / W[1] 困難（多角形に複雑さを持たせられる）
  • $G$ がパスでも，その終点・始点の位置が指定されたときには NP 困難になる

という結果の説明でした． （計算幾何学あるあるの）帰着の図が直感的で楽しい発表でした1． 論文では Fig.3 から Fig. 6 あたりです． これ以外の結果も Abstract に書いてありました．

An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs
Nacim Oijid, Clara Marcille
📗会議版 📕arXiv版

グラフ $G$ の Monitoring Edge-Geodetic set（MEG-set）とは，頂点集合 $M \subseteq V$ で「任意の辺 $e$ についてある頂点ペア $u, v \in M$ が存在し $\mathrm{dist}_G(u,v) \lt \mathrm{dist}_{G-e}(u,v)$ 」を満たすものです． つまり，辺の削除を最短パス長で検知できる頂点集合です．

これは [Foucaud, Narayanan & Sulochana, CALDAM 2023] で導入された概念で，NP困難性といくつかのクラスに対する多項式時間アルゴリズムが知られています． 面白いのは，既存の多項式時間アルゴリズムのほとんど（サイクル以外）は，そのクラス上で以下の性質を示して与えているようです：

  • 性質 (meg-minimal) すべての MEG-set に含まれる頂点を必須頂点（mandatory vertex）と呼ぶ．このとき，すべての必須頂点からなる集合は MEG-set である．

これが成り立つとき，その集合が明らかにユニークな最小 MEG-set です． ある頂点が必須頂点であるかどうかの特徴付け（多項式時間判定可能）が与えられている (Theorem 4.1, [FMMSST, DAM (2025)]) ため，この性質を示せば多項式時間で解けるらしいです．

この論文では，これまでに強弦グラフ（strongly chordal），スプリットグラフなど弦グラフのサブクラスについてこの性質が知られていたところを，弦グラフでも示して一般化していました．

Algorithmic Meta-Theorems for Distributed Computing
Pierre Fraigniaud
（招待講演）

  • CONGEST モデル
  • local FO formula （一階述語論理式 $\varphi$ の中でも，ある $r = f(\varphi)$ が存在して「各頂点から距離 $r$ の頂点たち」を順に見るだけで判定可能なもの（多分））
  • bounded expansion を持つグラフクラス $\mathcal{G}$

に対して $O_{\varphi, \mathcal{G}}(\log n)$ ラウンドで動作する（決定的）モデル検査アルゴリズムを与えた（[BFFGGMRT, STOC 2026]）という話が主でした．

たとえば $C_4$-freeness とかは各頂点 $v$ から $2$ 頂点先ぐらいを見て $C_4$ があるか判定すればよいので local FO formula です． ただ分散とかでは $C_4$-freeness も非常に難しい問題らしく，Set Disjointness という問題を二人でやるときの通信計算量から上手くグラフを構築してシミュレートすると $\tilde\Omega(\sqrt{n})$ ラウンド必要という下界が示せるという話もあって知らない分野なので面白かったです． 下界の構成を見ると bounded expansion が上手く効いている感じがしました．

[Nešetřil & Ossona de Mendez, Distrib. Comput. (2016)] によって CONGEST モデルで $O_{\mathcal{G}}(\log n)$ ラウンドで（bounded expansion で） low treedepth coloring ができるらしく，部分グラフ判定などはそれを使えば判定可能でした． （どれぐらいのギャップがあるのかはわかりませんでしたが）それ以後 local FO formula 全体に一般化できるかは未解決で，今回の STOC の論文で肯定的に解決されたようです．

  1. 大体の場合，“直感的"をちゃんと証明するパートは辛いですが… ↩︎