A new theoretical preprint reports that a logic for asking for minimum or maximum graph solutions can be handled with algorithms whose dependence on graph size is quadratic for bounded clique-width and linear for bounded treewidth.
But a related version in which optimality depends on an external set is stated to be hard at every fixed level of the polynomial hierarchy, even on trees of depth 4.
Putting minimum and maximum into the logic
The paper introduces AmCMSO, an extension of CMSO that adds Argmin and Argmax operations. These operations let the logic seek a set—or a tuple of sets—that minimizes or maximizes a value.
The formal domain is finite simple graphs. This is an algorithmic study rather than an empirical investigation, with no dataset or participants.
What the algorithms guarantee
For an n-vertex graph with clique-width cw, the paper states that an AmCMSO1 satisfying tuple can be found in time f(ϕ,cw)·n², where f is computable. The result is fixed-parameter tractable: the formula and width parameter are kept in the computable part of the bound, while graph size contributes a quadratic term.
For AmCMSO2 on graphs of treewidth tw, the stated runtime is f(ϕ,tw)·n. The framework extends the Feferman–Vaught theorem and uses dynamic programming on a decomposition tree, tracking ranks of sums of optimal values as graph components are combined.
A boundary around external-set questions
The harder result concerns 1-AmMSO model checking with an external-set-dependent optimality condition. For every fixed integer i≥1, the paper states that the problem is both ΣP_i-hard and ΠP_i-hard on trees of depth 4. These labels refer to levels in the polynomial hierarchy, a framework for classifying computational difficulty.
This is a worst-case statement about constructed instances, not a benchmark of typical performance. It also does not say that every formula involving an external set is hard; the stated theorem asserts the existence of hard formulas.
Several kinds of optimal solution
The framework is also applied to finding diverse optimal solutions. The SumHam result is fixed-parameter tractable when parameterized by the number of solutions r together with clique-width, and the paper says it covers several weighted graph-optimization problems. For MinHam, the stated runtime for r≥3 is g(r,cw,|ϕ|)·O(n^(r²)).
Other formal applications include Most Vital Nodes of δ-approximate CMSO solutions, which is fixed-parameter tractable in the stated width, approximation-gap and formula-size parameters. Minimum and maximum unique-optimum preassignment are fixed-parameter tractable by clique-width for CMSO1 and by treewidth for CMSO2.
A cardinality-constrained CMSO problem is given a runtime of g(cw,|ϕ|)n^(2k+1), with the exponent depending on the number k of set variables.
A complexity result, not a benchmark
The preprint does not report an implementation study, benchmark or real-world validation. Its runtime bounds leave the computable functions and practical constants unspecified, and the detailed clique-width algorithm assumes that a suitable clique-width expression or related decomposition is available.
The work is an arXiv preprint, version 1, dated 20 August 2026. No journal venue or funding statement is listed in the supplied record.
Paper data and sources
Original title: Quantifying over Optimal MSO-Definable Sets on Graphs of Bounded Clique-Width
Authors: Tatsuya Gima
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text