リーフパワー

グラフ理論の数学分野において、木Tのk葉冪とは、頂点がTの葉であり、辺がTにおける距離がk以下である葉のペアを結ぶグラフGのことである。つまり、Gはグラフ冪の誘導部分グラフである。${\displaystyle T^{k}}$⁠ 、 Tの葉によって誘導されるこのように構築されたグラフGの場合、 TはGのk葉根と呼ばれる。

グラフが葉冪であるとは、あるkに対してk葉冪であることを意味する。^{[ 1 ]}これらのグラフは、進化系統樹を再構築する問題である系統発生学に応用されている。

強弦グラフのべき乗は強弦グラフであり、木は強弦グラフであるため、葉のべき乗は強弦グラフであることがわかります。 ^{[ 2 ]} 実際、葉のべき乗は強弦グラフの適切な部分クラスを形成します。グラフが葉のべき乗であるのは、それが固定許容NeSTグラフである場合のみです^{[ 3 ]。}そして、そのようなグラフは強弦グラフの適切な部分クラスです。^{[ 4 ]}

Brandstädt ら (2010)では、区間グラフと、より広いクラスの根付き有向パスグラフがリーフパワーであることが示されています。無差別グラフは、まさにその基となる木がキャタピラーツリーであるリーフパワーです。

kの値が有界な場合、k 葉のべき乗は有界なクリーク幅を持ちますが、指数が有界でない葉のべき乗ではそうではありません。^{[ 5 ]}

グラフが3葉冪であるのは、それが（雄牛、矢、宝石）を含まない弦グラフである場合に限る。^{[ 6 ]}この特徴付けや同様の特徴付けに基づいて、3葉冪は線形時間 で認識できる。^{[ 7 ]}

4葉冪グラフの特徴付けは、Rautenbach (2006)およびBrandstädt、Le & Sritharan (2008)によって行われ、線形時間での認識も可能になります。5葉冪グラフと6葉冪グラフの認識も、それぞれ Chang と Ko (2007) ^{[ 8 ]}および Ducoffe (2018) ^{[ 9 ]}によって線形時間で解決されています。

k ≥ 7の場合、k葉べき乗の認識問題は長い間未解決でしたが、Lafond (2021) は、任意の固定kに対してk葉べき乗を多項式時間で認識できることを示しました。しかし、このアルゴリズムはパラメータkに大きく依存するため、実用には適していません。

また、 k-葉パワーの認識は、 kと入力グラフの縮退度によってパラメータ化される場合、固定パラメータ扱い可能であることが証明されている。 ^{[ 10 ]}