Answer: polynomial-time solvable
Theorem 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIf the dependency graph of every voter has max- imum in-degree at most 1 and the undirected version of the global dependency graph has treewidth at most 2, then CMS is optimally solvable in polynomial time4.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) binary issues and a distribution \(\mu\) over \(\tau\) complete conditional approval ballot types, with rational masses summing to \(1\), suppose each supported type has maximum dependency in-degree at most \(1\) and the undirected union of their dependency graphs has treewidth at most \(2\). Find an assignment \(s\in\{0,1\}^m\) minimizing \(\sum_t \mu_t\delta_t(s)\), where \(\delta_t(s)\) is the number of issues on which type \(t\) is dissatisfied.
There are \(m\geq 1\) binary issues. A ballot type \(t\) specifies a loopless directed dependency graph \(G_t\) on the issues, with maximum in-degree at most \(1\); directed cycles are allowed. Write \(P_{t,j}\) for the predecessors of issue \(j\).
For every issue \(j\) and every assignment \(a\in\{0,1\}^{P_{t,j}}\), the type explicitly specifies an approval set \(A_{t,j}(a)\subseteq\{0,1\}\). Empty approval sets and approval of both values are allowed; if \(P_{t,j}\) is empty, there is one unconditional approval set.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass \(\mu_t\) as a binary rational, where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
The undirected graph obtained by taking the union of all supported dependency graphs and forgetting edge orientations has treewidth at most \(2\).
For a common assignment \(s\in\{0,1\}^m\), define \(\delta_t(s)=|\{j:s_j\notin A_{t,j}(s|_{P_{t,j}})\}|\). The optimization problem is to return any assignment minimizing \(\sum_t\mu_t\delta_t(s)\); ties may be resolved arbitrarily.
Is computing such a minimizing assignment solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finite unweighted electorates under these same graph restrictions, Conditional Minisum is exactly solvable in polynomial time (Markakis and Papasotiropoulos, 2020). The stated discrete result does not explicitly classify the formulation with support-encoded rational masses.
Computing a minimizing assignment is polynomial-time solvable in \(m,\tau,L\), including when the dependency graphs contain directed cycles and the masses are support-encoded binary rationals.
The unweighted result appears as Theorem 3 of [Markakis and Papasotiropoulos (2020)](https://www.ijcai.org/proceedings/2020/0043.pdf). The proof below directly handles rational masses and gives an explicit polynomial bit-complexity bound.
Let \(V=\{1,\ldots,m\}\), and let \(H\) be the undirected union of the supported dependency graphs. By hypothesis, \(H\) has treewidth at most \(2\).
For each supported type \(t\) and issue \(j\), define a dissatisfaction indicator \(d_{t,j}\).
The in-degree bound ensures that these are all cases. Thus every term involves either one issue or two issues joined by an edge of \(H\), and
\(\displaystyle F(s):=\sum_{t=1}^{\tau}\mu_t\delta_t(s)=\sum_{t=1}^{\tau}\sum_{j=1}^{m}\mu_t d_{t,j}\bigl(s|_{P_{t,j}\cup\{j\}}\bigr).\)
Empty approval sets and approval of both values simply produce valid indicator tables. Directed cycles cause no difficulty: every indicator is evaluated on the common assignment \(s\), without requiring a sequential evaluation of issues.
Write each mass as \(\mu_t=p_t/q_t\), with positive integers \(p_t,q_t\). Reduction to lowest terms is unnecessary. Define
\(\displaystyle D=\prod_{t=1}^{\tau}q_t,\qquad w_t=p_t(D/q_t).\)
Then \(w_t\) is a positive integer, \(\sum_t w_t=D\), and
\(\displaystyle C(s):=D F(s)=\sum_{t=1}^{\tau}\sum_{j=1}^{m}w_t d_{t,j}\bigl(s|_{P_{t,j}\cup\{j\}}\bigr).\)
Since \(D>0\), the minimizing assignments of \(C\) and \(F\) coincide.
The sum of the encoded denominator lengths is at most \(L\), so \(D\) has at most \(L+1\) bits. Furthermore, \(w_t\leq D\), because the positive masses sum to \(1\). Consequently,
\(\displaystyle 0\leq C(s)\leq mD.\)
Aggregate all contributions with the same scope into one table. This gives a representation
\(\displaystyle C(s)=\sum_{j\in V}U_j(s_j)+\sum_{\{i,j\}\in E(H)}Q_{ij}(s_i,s_j),\)
where each unary table has two entries and each binary table has four entries. When contributions use opposite edge orientations, their arguments are reordered into the same fixed vertex order before aggregation.
Thus the problem is exact minimization of a sum of integer unary and binary tables on \(H\).
We prove that the promised graph permits the following greedy procedure: repeatedly choose a vertex of degree at most \(2\), join its two neighbors if necessary, and delete the vertex.
A tree decomposition consists of a tree of vertex bags such that every vertex occurs in a bag, every edge has both endpoints in some bag, and the bags containing any fixed vertex form a connected subtree. Its width is the largest bag size minus one.
Lemma 1. Every nonempty graph of treewidth at most \(2\) has a vertex of degree at most \(2\).
Proof. Take a tree decomposition whose bags have size at most \(3\). Repeatedly remove any leaf bag contained in its neighboring bag. This preserves the decomposition properties.
If only one bag remains, the graph has at most three vertices, so every vertex has degree at most \(2\).
Otherwise, choose a leaf bag \(B\) with neighboring bag \(B'\). Since \(B\not\subseteq B'\), choose \(v\in B\setminus B'\). The connectedness condition implies that \(v\) occurs only in \(B\). Every neighbor of \(v\) must therefore belong to \(B\), by the edge-covering condition. Hence \(\deg(v)\leq |B|-1\leq2\). \(\square\)
Lemma 2. Deleting a vertex of degree at most \(2\) and joining its two neighbors, if it has two, preserves treewidth at most \(2\).
Proof. For degree zero or one, the operation is vertex deletion.
If \(v\) has exactly two neighbors \(a,b\), the resulting graph is obtained by contracting the edge \(va\): contraction deletes \(v\), identifies it with \(a\), and adds precisely the potentially missing edge \(ab\).
For completeness, neither deletion nor contraction increases treewidth. Deletion is implemented by removing the deleted vertex from every bag. For contraction of an edge \(xy\), replace \(x,y\) by the merged vertex in every bag. Bag sizes do not increase. The bags containing the merged vertex are connected because the subtrees for \(x\) and \(y\) intersect in a bag covering \(xy\). Vertex and edge coverage are preserved. \(\square\)
Together, the lemmas show that greedy elimination always succeeds. Let its order be \(v_1,\ldots,v_m\), and let \(N_i\) be the neighbors of \(v_i\) immediately before its elimination. Then \(|N_i|\leq2\), and every vertex in \(N_i\) occurs later in the order.
An adjacency-matrix implementation can construct this order using \(O(m^3)\) elementary graph operations by recomputing degrees at each step.
Maintain a constant and unary or binary tables on the remaining variables. Every binary table has its scope on an edge of the current elimination graph.
When eliminating \(v_i\), let \(\mathcal F_i\) be the current tables whose scopes contain \(v_i\). Every other variable appearing in these tables belongs to \(N_i\). For each assignment \(a\in\{0,1\}^{N_i}\), calculate
\(\displaystyle h_i(a)=\min_{b\in\{0,1\}}\sum_{f\in\mathcal F_i}f\bigl((b,a)|_{\operatorname{scope}(f)}\bigr).\)
Here \((b,a)\) assigns value \(b\) to \(v_i\) and assigns the values specified by \(a\) to \(N_i\). Store one minimizing value \(b_i(a)\), choosing either value in a tie.
Remove the tables in \(\mathcal F_i\) and insert \(h_i\), merging it with an existing table of the same scope if necessary. If \(N_i=\varnothing\), add \(h_i\) to the maintained constant.
Because \(|N_i|\leq2\), the new table has at most four entries. If its scope has two vertices, the fill operation has joined those vertices, preserving the graph invariant.
Correctness invariant. After eliminating \(v_1,\ldots,v_{i-1}\), the maintained function on the remaining variables equals the minimum of the original \(C\) over those eliminated variables.
This is true initially. For the inductive step, fix an assignment of all remaining variables other than \(v_i\). Tables outside \(\mathcal F_i\) do not depend on \(v_i\), so
\(\displaystyle \min_{s_{v_i}}\left(\sum_{f\notin\mathcal F_i}f+\sum_{f\in\mathcal F_i}f\right)=\sum_{f\notin\mathcal F_i}f+h_i.\)
This is exactly the replacement performed by the algorithm, proving the invariant. Once all variables have been eliminated, the remaining constant is therefore \(\min_s C(s)\).
To recover an assignment, process the vertices in reverse order. When processing \(v_i\), every vertex in \(N_i\) has already received a value. Set
\(\displaystyle s_{v_i}=b_i(s|_{N_i}).\)
Each stored choice attains the corresponding elimination minimum. Reversing the elimination equalities therefore gives \(C(s)=\min_x C(x)\). This assignment also minimizes \(F\).
It remains to bound the sizes of intermediate integers.
Initially, the sum of the maximum entries of all tables is at most
\(\displaystyle \sum_{t=1}^{\tau}\sum_{j=1}^{m}w_t=mD.\)
Aggregation preserves this bound because the maximum of a sum is at most the sum of the maxima. During elimination,
\(\displaystyle \max_a h_i(a)\leq\sum_{f\in\mathcal F_i}\max_x f(x).\)
Hence replacing the consumed tables by \(h_i\), and merging tables, cannot increase the sum of their maximum entries, including the maintained constant. All entries are nonnegative. Every intermediate integer is consequently at most \(mD\).
Set \(B=L+\lceil\log_2(m+1)\rceil+3\). Every cost entry and arithmetic operand can be stored with \(O(B)\) bits.
Using elementary integer arithmetic:
A valid overall running-time bound is thus
\(\displaystyle O\!\left((m^3+m\tau+\tau)\bigl(L+\log_2(m+1)+3\bigr)^2\right).\)
The algorithm works directly with the \(\tau\) supported types. Although \(D\) may have exponentially large numerical value, it has only polynomially many bits, and no expansion into an unweighted electorate is needed.
Therefore the stated support-encoded rational-mass optimization problem admits an exact polynomial-time algorithm.
⟨structured verdict parsed — rendered above⟩
The output fully resolves the assigned problem. Its algorithm and bit-complexity analysis are correct; I found no major or minor gaps requiring repair.
Maximum in-degree at most \(1\) and looplessness ensure that every dissatisfaction indicator depends on either one variable or two distinct variables. Each binary scope is an edge of the undirected union graph \(H\).
The indicator definitions exactly match the task’s dissatisfaction rule, so the displayed expression for \(F(s)\) is correct. Empty approval sets give indicators identically equal to \(1\); approval of both values gives indicators identically equal to \(0\). Directed cycles introduce no ambiguity because all indicators are evaluated on a complete assignment, without sequential evaluation.
Positive support masses admit representations \(\mu_t=p_t/q_t\) with positive integer numerators and denominators. The product \(D=\prod_t q_t\) is positive, and every quotient \(D/q_t\) is an integer. Thus the weights \(w_t=p_t(D/q_t)\) are positive integers.
The normalization \(\sum_t\mu_t=1\) implies \(\sum_t w_t=D\), hence \(w_t\leq D\). Multiplication of the objective by \(D>0\) preserves all minimizing assignments.
The denominator-length bound is valid: the logarithm of their product is at most the sum of their encoded bit lengths. Consequently, the asserted \(L+1\) bound on the bit length of \(D\) is conservative. The bound \(0\leq C(s)\leq mD\) follows from the indicator values and \(\sum_t w_t=D\).
Aggregating contributions by scope preserves the objective. Reordering arguments for opposite orientations correctly handles dependencies in both directions.
Lemma 1: Removing a leaf bag contained in its neighboring bag preserves vertex coverage, edge coverage, and the connectedness condition. Once such removals stop, either one bag remains or a leaf bag contains a vertex absent from its neighboring bag. In the latter case, connectedness forces that vertex to occur only in the leaf bag. Edge coverage then places every neighbor in that bag, giving degree at most \(2\). The single-bag case is also valid.
Lemma 2: For degree \(0\) or \(1\), the operation is vertex deletion. For degree \(2\), contracting the edge from the eliminated vertex to one neighbor produces exactly the required remaining graph, with the potentially missing edge between its two neighbors added. This assertion uses the fact that the eliminated vertex has no other neighbors.
The supplied bag modifications correctly establish that deletion and contraction do not increase treewidth. In the contraction case, the two occurrence subtrees intersect because a bag covers the contracted edge, so their union is connected.
These lemmas justify choosing any currently available vertex of degree at most \(2\). The promise is preserved after each operation, so elimination cannot become stuck. Recomputing degrees with an adjacency matrix supports the stated \(O(m^3)\) graph-operation bound.
Initially, all binary tables lie on edges of \(H\). At an elimination step, every variable sharing a table with \(v_i\) therefore belongs to its current neighborhood \(N_i\).
Because \(|N_i|\leq2\), the replacement table \(h_i\) has at most four entries. Its scope is supported by the fill edge when necessary. Merging tables with identical scopes preserves the represented function.
For a fixed assignment of the other remaining variables, every table outside \(\mathcal F_i\), together with the maintained constant, is independent of \(v_i\). The displayed minimization identity therefore proves the stated invariant. Iterating it leaves exactly the global minimum as the final constant.
The construction also covers an isolated variable with no incident tables: its local sum is empty, both values minimize it, and its contribution is zero.
Every vertex in \(N_i\) occurs later in the elimination order, so its value is available during reverse reconstruction. The stored value \(b_i(a)\) attains the local minimum for every neighborhood assignment \(a\).
Consequently, each reconstructed choice attains the corresponding elimination equality, and the recovered complete assignment attains the final minimum. Arbitrary tie-breaking is permitted by the task. The argument also covers disconnected graphs, isolated vertices, and \(m=1\).
Before aggregation, the sum of table maxima is at most \(mD\). Aggregation cannot increase that sum.
At each elimination, the maximum entry of \(h_i\) is at most the sum of the maxima of the consumed tables. The same bound remains valid when a scalar contribution is added to the constant. Since all entries remain nonnegative, every table entry, constant, and partial cost sum is bounded by \(mD\).
The chosen \(B=L+\lceil\log_2(m+1)\rceil+3\) therefore suffices for cost arithmetic. It also bounds the integers used to compute \(D\) and the weights. Elementary multiplication and division support the stated \(O(\tau B^2)\) preprocessing bound.
After aggregation, an eliminated vertex has at most one unary table and two incident binary tables. Its numerical elimination and storage of minimizing choices require only constantly many operations on bounded-length integers. The graph bookkeeping and input-table aggregation fit within the conservative overall bound
\[
O\!\left((m^3+m\tau+\tau)\bigl(L+\log_2(m+1)+3\bigr)^2\right).
\]
Thus the algorithm is polynomial in the requested parameters and never expands the rational masses into individual voters.
The cited [Theorem 3 of Markakis and Papasotiropoulos (2020)](https://www.ijcai.org/proceedings/2020/0043.pdf) states polynomial-time optimal solvability for unweighted Conditional Minisum under the specified in-degree and union-treewidth restrictions. The prover supplies an independent argument for rational support masses, so it does not assume an unstated weighted extension of that theorem.
Actionable feedback: No repair or additional clarification is required. The polynomial-time classification and the explicit running-time bound stand as written.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.