論文の概要: Structure-Aware Encodings of Argumentation Properties for Clique-width

• arxiv url: http://arxiv.org/abs/2511.10767v1
• Date: Thu, 13 Nov 2025 19:36:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-17 22:42:18.315575
• Title: Structure-Aware Encodings of Argumentation Properties for Clique-width
• Title（参考訳）: 斜め幅の係り受け特性の構造認識符号化
• Authors: Yasir Mahmood, Markus Hecher, Johanna Groven, Johannes K. Fichte,
• Abstract要約: コンパクトエンコーディングを (Q)SAT に分解し, 符号化限界を理解する。 アルゴリズムはclique-widthで利用できるが、エンコーディングについてはほとんど知られていない。 我々の減少は斜め幅を線形に保ち、直接分解誘導(DDG)の減少をもたらす。
• 参考スコア（独自算出の注目度）: 19.447613152899752
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Structural measures of graphs, such as treewidth, are central tools in computational complexity resulting in efficient algorithms when exploiting the parameter. It is even known that modern SAT solvers work efficiently on instances of small treewidth. Since these solvers are widely applied, research interests in compact encodings into (Q)SAT for solving and to understand encoding limitations. Even more general is the graph parameter clique-width, which unlike treewidth can be small for dense graphs. Although algorithms are available for clique-width, little is known about encodings. We initiate the quest to understand encoding capabilities with clique-width by considering abstract argumentation, which is a robust framework for reasoning with conflicting arguments. It is based on directed graphs and asks for computationally challenging properties, making it a natural candidate to study computational properties. We design novel reductions from argumentation problems to (Q)SAT. Our reductions linearly preserve the clique-width, resulting in directed decomposition-guided (DDG) reductions. We establish novel results for all argumentation semantics, including counting. Notably, the overhead caused by our DDG reductions cannot be significantly improved under reasonable assumptions.
• Abstract（参考訳）: 木幅のようなグラフの構造測度は、計算複雑性の中心的なツールであり、パラメータを利用する際に効率的なアルゴリズムをもたらす。 現代のSATソルバは、小さなツリー幅のインスタンスで効率的に動作することが知られている。 これらの解法は広く適用されているため、符号化制限の解決と理解のためにコンパクトな符号化を (Q)SAT に組み込むことに関心がある。 さらに一般的なグラフパラメータclique-widthは、高密度グラフでは木幅が小さくなる。 アルゴリズムはclique-widthで利用できるが、エンコーディングについてはほとんど知られていない。 我々は、矛盾する議論を推論するための堅牢な枠組みである抽象的議論を考慮し、クリプト幅で符号化能力を理解するための探求を開始した。 これは有向グラフに基づいており、計算に挑戦する性質を求めており、計算特性を研究する自然な候補となっている。 議論問題から(Q)SATへの新たな還元を設計する。 我々の減少は斜め幅を線形に保ち、直接分解誘導(DDG)の減少をもたらす。 カウントを含む全ての議論の意味論について、新しい結果を確立する。 特に、DDG削減によるオーバーヘッドは、合理的な仮定では著しく改善できない。

関連論文リスト

• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  大規模計算には量子エラー補正(QEC)が必要であるが、かなりのリソースオーバーヘッドが発生する。 近年の進歩により、論理ゲートからなるアルゴリズムにおいて論理キュービットを共同で復号化することにより、症候群抽出ラウンドの数を削減できることが示されている。 ここでは、回路を介して伝播する関連する論理演算子製品を直接復号することで、回路の復号化の問題を修正する。
  論文  参考訳（メタデータ） (2025-05-19T18:00:00Z)
• Extended Version of: On the Structural Hardness of Answer Set Programming: Can Structure Efficiently Confine the Power of Disjunctions? [21.10339925217772]
  プログラムのルール構造上での解離的ASPの構造パラメータの分類に対処する。 我々は、その範囲で最も顕著なパラメータに対して、二重指数下界を提供する。 本研究は, 通常のプログラムから解離プログラムへの新規な縮小に頼って, 深部硬度調査を行う。
  論文  参考訳（メタデータ） (2024-02-05T21:51:36Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Solving Projected Model Counting by Utilizing Treewidth and its Limits [23.81311815698799]
  予測モデルカウント(PMC)を解く新しいアルゴリズムを提案する。 いわゆる「ツリー幅」が最も顕著な構造パラメータの1つであるという観測から着想を得て,本アルゴリズムは入力インスタンスの一次グラフの小さなツリー幅を利用する。
  論文  参考訳（メタデータ） (2023-05-30T17:02:07Z)
• Treewidth-aware Reductions of Normal ASP to SAT -- Is Normal ASP Harder than SAT after All? [9.480212602202517]
  木幅を考えると、通常のASPのフラグメントはSATよりもわずかに難しいことが判明した。 本報告では, 通常のASPからSATへの新規な縮小について実証的研究を行い, 既知分解による木幅上界の比較を行った。
  論文  参考訳（メタデータ） (2022-10-07T13:40:07Z)
• Advanced Tools and Methods for Treewidth-Based Problem Solving -- Extended Abstract [9.480212602202517]
  この研究は、論理ベースの問題とツリー幅ベースの方法とそれを解決するツールに焦点を当てている。 本稿では,分解誘導(DG)による新しいタイプの問題削減について述べる。 木幅を直接利用して,Satの拡張を効率的に解くアルゴリズムを実装した。
  論文  参考訳（メタデータ） (2022-08-24T07:43:58Z)
• Neural network relief: a pruning algorithm based on neural activity [47.57448823030151]
  重要でない接続を非活性化する簡易な重要スコア計量を提案する。 MNIST上でのLeNetアーキテクチャの性能に匹敵する性能を実現する。 このアルゴリズムは、現在のハードウェアとソフトウェアの実装を考えるとき、FLOPを最小化するように設計されていない。
  論文  参考訳（メタデータ） (2021-09-22T15:33:49Z)
• An Information Theory-inspired Strategy for Automatic Network Pruning [97.03772272417599]
  深層畳み込みニューラルネットワークは、リソース制約のあるデバイスで圧縮されることがよく知られている。 既存のネットワークプルーニング手法の多くは、人的努力と禁忌な計算資源を必要とする。 本稿では,自動モデル圧縮のための情報理論に基づく戦略を提案する。
  論文  参考訳（メタデータ） (2021-08-19T07:03:22Z)
• Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results [58.277290855841976]
  グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。 新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。 いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
  論文  参考訳（メタデータ） (2020-12-06T03:42:54Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。