概要 - 分数的および拡張したハイパートリewidthのFPTパラメタ化
タイトル
分数的および拡張したハイパートリewidthのFPTパラメタ化
時間
2025-07-15 08:23:01
著者
{"Matthias Lanzinger","Igor Razgon","Daniel Unterberger"}
カテゴリ
{cs.DS,cs.CC}
リンク
http://arxiv.org/abs/2507.11080v1
PDF リンク
http://arxiv.org/pdf/2507.11080v1
概要
この論文では、一般化されたハイパートリewidth（ghw）や分数的なハイパートリewidth（fhw）を含むいくつかの中心的なハイパーグラフ分解パラメータを正確に決定するための初めての固定パラメータトラクタブル（FPT）アルゴリズムを提案しています。これらのパラメータは複雑性理論、データベース、制約満足において認知されている重要性にもかかわらず、これまでその正確なFPTアルゴリズムは知られていませんでした。 著者たちは、有限なランクと度数を持つハイパーグラフクラスに対して結果を得ています。彼らのアプローチは、モナド第二階（MSO）トランズデューションを使用した最近のトライエッジ幅（Bojańcyk & Pilipczuk、LMCS 2022）のアルゴリズムを拡張しており、このフレームワークは、構造分解がグラフの対比よりも複雑なハイパーグラフの技術的な技術的な障害を克服することができます。 論文の主な貢献は以下の通りです： 1. **管理可能な幅関数の定義**：著者たちは、トライエッジ幅に使用される伝統的な幅関数よりも一般的な新しい幅関数クラス、管理可能な幅関数を定義しました。これにより、彼らのアルゴリズムをより広範なハイパーグラフ幅測定値に適用することができます。 2. **トライエッジ幅アルゴリズムの一般化**：著者たちは、BojańczykとPilipczukのトライエッジ幅アルゴリズムを一般化したハイパーグラフパラメータのフレームワークに拡張しました。これにより、ghwやfhwにアルゴリズムを適用することができます。 3. **トランズデューションの構築**：著者たちは、木分解と最適な排除林を関連付けるMSOトランズデューションを構築しました。これにより、ハイパーグラフのf幅を確認することができます。 4. **ghwとfhwのチェックアルゴリズム**：著者たちは、有限なランクと度数を持つハイパーグラフに対してghwとfhwをチェックするためのFPTアルゴリズムを提案しました。 著者たちは、彼らの結果がハイパーグラフの研究とそのさまざまな分野への適用に大きな影響を与えると信じています。彼らはまた、アルゴリズムから度数制約を取り除く可能性を含むいくつかの未解決問題について議論しています。
推奨論文
TyDi QA-WANA: 西アと北アフリカの言語における情報探索型質問応答のための基準
「確証可能に修正可能なエージェントのための基本的安全価値」
デ・モルگان基底におけるブール関数の正確な表現と近似表現
DENSE: 病院訪問を横断する多様な臨床記録の時系列モデリングを用いた長期的な進捗ノート生成
SpiNNaker2神経モーフィックMPSoCのためのエンドツーエンドDNN推論フレームワーク
引っ越し：物理的に基づく人間-AIの協力
「デュアル戦略統合による需要予測のためのベースモデル」
多変量金融時系列予測のための時系列基盤モデル
CCL25-Evalタスク10用システムレポート：微細な中国語のヘイトスピーチ認識のためのSRAG-MAV
細胞無しのマスive MIMOシステムにおけるハイブリッド量子卷積神経網補助のパイロットアサインメント