Recent advances in combinatorial optimization (CO) have demonstrated that neural network approaches can effectively tackle NP-complete (NPC) problems without requiring domain-specific heuristics. In this work, we expand the capabilities of neural-based NPC problem solvers by presenting DIFUSCO, a novel framework built on graph-based diffusion framework. By transforming NPC problems into {0, 1}-vector optimization tasks, our framework employs graph-based denoising diffusion models to produce optimal solutions. We explore both Gaussian and Bernoulli noise-based diffusion models and develop an optimized inference protocol to maximize solution efficiency. We demonstrate our approach on two classical NPC combinatorial optimization problems: the traveling salesman problem (TSP) and the maximal independent set (MIS). Our extensive evaluations reveal that DIFUSCO delivers superior performance compared to existing neural solvers for TSP, demonstrating enhanced precision and robustness across different problem scales. Additionally, when tested on the complex SATLIB benchmark for the MIS problem, DIFUSCO achieves results that exceed the current state-of-the-art neural approaches.