抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
グラフG,Hでは,GからHへの同形写像はV(G)からV(H)へのエッジ保存マッピングである。LHom(H)によって表示されたリストホモモルフィズム問題において,著者らはグラフGとリストL:V(G)→2 ̄V(H)を与えて,著者らはリストLを付加的に尊重するGからHまでのホモモルフィズムのために,著者らは与えた。ごく最近,Okrasa,Piecyk,およびRz ka.zewski[ESA2020]は不変i ̄*(H)を定義し,SETH O ̄*(i ̄*(H) ̄tw(G))の下では,インスタンスグラフGの木幅tw(G)によってパラメータ化されたLHom(H)に束縛されたタイトな複雑性であることを立証した。。”SET O ̄*(i ̄*(H) ̄tw(G))は,LHom(H)に束縛された堅固な複雑性であると証明した.。”SET O ̄*(I ̄*(H) ̄tw(G))”は,事例グラフGの木幅tw(G)によってパラメータ化された。著者らは,2次元パラメータ化の下で問題の複雑性を研究した。最初の結果として,パラメータがGの最小フィードバック頂点集合のサイズであるならば,i ̄*(H)も正しい複雑性ベースであることを示した。次に,Gのカット幅ctw(G)によるパラメタリゼーションに注意を向けた。JasenとNederlof ̄[ESA 2018]は,List k-Coloring(すなわち,LHom(K_k))が,cがkに依存しない時間O ̄*(c ̄ctw(G))で解決できることを示した。この行動がグラフホモモルフィズムに拡張するかどうかは,1月1回であった。本論文の主な結果として,著者らは負における質問に答えた。新しいグラフ不変mim ̄*(H)を定義して,SETHが失敗するならば,任意のε>0に対して時間O ̄*((mim ̄*(H)-ε) ̄ctw(G))でLHom(H)問題を解決できないことを証明した。これは,あらゆる奇数サイクルに対して,この問題の非リストバージョンが時間O ̄*(c ̄ctw(G))で解くことができるようなcはないことを意味する。最後に,著者らは,JansenとNederlofのアルゴリズムを一般化して,それを用いて,あらゆるグラフHのためにLHom(H)を解決できた。その複雑性はctw(G)とHの別の不変量に依存し,クリークに対して一定である。【JST・京大機械翻訳】
