| paper | d4-conf-ijcai-2011-0269 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard for every fixed \(\varepsilon>0\) and every \(\sigma\in\{\mathrm{ADM},\mathrm{COM},\mathrm{PRF},\mathrm{SEM},\mathrm{STB}\}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4(1)
For fixed \(\varepsilon>0\) and \(\sigma\in\{\mathrm{ADM},\mathrm{COM},\mathrm{PRF},\mathrm{SEM},\mathrm{STB}\}\), an instance is a finite supported type set \(T\), a directed attack relation \(R\subseteq T\times T\), positive rational masses \(\mu_t\) summing to one, and a target type \(t^\star\). Each type occupies a measurable interval \(I_t\) of mass \(\mu_t\), with occurrences attacking according to \(R\); extensions obey the measurable lift of the paper's Dung semantics. Promise that some single type \(b\) has \(T\setminus\{b\}\) bipartite and \(\mu_b\le\varepsilon\). Decide whether a \(\sigma\)-extension contains positive mass of \(t^\star\).
Types are recurring argument roles, with mass \(\mu_t\) represented by occurrences in \(I_t\); the type-level relation \(R\) determines attacks between occurrences. The decision variable is a measurable extension \(S\), and acceptance asks whether \(\lambda(S\cap I_{t^\star})>0\); there is no optimization objective.
Support types can encode one-off formula gadgets, so the repeated-role interpretation is plausible only in application regimes where argument roles genuinely recur; the consultation example narrows but does not eliminate that concern.
fatal: False
The selected mirror covers Theorem 4(1), the NP-hardness of credulous acceptance near bipartite frameworks; Theorem 1 supplies a separate surviving FPT mirror. It leaves the other hardness results, the noeven results, and the structural comparisons untreated.
The strongest mirror I can defend is narrow: large argumentation settings with many occurrences of a small number of recurring argument roles. An occurrence’s type records its attack behavior toward every other type. Let \(T\) be the supported types, with rational masses \(\mu_t>0\) summing to \(1\), and let \(R\subseteq T\times T\) be the attack relation. Partition \([0,1)\) into intervals \(I_t\) of lengths \(\mu_t\); an occurrence in \(I_t\) attacks one in \(I_u\) exactly when \((t,u)\in R\). An extension is a measurable set of occurrences, and the paper’s semantics lift pointwise to this continuum: conflict-free, defended, complete, preferred, semi-stable, and stable have their usual definitions. A target type is credulously accepted if some extension contains positive mass of it, and skeptically accepted if every extension contains it up to measure zero. For credulous acceptance, a witness is such an extension; the problem asks for a yes/no answer.
This describes, for example, a large consultation in which many submissions instantiate recurring argument roles with the same attack relations. The regime can have \(N=q\tau\) occurrences for arbitrarily large \(q\), while the support has only \(\tau=|T|\) types. The attacks are homogeneous within and between types. Under these lifted semantics, accepted blocks are saturated up to measure zero, so the continuum problem corresponds exactly to acceptance in the support graph. That correspondence is a result of the mirror, not a reason to pretend its population mass changes the answer.
My lead is the hardness anchor, Theorem 4(1), proved in the paper by a reduction whose details are sketched. It states that for AFs \(F\) with \(\bsdist_{\BIP}(F)=1\), \(\CA_\sigma\) is NP-hard for every \(\sigma\in\{\ADM,\COM,\PRF,\SEM,\STB\}\).
The corresponding continuous problem is Mass Credulous Acceptance near Bipartite. Its instance is \((T,R,\mu,t^\star,\sigma)\), where \(\mu\) is a rational mass distribution, \(t^\star\) is a target type, and \(\sigma\) is one of those five semantics. Promise that deleting one type makes the support attack graph bipartite, and that the minimum mass of a type set whose deletion makes it bipartite is at most a fixed \(\varepsilon>0\). Ask whether some \(\sigma\)-extension contains positive mass of \(t^\star\). This is NP-hard for every fixed \(\varepsilon>0\): lift each hard AF from Theorem 4(1), assign a bipartizing type mass below \(\varepsilon\), and distribute the remaining mass positively over the other types. The support graph and acceptance answer are unchanged. The expected direction is Class B: hardness transfers. The reduction’s combinatorics remain in the attack graph over types, even if the exceptional type has arbitrarily small mass. It also raises a useful follow-up: which results hold when distance is measured by mass rather than by the number of types?
A second, algorithmic anchor is Theorem 1, proved in the paper. It states that both \(\CA_\sigma\) and \(\SA_\sigma\) are fixed-parameter tractable in \(\bsdist_{\ACYC}\) for all five semantics \(\sigma\in\{\ADM,\COM,\PRF,\SEM,\STB\}\). Its mirror, Mass Acceptance near Acyclicity, uses the same typed continuum and asks either acceptance question, parameterized by the minimum number \(k\) of support types whose deletion makes the support attack graph acyclic. The expected direction is Class A, with running time \(f(k)\operatorname{poly}(\tau,L)\), where \(L\) includes the masses’ encoding length. The paper’s FPT argument works on the quotient: detecting an acyclic backdoor is directed feedback vertex set, and evaluating it uses the backdoor. A natural further question is whether any useful bound survives if \(k\) is replaced by the removed mass.
I expect the authors to recognize both questions as their acceptance problems on a continuum of repeated, type-homogeneous argument occurrences: the target, extensions, and semantics retain their meaning, and the support graph preserves the attack structure they study. This covers those acceptance results, not every result in the paper or every kind of argumentation framework.
The weak point is substantial: argument occurrences are not ordinarily a population of voters, and exact duplicates often add no force under Dung semantics. Here the masses are inert and the quotient does the computational work. So this is a credible high-multiplicity mirror only for settings where recurring argument roles are plausible; it is not a claim that continuous population semantics naturally fits arbitrary AFs.
The paper clearly has computational results to mirror: Theorems 1 and 4(1) are explicit complexity anchors. The strongest case against rests on what counts as a type here. An argument’s attack behaviour is defined by its relations to the other arguments in the instance. In a generic framework, describing an argument’s type therefore requires its place in that graph, and most arguments will have distinct types. Unlike voter rankings from a fixed type space, these types are made by the instance’s combinatorics.
For Theorem 4(1), the proposed construction assigns a type to each argument in the hardness instance. The formula and its gadgets remain encoded in the support graph. Replicating each type many times creates a larger graph, but Dung acceptance depends on whether attackers and defenders exist, not on how much mass they carry. Under the proposed lifted semantics, the copies collapse back to the support graph. Giving the bipartizing type arbitrarily small mass makes the mass-distance promise hold, yet leaves the entire hardness instance in place. That establishes a formal weighted variant; it does not give the exceptional mass a natural meaning in the acceptance problem. If arguments are repeated submissions, their frequency still does no work under these semantics, and deduplicating them recovers the original AF.
Theorem 1 has the same problem. Its parameter is the number of arguments whose deletion makes the framework acyclic. In the proposed mirror, that becomes the number of support types deleted, and the algorithm runs on the support graph. The population mass is unused. Replacing the parameter with deleted mass would ask a different question about the weight of a feedback set; it would still leave credulous and skeptical acceptance determined by the support graph. Moreover, assigning tiny masses to the types that encode cycles can make that weight small without simplifying the acceptance instance. The result is a graph parameter with attached weights, not a population-level version of the paper’s acceptance problem.
This is a modeling objection, not the claim that an unchanged answer makes a mirror uninteresting. Here the population coordinate has no role in either the semantics or the computational input once the support graph is known. To make proportions affect acceptance, one would need a new notion of attack or defense based on thresholds or aggregate mass. That could be a worthwhile study of weighted or collective argumentation, but the paper’s Dung semantics supply no natural threshold to continuize, and such a change would alter the problem the authors studied.
The negative case has a real limit: one can imagine a domain where many sources submit arguments from a small set of recurring roles, and the authors might find the exact blow-up construction useful as a duplication-invariance result. But that scenario makes multiplicity semantically inert under the paper’s definitions. On the evidence here, neither anchor yields a continuous-population question the authors are likely to recognize as their acceptance problem.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.