Large Hamiltonian graphs with minimum degree n to the power 1 minus a small epsilon contain a 2-factor consisting of exactly k cycles.
hub Canonical reference
Karp.Reducibility among Combinatorial Problems, pages 85–103
Canonical reference. 100% of citing Pith papers cite this work as background.
19
Pith papers citing it
6,151
external citations · Crossref
Background
100% of classified citations
hub tools
citation-role summary
background 6
citation-polarity summary
roles
background 6polarities
background 6representative citing papers
An algorithm for online Steiner forest achieves constant competitiveness with amortized O(log n) recourse.
MathConstraint generates scalable, automatically verifiable combinatorial problems where LLMs achieve 18.5-66.9% accuracy without tools but roughly double that with solver access.
Random 0/1 polytopes have edge-expansion Θ(d) whp for p ≤ 1-ε and Ω(d^k) for any k when p ≤ 1/2-ε, verifying the Mihail-Vazirani conjecture in strong form with a phase transition at p=1/2.
A new single-SDP rounding method for Lovász theta that provably recovers maximum weighted stable sets in generalized split graphs and other perfect graph subclasses via value function approximation and dynamic programming.
ConvexTok uses convex relaxation of tokenization to a linear program, improving intrinsic metrics, bits-per-byte, and some downstream tasks while certifying near-optimality within 1% at typical vocabulary sizes.
Exponential lower bounds for cutting planes and Res(⊕) on binary clique formulas for random dense graphs, with polynomial randomized communication complexity for falsified clause finding.
A knowledge-first approach to LLM-driven automatic heuristic design in combinatorial optimization yields better discovery efficiency, transfer, and generalization than code-centric baselines by formalizing a distortion-compression trade-off.
Dynamic programming solves interval ordering in O(2^n poly(n)) time via oracle access to f, in polynomial time when f-f(0) is subadditive or superadditive, with a 2^{n-1} lower bound and NP-hardness for some simple f.
A unified framework yields eight depth measures on matroids with six shown functionally inequivalent, two matching branch-depth and tree-depth, and all coinciding on matroids versus matrices over any field.
Broadcast Independence and Broadcast Packing are FPT parameterized by treewidth plus diameter via DP on nice tree decompositions, W[1]-hard for pathwidth, and admit a constant-factor approximation parameterized by treewidth.
O(n^3 log n) algorithm computes maximum (weighted) independent sets for disk graphs with all disks on the convex hull, plus O(n^3 log^2 n) for k-dispersion on the same inputs.
Gaussian randomized rounding on two-qubit marginals of depth-D circuits with local depolarizing noise p yields samples whose expected Max-Cut cost matches the noisy quantum device up to an approximation ratio of 1-O[(1-p)^D].
NP-completeness of knapsack and subset sum proven for max-plus and max-times matrix semigroups, with pseudo-polynomial and polynomial algorithms demonstrated.
The authors give an Õ(n + √(wt))-time algorithm for Subset Sum.
An ILP formulation for Evolomino encodes puzzle rules as linear constraints and supports generation of unique instances, with solver tests up to 18x18 grids.
Simulations predict that a virtually connected photonic probabilistic computer solves Erdos-Renyi graph spin-glass ground states orders of magnitude faster than digital annealing units by avoiding embedding and sparsification.
Studying twists of edges in embeddings of cubic graphs yields bounds on the number of singular edges.
A hybrid CPU-GPU algorithm derived from Schroeppel-Shamir's subset sum method solves market split feasibility instances with up to 10 constraints and 90 variables, with reported runtimes under 15 minutes for (9,80) and up to one day for (10,90).
citing papers explorer
-
Rounding the Lov\'asz Theta Function with a Value Function Approximation
A new single-SDP rounding method for Lovász theta that provably recovers maximum weighted stable sets in generalized split graphs and other perfect graph subclasses via value function approximation and dynamic programming.
-
Sampling (noisy) quantum circuits through randomized rounding
Gaussian randomized rounding on two-qubit marginals of depth-D circuits with local depolarizing noise p yields samples whose expected Max-Cut cost matches the noisy quantum device up to an approximation ratio of 1-O[(1-p)^D].
-
On tropical knapsack-type problems
NP-completeness of knapsack and subset sum proven for max-plus and max-times matrix semigroups, with pseudo-polynomial and polynomial algorithms demonstrated.
-
GPU accelerated variant of Schroeppel-Shamir's algorithm for solving the market split problem
A hybrid CPU-GPU algorithm derived from Schroeppel-Shamir's subset sum method solves market split feasibility instances with up to 10 constraints and 90 variables, with reported runtimes under 15 minutes for (9,80) and up to one day for (10,90).