Answer: Constrained stable-mass feasibility is in \(\mathrm P\). A complete description by distinct nonempty rational polyhedra can be computed in total time \((s+1)\operatorname{poly}(m,\tau,L)\), where \(s\) is the number output; the description may include contained faces.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm \ref{alg:ALLmain} correctly solves {\sc Reduced Constrained Stable Matchings} and does so in time $O(N^3 + N^3s)$. Moreover, the time between two consecutive stable matchings outputted by the algorithm is $O(N^3)$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite worker types \(W\) and position types \(F\), rational type masses and capacities, shared strict rankings over mutually acceptable types, and type-level assignment constraints, compute a finite union of rational polyhedra describing all stable mass assignments. Each assignment is a matrix \(x\ge 0\) with row and column sums bounded by the corresponding masses and capacities; forbidden pairs require \(x_{ij}=0\), while an in-constraint requires the whole specified type mass to be assigned within its permitted set. For each acceptable pair \((i,j)\), stability requires that either \(a_i-\sum_k x_{ik}+\sum_{k:\,j\succ_i k}x_{ik}=0\) or \(b_j-\sum_h x_{hj}+\sum_{h:\,i\succ_j h}x_{hj}=0\). Can this description be computed in time polynomial in the input encoding size plus polynomial work per output polyhedron?
Let \(W\) and \(F\) be nonempty finite sets of worker and position types, with \(m=|F|\). A society is given by its support: the list of its \(\tau=|W|+|F|\) types with positive binary-rational masses, where position masses are capacities; \(\tau\) counts listed types, not all possible types. Write worker masses as \(a_i\), position capacities as \(b_j\), and total input bit length as \(L\); totals need not equal each other or be normalized.
Each type has a strict ranking of a nonempty list of acceptable opposite-side types, shared by all its members; acceptability is mutual and preferred to remaining unmatched.
A mass assignment is \(x\in\mathbb R_{\geq0}^{W\times F}\), with \(\sum_jx_{ij}\leq a_i\), \(\sum_ix_{ij}\leq b_j\), and \(x_{ij}=0\) on unacceptable pairs. Worker- and position-side out-constraints also require their specified pairs to have zero mass.
A worker-side in-constraint with permitted set \(S_i\subseteq F\) requires \(\sum_{j\in S_i}x_{ij}=a_i\); a position-side in-constraint with permitted set \(T_j\subseteq W\) requires \(\sum_{i\in T_j}x_{ij}=b_j\). Both kinds of constraint may coexist.
Stability requires, for every acceptable pair \((i,j)\), \(a_i-\sum_kx_{ik}+\sum_{k:\,j\succ_i k}x_{ik}=0\) or \(b_j-\sum_hx_{hj}+\sum_{h:\,i\succ_j h}x_{hj}=0\), including acceptable pairs forbidden by constraints; \(\succ\) denotes strict preference.
The description sought is a finite list of distinct nonempty rational polyhedra in the assignment variables, given by binary-rational linear inequalities, whose union is exactly the constrained stable assignments; the empty list describes infeasibility. Each output polyhedron must have encoding length polynomial in \(m,\tau,L\); let \(s\) be the number output.
Is constrained stable-mass feasibility in \(\mathrm P\) or \(\mathrm{NP}\)-hard? Can the complete polyhedral description be computed in total time \((s+1)\operatorname{poly}(m,\tau,L)\)?
For discrete forced and forbidden pairs, feasibility and enumeration take \(O(N^3(1+s_d))\) total time with \(O(N^3)\) delay, where \(N\) is the larger number of workers and individual positions and \(s_d\) counts solutions ([Gutin–Neary–Yeo](https://arxiv.org/html/2204.03989v4)).
A single unconstrained bipartite stable allocation with divisible quantities can be computed in strongly polynomial time ([Dean–Munshi](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf)); this result does not establish constrained polyhedral enumeration.
Constrained stable-mass feasibility is in \(\mathrm P\). A complete polyhedral description can be computed in total time \((s+1)\operatorname{poly}(m,\tau,L)\).
The enumeration below outputs closures of feasible rotation cells, including their faces. These are distinct, nonempty polyhedra; some may be contained in others. The question does not require an irredundant or minimum-size description.
Let \(E\subseteq W\times F\) be the acceptable pairs, and write \(e=|E|\). Retain every edge of \(E\), including pairs forbidden by the assignment constraints.
For each acceptable pair, introduce the redundant edge capacity
\[ u_{ij}=\min(a_i,b_j). \]
These capacities do not change assignment feasibility. They also do not change stability: if \(x_{ij}=u_{ij}\), then at least one endpoint assigns its entire mass to the other endpoint, so that endpoint’s dissatisfaction expression is zero. If \(x_{ij}<u_{ij}\), the pair blocks precisely when both dissatisfaction expressions are positive.
For completeness, unequal totals and unmatched mass can be handled explicitly. Put \(A=\sum_i a_i\) and \(B=\sum_j b_j\). Add a dummy worker of mass \(B\) and a dummy position of capacity \(A\). Each original type ranks its dummy partner last; each dummy ranks the other dummy last. Give every added edge the capacity equal to the minimum of its endpoint quotas.
An original assignment has a unique extension satisfying all augmented row and column equalities:
\[ x_{i0}=a_i-\sum_jx_{ij},\qquad x_{0j}=b_j-\sum_ix_{ij},\qquad x_{00}=\sum_{i,j}x_{ij}. \]
No dummy edge can block: on each such edge, at least one endpoint ranks the other last and has no worse assignment. Thus extension and restriction give inverse bijections between original stable assignments and augmented stable allocations.
The augmented instance has \(\tau+2\) vertices and \(e+\tau+1\) edges.
We use the following published structural result, beyond the computation of a single allocation.
For a bipartite stable-allocation instance, one can compute a base allocation \(x^0\), a poset of \(k=O(e+\tau)\) rotations, positive multiplicities \(r_v\), and rotation directions \(\rho^v\), with entries in \(\{-1,0,1\}\). Stable allocations are represented bijectively by
\[ \Phi(y)=x^0+\sum_{v=1}^k y_v\rho^v, \]
where
\[ 0\leq y_v\leq r_v,\qquad p\prec q,\ y_q>0\ \Longrightarrow\ y_p=r_p. \]
The representation is computable in polynomial time. These are the rotation construction and correspondence in Section 4, particularly Lemmas 10–12, of [Dean–Munshi](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf).
Restrict \(x^0\) and the directions to the original assignment coordinates. The representation remains bijective, because the dummy extension is unique.
Let \(\mathcal C\) denote the displayed domain of rotation vectors. A vector in \(\mathcal C\) will be called *closed*. The hypotheses of the cited result hold: the instance is bipartite, preferences are strict, and all quotas and edge capacities are rational.
The construction also has polynomial bit complexity here. After scaling by a common denominator of polynomial bit length, its arithmetic uses integer additions, subtractions, comparisons, and minima. Its polynomial number of operations therefore produces data of polynomial bit length.
Let \(E_{\mathrm{out}}\) be the union of the worker-side and position-side forbidden acceptable pairs. Let \(I\) and \(J\) index the worker-side and position-side in-constraints.
Define the affine function
\[ H(x)= \sum_{(i,j)\in E_{\mathrm{out}}}x_{ij} +\sum_{i\in I}\left(a_i-\sum_{j\in S_i}x_{ij}\right) +\sum_{j\in J}\left(b_j-\sum_{i\in T_j}x_{ij}\right). \]
Every summand is nonnegative on every feasible assignment. For example,
\[ \sum_{j\in S_i}x_{ij}\leq\sum_jx_{ij}\leq a_i. \]
Consequently, an assignment satisfies all specified constraints if and only if \(H(x)=0\). Constraints on unacceptable pairs hold automatically.
In rotation coordinates, write
\[ \ell(y)=H(\Phi(y))=\gamma+\sum_{v=1}^k c_vy_v. \]
All these coefficients are computable exactly in polynomial time, and
\[ \ell(y)\geq0\qquad\text{for every }y\in\mathcal C. \]
Thus the target set is precisely \(\Phi(\{y\in\mathcal C:\ell(y)=0\})\).
First observe a property of partially applied rotations.
Lemma 1. If \(y\in\mathcal C\) and \(0<y_v<r_v\), every predecessor of \(v\) is fully applied and every successor is unused. With all other coordinates fixed, \(y_v\) can vary throughout \([0,r_v]\) while preserving closedness.
Proof. Positive \(y_v\) forces every predecessor to its upper bound. A positive successor would force \(y_v=r_v\), which is excluded. These conditions remain sufficient throughout the indicated interval. \(\square\)
Because \(\ell\) is affine, Lemma 1 lets us replace any partial coordinate by an endpoint without increasing \(\ell\). Repeating this produces a closed vector with every coordinate in \(\{0,r_v\}\). Hence the minimum of \(\ell\) over \(\mathcal C\) is attained at such a vector.
These endpoint vectors correspond exactly to ideals of the rotation poset. Here an ideal \(K\) means that \(q\in K\) and \(p\prec q\) imply \(p\in K\). Its objective value is
\[ \gamma+\sum_{v\in K}c_vr_v. \]
Minimum-weight ideal selection is a polynomial-time minimum-cut problem. Explicitly, for weights \(w_v=c_vr_v\), use:
A minimum cut crosses no precedence arc: a cut respecting precedence exists with capacity at most \(\sum_v|w_v|\). The vertices on its source side therefore form an ideal. For an ideal \(K\), the cut capacity is
\[ \sum_{w_v<0}|w_v|+\sum_{v\in K}w_v, \]
so minimizing the cut minimizes the ideal weight.
The minimum of \(H\) is nonnegative. It is zero exactly when the constraints are feasible. All capacities have polynomial bit length, proving feasibility is in \(\mathrm P\).
Give each rotation one of three statuses:
A complete status pattern determines an open coordinate cell. Suppose that cell contains a closed vector. Its closure is the box obtained by replacing each partial interval with \([0,r_v]\).
This entire box lies in \(\mathcal C\). Indeed, every predecessor of a \(*\) coordinate has status \(1\), every successor has status \(0\), and every predecessor of a status-\(1\) coordinate also has status \(1\).
The nonnegative penalty has a useful consequence.
Lemma 2. If such an open cell contains a vector with \(\ell(y)=0\), then \(\ell\) vanishes throughout its closure.
Proof. At that vector, each free coordinate can be varied slightly in either direction while staying in the box. Since \(\ell\) is nonnegative on the box and equals zero at the vector, its coefficient on each free coordinate must be zero. Its value therefore remains zero throughout the box. \(\square\)
Thus every feasible complete pattern yields a nonempty polyhedron of constrained stable assignments. Every constrained stable assignment belongs to the box associated with its own status pattern.
It remains to enumerate exactly these patterns without spending time on branches with no feasible completion.
Fix an order of the rotations. A prefix prescribes statuses on some initial segment. Let \(Z,O,P\) be its sets of unused, fully applied, and partially applied rotations.
Closedness forces the following additional endpoint statuses:
\[ O'=O\cup\operatorname{Pred}(O\cup P),\qquad Z'=Z\cup\operatorname{Succ}(Z\cup P), \]
where predecessors and successors are strict and transitive.
Reject the prefix if \(O',Z',P\) are not pairwise disjoint. This also detects comparable rotations in \(P\).
There is another necessary rejection rule: if \(c_v\neq0\) for some \(v\in P\), reject.
To justify it, suppose a feasible completion existed. By Lemma 1, varying \(y_v\) slightly in either direction would preserve closedness. Nonnegativity of \(\ell\), together with its zero value at the completion, would force \(c_v=0\).
Assume these checks pass. Set
\[ y_v=r_v\quad(v\in O'),\qquad y_v=0\quad(v\in Z'),\qquad y_v=r_v/2\quad(v\in P). \]
Let \(U\) contain the remaining rotations. Every rotation of \(U\) is incomparable with every rotation of \(P\).
The prefix has a feasible completion if and only if it has one in which all coordinates of \(U\) are endpoints.
For the nontrivial direction, take any feasible completion. The coefficients on its partial coordinates are zero, by the same variation argument. Set the prescribed partial coordinates to their midpoints. Then round every other partial coordinate to an endpoint. Lemma 1 preserves closedness at each step, and the zero coefficients preserve \(\ell=0\).
Endpoint completions correspond exactly to ideals \(K\) of the induced poset on \(U\): fully apply \(K\), and leave \(U\setminus K\) unused. Indeed, \(O'\) is downward closed, \(Z'\) is upward closed, and every predecessor of a prescribed partial rotation is already in \(O'\).
Their penalty values are
\[ \gamma+\sum_{v\in O'}c_vr_v+\sum_{v\in K}c_vr_v. \]
The prescribed partial coordinates contribute zero. A minimum-weight ideal computation therefore decides whether this expression can equal zero.
This gives an exact polynomial-time prefix oracle.
Consider a feasible complete pattern. Let \(P\) be its free rotations and \(O\) its fully applied rotations. Its image is
\[ \mathcal Q= \left\{ h+\sum_{v\in P}t_v\rho^v: 0\leq t_v\leq r_v \right\}, \qquad h=x^0+\sum_{v\in O}r_v\rho^v. \]
We must describe this polyhedron without retaining auxiliary rotation variables.
Let \(V\) be the matrix whose columns are \(\rho^v\), for \(v\in P\), in the original assignment coordinates. It has full column rank. Otherwise, a nonzero kernel vector would give two distinct parameter vectors sufficiently close to the box’s midpoint with the same assignment image, contradicting the bijectivity of \(\Phi\).
Choose \(|P|\) coordinate rows \(R\) such that \(V_R\) is nonsingular. Define the affine expression
\[ t(x)=V_R^{-1}(x_R-h_R). \]
Then \(\mathcal Q\) is described exactly, in assignment variables, by
\[ x-h=Vt(x),\qquad 0\leq t_v(x)\leq r_v\quad(v\in P). \]
Each equality can be written as two inequalities. If \(P\) is empty, the description is simply \(x=h\).
There are polynomially many coefficients. Gaussian elimination computes them in polynomial time, and rational matrix inversion gives polynomial bit length. In particular, \(V_R\) has entries in \(\{-1,0,1\}\), so determinant bounds give polynomial bit length for its inverse. Thus every output polyhedron has the required polynomial encoding length.
Run a depth-first ternary search over rotation statuses. Apply the prefix oracle at every node, and prune rejected nodes. At every surviving complete pattern, output its polyhedron.
Correctness. Lemma 2 shows that every output lies entirely in the constrained stable set. Conversely, each constrained stable assignment has a unique rotation vector and hence a status pattern. That vector witnesses acceptance of every prefix along its path, so its polyhedron is output.
Distinctness. Different surviving complete patterns define different coordinate boxes: a coordinate fixed at an endpoint differs from a free coordinate, and the two endpoints differ from each other. All boxes lie in \(\mathcal C\). Since \(\Phi\) is injective there, their image polyhedra are distinct.
Running time. Let \(s\) be the number output. Every accepted node has an accepted complete descendant, by the oracle’s correctness. The depth is \(k\), so accepted nodes lie on the union of \(s\) paths of length \(k\), giving at most \((k+1)s\) accepted nodes. Each has at most three children to test.
If \(s=0\), the root is rejected. Otherwise, the number of oracle calls is \(O(1+ks)\). Each call and each output construction takes polynomial time in \(m,\tau,L\), and \(k=O(e+\tau)\). The total time is therefore
\[ (s+1)\operatorname{poly}(m,\tau,L). \]
This uses the listed types directly; no expansion into individual workers or positions is required.
⟨structured verdict parsed — rendered above⟩
The argument establishes polynomial-time feasibility and the requested output-sensitive polyhedral enumeration, subject to one minor specification issue in the dummy preference lists. I found no false central step or gap requiring new mathematics.
The capacities \(u_{ij}=\min(a_i,b_j)\) are redundant under the original row and column bounds.
The stability comparison is also correct. If \(x_{ij}=u_{ij}\), an endpoint whose quota equals \(u_{ij}\) assigns its entire quota to this pair. Its unmatched mass and its assignments to worse partners are therefore zero. If \(x_{ij}<u_{ij}\), the stable-allocation blocking condition agrees with simultaneous positivity of the two dissatisfaction expressions.
Keeping forbidden acceptable edges in the instance is essential and is explicitly done. Thus forbidden edges remain relevant to stability.
The dummy extension satisfies every augmented equality. Its dummy-worker row sums to \(B\), its dummy-position column sums to \(A\), and the stated entries respect their edge capacities. Conversely, the augmented equalities force exactly these entries, establishing uniqueness.
Each dummy edge has an endpoint that ranks its partner last and has no worse assignment. Hence it cannot block. For original edges, dummy assignments represent precisely the unmatched terms in the original dissatisfaction expressions. Extension and restriction therefore preserve stability.
Minor issue: The dummy preference lists are not completely specified. Saying that each dummy ranks the other dummy last leaves the relative ordering of its original neighbors unspecified. Strict preferences are a hypothesis of the structural theorem subsequently invoked.
Minimum clarification: State that each dummy has a complete strict ordering of its original neighbors, followed by the other dummy. No additional mathematical argument is needed.
Section 4 of [Dean–Munshi](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf) supplies the required structural result: Lemma 10 establishes invariant rotations and multiplicities; Lemma 11 identifies the precedence DAG; Lemma 12 states the one-to-one correspondence with closed rotation vectors. The surrounding construction bounds the number of rotations by twice the edge count and computes their explicit structures and precedence information in polynomial time.
Thus this citation supports substantially more than computation of a single allocation.
The augmented instance satisfies the relevant hypotheses: bipartiteness, strict preferences once the dummy ordering is specified, feasible augmented quota equalities, and admissible edge capacities. Applying fixed rotation directions gives the stated affine map.
Restriction to original assignment coordinates preserves injectivity because those coordinates uniquely determine the dummy extension. This justifies the later uses of bijectivity in the original variables.
The bit-complexity argument is sufficient. A common denominator has bit length polynomial in the input length. With scaled integral data, the allocation and rotation construction uses the described arithmetic operations, so its polynomially many operations preserve polynomial bit length. There is no expansion proportional to numerical mass.
Every forbidden-edge term is nonnegative. Every worker-side deficit is nonnegative because its permitted-set sum is bounded by the whole row sum, and every position-side deficit is nonnegative by the corresponding column bound.
Consequently, \(H(x)=0\) holds exactly when every specified constraint holds. There is no possibility of cancellation between violated constraints.
Taking the union of forbidden acceptable pairs is sufficient: repeated zero requirements need only be imposed once. Unacceptable pairs already have zero assignment. Empty permitted sets also cause no exception; positive masses then make the corresponding deficit strictly positive.
The affine expression \(\ell=H\circ\Phi\), its exact computability, and its nonnegativity throughout \(\mathcal C\) all follow.
Lemma 1 follows directly from closedness. A partial rotation forces its predecessors to be full; it cannot have a positive successor. Changing only that coordinate to either endpoint preserves every precedence implication.
The affine objective can therefore be rounded coordinate by coordinate without increasing its value. Each rounding removes a partial coordinate and creates no new partial coordinate, so the process terminates. Endpoint vectors are exactly the ideals of the rotation poset.
The minimum-cut construction has the correct orientation: an arc from \(q\) to \(p\) prevents selecting \(q\) without selecting its predecessor \(p\). The bound \(M>\sum_v|w_v|\) guarantees that an optimal cut crosses no precedence arc, because a precedence-respecting cut with capacity at most that sum exists.
The displayed cut-capacity identity has the correct signs and constant term. Rational capacities of polynomial bit length admit polynomial-time minimum-cut computation.
Since every closed vector has nonnegative penalty, a minimum of zero is equivalent to constrained feasibility. The case \(k=0\) is covered by the empty ideal.
A realizable complete pattern forces all predecessors of a free coordinate to be full and all its successors to be unused. It also forces all predecessors of a full coordinate to be full. These conditions ensure that the entire closed coordinate box belongs to \(\mathcal C\), including its boundary.
At a zero-penalty point in the relative interior of this box, each free coordinate can vary slightly in both directions. Nonnegativity of the affine penalty forces its coefficient to vanish. Therefore the penalty vanishes throughout the box.
Singleton cells, with no free coordinates, are covered as well. Every feasible assignment has a status pattern, so these boxes cover the target set.
The forced sets \(O'\) and \(Z'\) correctly propagate fullness downward and unused status upward. Their required disjointness with \(P\) detects contradictions, including comparable prescribed partial rotations.
Rejecting a prescribed partial rotation with \(c_v\ne0\) is justified by Lemma 1 and nonnegativity: a zero-penalty completion would permit local variation in both directions and hence require \(c_v=0\).
After these checks, every remaining rotation is incomparable with every member of \(P\). Setting prescribed partial coordinates to their midpoints preserves closedness and penalty. Rounding other partial coordinates preserves both for the reasons given.
The endpoint completions are exactly the ideals of the induced poset on \(U\). The downward closure of \(O'\), upward closure of \(Z'\), and incomparability with \(P\) ensure that no omitted precedence condition invalidates this correspondence.
Finally, every such completion lies in \(\mathcal C\), so every penalty value considered by this minimum-cut problem is nonnegative. This is essential: testing whether the minimum equals zero is therefore an exact existence test, rather than merely an optimization bound.
The full-column-rank argument is valid. A nonzero kernel vector would produce two distinct points sufficiently close to the midpoint of a positive-width box with the same assignment image, contradicting injectivity.
Selecting nonsingular coordinate rows and substituting the resulting affine inverse describes the image exactly. The equalities enforce membership in the affine image, and the parameter inequalities enforce membership in the box.
Determinant bounds give polynomial bit length for the inverse matrix. Combining these coefficients with the polynomial-bit data \(h\) and \(r_v\) preserves polynomial encoding length. The construction uses only assignment variables. The empty-free-set case correctly produces a singleton.
The oracle accepts precisely the prefixes with feasible complete descendants. Consequently, pruning loses no feasible pattern, and every output is a nonempty polyhedron contained in the constrained stable set.
Distinct patterns yield distinct coordinate boxes because all multiplicities are positive. Injectivity on \(\mathcal C\) then guarantees distinct image polyhedra. Overlap or containment does not violate the requested output specification.
Every accepted node lies on a path to an accepted leaf. With \(s\) leaves and depth \(k\), the bound of \((k+1)s\) accepted nodes is valid. Testing at most three children per accepted node yields \(O(1+ks)\) oracle calls. If \(s=0\), the exact oracle rejects the root.
Since every oracle call and output construction costs polynomial time and \(k=O(e+\tau)\), the claimed total bound follows.
The only requested repair is to complete the dummy preference-list specification. The substantive feasibility and enumeration arguments stand.
⟨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.