This tutorial develops three complementary hardness results for SN3DM, a role recovery under marginal symmetry that asks whether three disjoint labeled classes with identical weight multisets can be partitioned into class-transversal triples of one common target sum.
Abstract
Symmetric Numerical Three-Dimensional Matching (SN3DM) asks whether three disjoint labeled classes with identical weight multisets can be partitioned into class-transversal triples of one common target sum. Its theme is role recovery under marginal symmetry: identical numerical catalogues force the asymmetric source roles to be reconstructed from incidence structure alone. This tutorial develops three complementary hardness results for that symmetry restriction. Part I gives a unary-polynomial reduction from N3DM. Source roles become ports in one common occurrence set, a uniquely forced filler system reserves one main incidence per port, bipartite edge coloring restores the output-class labels, and a no-carry mixed-radix encoding packs four coordinates into positive integers. Hence SN3DM is strongly NP-complete. Part II studies Max-SN3DM, for which strong NP-hardness alone does not exclude a PTAS. Two numerical compilers lift Petrank's perfect-completeness gap for bounded 3DM to unary Max-N3DM, and a defect-stability lemma shows that a symmetric matching of size 13n - d yields a source matching of size at least n - 21d, where n is the multiset cardinality, and d is a symmetric defect. Hence, for some epsilon>0, it is NP-hard to separate perfect instances from those of optimum at most (1- epsilon) times perfect, so no PTAS exists unless P = NP. Every maximal legal triple matching is a 3-approximation, placing the problem in APX. Part III supplies the approximation-preserving reduction Part II does not claim. An exact pair compiler and a one-live-port separation map degree-three Maximum 3DM to unary Max-SN3DM with OPT(Max-SN3DM) = Gamma + OPT(Max-3DM) for a fixed offset Gamma and one-for-one optimum-error transfer. The L-reduction has constants alpha = 764 and beta = 1, so Max-SN3DM is APX-complete. The two are incomparable; worked yes / no instances audit each construction.
An ordered Ruzsa-Szemeredi graph is a graph whose edge set is partitioned into equal-size matchings, each induced in the suffix of the ordering that begins with it. Behnezhad and Ghafari introduced them to parametrize the update time of fully dynamic matching, but almost nothing is known about the numbers themselves. Writing f(n) for the largest number of parts when the matchings have size two, we determine f(n) exactly for every order from five to nineteen, narrow order twenty to two consecutive values, and give an explicit asymptotic construction. The engine is a bijection between ordered decompositions and K_4-peelings of the complete graph, each step deleting a perfect matching from four vertices that currently span a clique. This yields the counting bound floor(n(n-4)/4) at once and reduces equality to whether a cubic or near-cubic remainder is reachable. Structural lemmas cut the candidates to connected bridgeless graphs, and a contraction correspondence carries odd orders to the even census one larger, leaving a finite case analysis that we discharge by isomorphism-free reverse search. The bound is attained only at orders five through nine and eleven, and missed by exactly one at every other order we reach. Order eleven is thus an isolated exception rather than a parity phenomenon: the natural equality conjecture fails, and fails irregularly. Upper bounds are certified by fail-closed sweeps over complete cubic censuses, and every decomposition is re-checked against the definition by an independent verifier. Which of its two values order twenty takes remains open.
The exact domatic-number problem asks, for a fixed integer k, whether a given graph G satisfies dom(G) = k. Riege and Rothe proved DP-completeness for every fixed k>= 5, while the cases k = 3 and k = 4 remained open. We close this classification gap. The main ingredient is a polynomial-time reduction from 3SAT whose output graphs have domatic number 4 in the satisfiable case and domatic number 2 in the unsatisfiable case; in particular, the reduction never produces a graph of domatic number 3. This directly realizes the route suggested by Riege and Rothe for closing the remaining cases. Together with a simpler three-versus-two reduction, this yields DP-completeness of Exact-3-DNP and Exact-4-DNP. The proofs are constructive and give explicit graph gadgets whose local domination constraints encode truth assignments and clause satisfaction. The soundness arguments show conversely that any sufficiently large domatic partition enforces the intended consistency conditions and therefore yields a satisfying assignment. Consequently, Exact-k-DNP is DP-complete for every fixed k>= 3, completing the fixed-value classification from k = 3 onward.
P-SAPST Lite replaces peeling with a degree order and provides a lower latency order choice within the same framework and complements edge oblivious streaming APST by addressing an offline regime in which structural plans can be reused.
Rong Fu, Yongtai Liu, Xiaowen Ma et al.· 0 citations
Stanley's tree-isomorphism conjecture asks whether the chromatic symmetric function distinguishes nonisomorphic trees. We give a reconstruction criterion that permits repeated leaf-component orders. For a proper tree, collapse each leaf component to its center and record its order as a vertex weight. We prove that the chromatic symmetric function reconstructs the tree whenever every nonleaf vertex of this weighted core has a weight that occurs nowhere else in the core. Repetitions among core leaves are unrestricted. The proof uses only the leading star-basis partition and the coefficients immediately above it. As a consequence, the conjecture holds for an infinite class of diameter-six trees not covered by the condition that all leaf-component orders are distinct. We also give a canonical integer-partition model for arbitrary diameter-six trees and an exact cut-partition implementation intended for further work. The unrestricted diameter-six case remains open.
Abstract.
The column number question asks for the maximum number of columns of an integer matrix with the property that all its rank size minors are bounded by a fixed parameter [Formula: see text] in absolute value. Polynomial upper bounds have been proved in various settings in recent years, with consequences for algorithmic questions in integer linear programming and matroid theory. In this paper, we focus on the exact determination of the maximum column number of such matrices with two rows and no vanishing 2-minors. We prove that for large enough [Formula: see text], this number is a quasi-linear function, nondecreasing, and always even. Such basic structural properties of column number functions are barely known, but may be expected to hold in other settings as well. Moreover, our results identify the unique excluded (co)rank two minors for the class of matroids that are representable as a [Formula: see text]-submodular matrix.
We study stochastic dynamic matching on hypergraphs: items of finitely many classes arrive over time and are removed in multisets by activating hyperedges. We characterize stabilizability, the existence of a matching policy under which the queue process is positive recurrent, in terms of the arrival rates and the incidence matrix alone: (G, $\lambda$) is stabilizable if and only if the conservation equation A$\mu$ = $\lambda$ admits a nonnegative solution whose support induces a surjective submatrix, equivalently $\lambda$ lies in the interior of the cone generated by the hyperedges. This extends a characterization known for simple graphs (non-bipartiteness together with the independent-set inequalities) to arbitrary hyperedges, allowing multiplicities and mono-edges, and, unlike the constant-regret theory, needs no general-position assumption. Sufficiency is constructive: a single $\lambda$-oblivious policy, Virtual-Queue Match-the-Longest (VQML), a rewardless variant of the Extended Greedy Primal-Dual policy of Nazari and Stolyar, stabilizes every stabilizable instance and is therefore maximally stable. The sufficiency proof requires the positive recurrence of the signed virtual queue underlying VQML; previous analyses invoke this property but, to our knowledge, do not prove it, and supplying it is a second contribution.
