New encodings achieve 2n + 2√(2n) + O(n^{1/3}) clauses for AtMostOne, refuting prior optimality conjectures, with a matching lower bound and grid compression yielding 2n + o(n) clauses for AtMost_k when k = o(n^{1/3}).
Ein Satz ¨ uber Untermengen einer endlichen Menge
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
citation-role summary
background 2
citation-polarity summary
roles
background 2representative citing papers
Finiteness of k-vertex-critical graphs holds in (P4+ℓP1, chair)-free, (P4+ℓP1,P5,bull)-free, (P4+ℓP1,P5,cricket)-free, and more generally (P4+ℓP1,B4(m),B3(m)+)-free graphs, with χ ≤ ℓ+2 for (P4+ℓP1,K3)-free graphs.
Derives query lower bounds matching lattice width for Tarski fixed point enumeration of isotone maps and gives poly-space algorithms for increasing/decreasing cases on lattices including binary relations.
citing papers explorer
-
Near-Optimal Encodings of Cardinality Constraints
New encodings achieve 2n + 2√(2n) + O(n^{1/3}) clauses for AtMostOne, refuting prior optimality conjectures, with a matching lower bound and grid compression yielding 2n + o(n) clauses for AtMost_k when k = o(n^{1/3}).
-
Vertex-critical graphs in subfamilies of $(P_4+\ell P_1)$-free graphs
Finiteness of k-vertex-critical graphs holds in (P4+ℓP1, chair)-free, (P4+ℓP1,P5,bull)-free, (P4+ℓP1,P5,cricket)-free, and more generally (P4+ℓP1,B4(m),B3(m)+)-free graphs, with χ ≤ ℓ+2 for (P4+ℓP1,K3)-free graphs.
-
On the enumeration of Tarski fixed points
Derives query lower bounds matching lattice width for Tarski fixed point enumeration of isotone maps and gives poly-space algorithms for increasing/decreasing cases on lattices including binary relations.