Structure-Aware Encodings of Argumentation Properties for Clique-width¶

会议: AAAI 2026
arXiv: 2511.10767
作者: Yasir Mahmood (Paderborn University), Markus Hecher (CNRS/University of Artois), Johanna Groven (Linköping University), Johannes K. Fichte (Linköping University) 代码: 未公开
领域: others
关键词: 抽象论辩, 团宽, 参数化复杂性, SAT编码, QBF, k-表达式, 分解引导归约

一句话总结¶

本文设计了从抽象论辩问题到(Q)SAT的有向分解引导(DDG)归约，线性保持团宽(clique-width)，为所有常见论辩语义（stable、admissible、complete、preferred、semi-stable、stage）在扩展存在性、论元接受性和计数问题上建立了以团宽为参数的可处理性上界，并证明了在ETH假设下这些归约的开销不可显著改进。

研究背景与动机¶

问题背景¶

抽象论辩(Abstract Argumentation)是知识表示与推理中的核心框架，基于有向图（论辩框架AF）描述论元间的攻击关系，并通过语义条件确定可接受的论元集合（扩展）。论辩问题的计算复杂性跨越P到多项式层级的第二层，使得利用结构参数实现高效求解成为重要研究方向。

树宽(treewidth)是最常用的图结构参数，已有大量基于树宽的论辩算法和分解引导归约。然而，团宽(clique-width)是比树宽更一般的参数：树宽受限意味着团宽受限，但反之不然——团宽可以在稠密图上仍然很小，而此时树宽必然很大。这使得团宽在处理包含大团或完全二部结构的攻击图时具有独特优势。

已有工作的不足¶

树宽方向已成熟：基于树宽的论辩分解引导归约和动态规划算法已有充分研究
团宽方向几乎空白：虽然Dvořák等人(2010)为preferred语义建立了基于团宽的动态规划算法，但关于结构引导归约到(Q)SAT，几乎没有理论结果
实践需求：现代SAT求解器在小团宽实例上高效运行（Fischer等2008），若能将论辩问题保持团宽地编码为(Q)SAT，即可直接利用这些求解器
缺少下界：此前没有关于论辩问题团宽下界的系统性结果

核心动机¶

填补抽象论辩在团宽参数下的理论空白：设计线性保持团宽的归约到(Q)SAT，使已有的SAT/QSAT团宽可处理性结果可直接用于论辩问题求解，同时建立匹配的ETH下界证明归约的结构最优性。

方法详解¶

核心概念：有向分解引导(DDG)归约¶

k-表达式与团宽：一个有向图\(G\)的有向团宽\(\mathsf{dcw}(G)\)是构造\(G\)所需的最小颜色数\(k\)，构造通过三种操作完成：(i)不相交并\(\oplus\)，(ii)重标记\(\rho_{c\to c'}\)，(iii)有向边引入\(\eta_{c,c'}\)（从颜色\(c\)到颜色\(c'\)的所有顶点添加有向边）。\(k\)-表达式可由解析树\(T\)表示。

DDG归约核心思想：沿\(k\)-表达式的解析树，为每个操作节点\(b\)和每种颜色\(c\)引入辅助布尔变量，通过公式传播论辩语义的关键信息（如"颜色\(c\)中是否有扩展成员"、"颜色\(c\)中的非扩展论元是否被击败"等）。

一阶语义编码（Stable/Admissible/Complete）¶

Stable扩展编码：使用两组变量沿解析树传播： - 扩展变量\(e_c^b\)：在操作\(b\)处，颜色\(c\)是否包含扩展成员（析取传播） - 击败变量\(d_c^b\)：在操作\(b\)处，颜色\(c\)中每个非扩展论元是否被扩展攻击（合取传播）

在初始节点为论元\(a\)设置\(e_c^b \leftrightarrow e_a\)，\(d_c^b \leftrightarrow e_c^b\)；在合并/重标记节点沿解析树传播；在边引入节点处理冲突自由（\(\neg e_c^b \vee \neg e_{c'}^b\)）和被击败更新（\(d_c^b \leftrightarrow d_c^{b'} \vee e_{c'}^b\)）；在根节点要求所有颜色被击败。

Admissible扩展编码：在扩展变量基础上增加攻击变量\(a_c^b\)，记录是否有非扩展论元攻击扩展论元而未被反击。边引入操作中根据攻击方向区分处理。

Complete扩展编码：在admissible基础上增加"出局"变量\(o_c^b\)和"被击败\(\geq b\)"变量\(d_c^{\geq b}\)（从根向叶反向传播），确保没有论元被不当排除在扩展之外。

二阶语义编码（Preferred/Semi-stable/Stage）¶

关键辅助引理（Lemma 14）：当QBF最内层量词为\(\forall\)且矩阵为\(\varphi_{\text{CNF}} \wedge \psi_{\text{DNF}}\)混合形式时，可将其转换为纯DNF矩阵，且线性保持有向入射团宽。此引理大幅简化了二阶语义的编码。

Preferred扩展：构造QBF \(\varphi_{\#\mathsf{adm}} \wedge \neg(\exists E^*, A^*, S.\, \varphi_{\mathsf{pref}})\)，其中星号变量编码候选的严格超集扩展。利用Lemma 14将矩阵转为标准形式，归约到\(\#2\text{-QBF}\)。

Semi-stable扩展：最大化扩展的范围(range)，构造QBF \(\varphi_{\#\mathsf{adm}} \wedge (\forall E^*, D^*, A^*, S.\, \neg\varphi_{\mathsf{semiSt}})\)。

Stage扩展：基于冲突自由集最大化范围，构造QBF \(\forall E^*, D^*, S.\, (\varphi_{\#\mathsf{conf}} \wedge \neg\varphi_{\mathsf{stage}})\)。

ETH下界证明¶

通过从3SAT构造团宽感知归约到admissible扩展的credulous接受问题，证明\(2^{o(w)} \cdot \text{poly}(n)\)的运行时间在ETH下不可实现。该下界自然推广到stable/complete（一阶）和preferred/semi-stable/stage（二阶，\(2^{2^{o(w)}}\)下界）。

实验关键数据¶

表1：各语义的DDG归约结果总览¶

语义 \(\sigma\)	团宽增长 (CW-Aw.)	ETH团宽下界	运行时间上界	运行时间ETH下界
\(\mathsf{stab}\)	\(\mathcal{O}(k)\)	\(\Omega(k)\)	\(2^{\Theta(k)} \cdot \text{poly}(n)\)	\(2^{\Theta(k)} \cdot \text{poly}(n)\)
\(\mathsf{adm}\)	\(\mathcal{O}(k)\)	\(\Omega(k)\)	\(2^{\Theta(k)} \cdot \text{poly}(n)\)	\(2^{\Theta(k)} \cdot \text{poly}(n)\)
\(\mathsf{comp}\)	\(\mathcal{O}(k)\)	\(\Omega(k)\)	\(2^{\Theta(k)} \cdot \text{poly}(n)\)	\(2^{\Theta(k)} \cdot \text{poly}(n)\)
\(\mathsf{pref}\)	\(\mathcal{O}(k)\)	\(\Omega(k)\)	\(2^{2^{\Theta(k)}} \cdot \text{poly}(n)\)	\(2^{2^{\Theta(k)}} \cdot \text{poly}(n)\)
\(\mathsf{semiSt}\)	\(\mathcal{O}(k)\)	\(\Omega(k)\)	\(2^{2^{\Theta(k)}} \cdot \text{poly}(n)\)	\(2^{2^{\Theta(k)}} \cdot \text{poly}(n)\)
\(\mathsf{stage}\)	\(\mathcal{O}(k)\)	\(\Omega(k)\)	\(2^{2^{\Theta(k)}} \cdot \text{poly}(n)\)	\(2^{2^{\Theta(k)}} \cdot \text{poly}(n)\)

其中 \(k = \mathsf{dcw}(\mathcal{G}_i^d(F))\)，\(n = |A|\)。所有DDG归约线性保持团宽，上下界在\(k\)的指数级别上匹配，证明了归约的结构最优性。结果统一覆盖扩展存在性\(\mathsf{exist}_\sigma\)、怀疑接受\(\mathsf{s}_\sigma\)、轻信接受\(\mathsf{c}_\sigma\)和计数\(\#_\sigma\)。

表2：与树宽参数结果的定位对比¶

结构参数	适用图类型	一阶语义运行时间	二阶语义运行时间	编码保持性
树宽 tw	稀疏图	\(2^{\mathcal{O}(\text{tw})} \cdot \text{poly}(n)\)	\(2^{2^{\mathcal{O}(\text{tw})}} \cdot \text{poly}(n)\)	线性保持树宽
有向团宽 dcw（本文）	稀疏+稠密图	\(2^{\mathcal{O}(\text{dcw})} \cdot \text{poly}(n)\)	\(2^{2^{\mathcal{O}(\text{dcw})}} \cdot \text{poly}(n)\)	线性保持团宽
无向团宽 cw	—	SAT不可处理	—	不适用（硬度已知）

团宽严格推广树宽，使得本文结果可处理包含大团或完全二部结构的攻击图，这些情况下树宽方法完全失效。值得注意的是，无向团宽下SAT已知不可处理，因此有向入射团宽是正确的参数选择。

亮点¶

全面性：首次为所有六种常见论辩语义（stable/admissible/complete/preferred/semi-stable/stage）在团宽参数下统一建立编码和复杂性结果，涵盖扩展存在性、论元接受性和计数三类问题
结构最优性：不仅给出上界，还通过ETH下界证明DDG归约的开销（团宽从\(k\)到\(\mathcal{O}(k)\)的线性增长）在合理假设下不可显著改进，实现了紧的上下界匹配
技术创新：Lemma 14提出了在保持团宽的前提下将混合CNF/DNF矩阵转换为纯DNF/CNF的方法，是处理二阶（最大化）语义的关键工具，具有独立价值
实际意义：使现代SAT/QBF求解器可直接用于小团宽的论辩实例求解，团宽适用于稠密图场景，弥补了树宽方法在稠密攻击图上的局限
有向vs无向的清晰论证：通过Example 9精妙地展示了为何必须使用有向团宽而非无向团宽——两个无向同构但有向不同的AF可以有完全不同的stable扩展数量

局限与展望¶

纯理论工作，缺乏实验验证：没有实现DDG归约并在实际SAT/QBF求解器上测试，无法评估在实际论辩实例上的表现
团宽计算本身困难：虽然理论上可在多项式时间内计算\(f(k)\)-表达式，但实践中团宽计算的\(f(k)\)因子极大，限制了实际应用
仅覆盖抽象论辩：未扩展到逻辑基论辩(logic-based argumentation)、演绎推理(abductive reasoning)、回答集编程(ASP)等相关KRR形式主义
编码规模：DDG归约产生的公式规模为\(\mathcal{O}(|T| \cdot k)\)（\(|T|\)为解析树大小），对于大型论辩框架可能产生较大的编码
未考虑枚举复杂性：归约保持解的双射对应，自然适合枚举问题，但论文未探索此方向
未涉及模块化树宽和对称入射团宽等正交参数

与相关工作的对比¶

Dvořák, Szeider, Woltran (2010)：首次为preferred语义在团宽下建立动态规划算法和可处理性结果，但未涉及编码到(Q)SAT或其他语义的系统性分析。本文全面覆盖所有语义并给出匹配下界
Hecher (2020), Fichte, Hecher, Mahmood (2021)：建立了基于树宽的分解引导归约，线性保持树宽。本文将此范式推广到严格更一般的团宽参数
Fischer, Makowsky, Ravve (2008)：证明了有向入射团宽\(k\)的CNF公式上#SAT可在\(2^{\mathcal{O}(k)} \cdot \text{poly}(n)\)时间解决，同时证明了无向团宽下SAT不可处理。本文DDG归约直接利用此正面结果
Capelli, Mengel (2019)：将SAT的团宽可处理性推广到QSAT。本文二阶语义的归约利用此结果获得\(2^{2^{\mathcal{O}(k)}}\)的运行时间
Niskanen, Järvisalo (2020)：常用的论辩SAT编码，但不考虑结构参数保持。本文编码的关键区别在于线性保持团宽
Lampis, Mengel, Mitsou (2018), Fichte, Hecher, Pfandler (2020)：QBF编码用于论辩问题的紧计算界，但在树宽框架下。本文在团宽框架下建立了类似结果

评分¶

新颖性: ⭐⭐⭐⭐⭐ — 首次系统解决论辩问题在团宽参数下的编码问题，开创DDG归约范式
实验充分度: ⭐⭐ — 纯理论贡献，无任何实验或实证评估
写作质量: ⭐⭐⭐⭐ — 结构严谨，定理体系完整，k-表达式示例有助理解，但符号密集对非专家不友好
价值: ⭐⭐⭐⭐ — 填补了论辩理论中团宽方向的重要空白，理论贡献扎实，但缺乏实践验证