@techreport{oai:ipsj.ixsq.nii.ac.jp:00238532,
 author = {藤原, 優 and 儀間, 達也 and 小林, 靖明},
 issue = {5},
 month = {Aug},
 note = {グラフの最大出次数最小化問題と標的集合選択問題に関して，グラフの構造的パラメータの視点での固定パラメータ容易性について議論する．これらの問題は，グラフの構造的パラメータを用いたパラメータ化計算量の研究がよく行われているが，非常に限定された範囲でも困難であることがわかっている．本稿では，Ganian と Korchemna (Algorithmica 2024) によって導入されたスリム木カット幅と呼ばれる辺カットに基づくグラフの構造的パラメータを用いて，前述の 2 つの問題のパラメータ化計算量を議論する．具体的には，どちらの問題もスリム木カット幅をパラメータとして固定パラメータ容易であることを示す．さらに，最大出次数最小化問題に関しては，スリム木カット幅を一般化した木カット幅が定数であっても NP 困難であることを示す．},
 title = {辺カット型グラフパラメータに基づく最大出次数最小化問題と標的集合選択問題の計算複雑性},
 year = {2024}
}