部分グラフ同型性判定の回路計算量について

摘要

n頂点入力グラフCに，定数サイズ（k）のパターンガが部分グラフとして含まれるか否かを問うk－部分グラフ同型性判定を定数段の論理回路で計算する場合の計算量について考える.いかなるパターンHに対しても，O（n~k)上界は自明である（ヒント：DNF式）.一方，例えば，パターンがk－starの場合には（kの値によらず）O（n~, log n）サイズの回路で判定可能である（ヒント：k－しきい値関数）．では，この間題の計算量を支配するのは何か，などについて，最近のRossmanによるk-クリークに対するω（n~(k/4)）下界の証明［STOC，08］をスタート地点に議論する．%We consider the constant-depth circuit complexity of the problem of detecting a fixed pattern H of size k in an input graph on n vertices, which is usually called the k-subgraph isomorphism problem. For every pattern, an O(n~k) upper bound is trivial (Hint: Use DNF formulas). Some patterns can be detected faster. For example, a k-star can be detected by constant-depth circuits of size O(n~2 log n) (Hint: Use k-threshold functions). In this talk, we will discuss some complexity issues on this problem. The starting point of this talk is a recent lower bound of ω(n~(k/4)) on the size of constant-depth circuits for the k-clique by Rossman [STOC '08].