The Maximum Clique Problem (MCP) is one of the most representative NP-complete problems in computational complexity theory, and obtaining an exact solution has long been regarded as unlikely to admit a polynomial-time algorithm. This paper presents a deterministic exact algorithmic framework centered on the notion of a “-partition feature. ” By partitioning a graph into a family of triangle-free subgraphs, we establish a structural bound relating the maximum clique size to the number of partitioned subgraphs. Based on this bound, we design a procedure that first partitions the graph and then repeatedly fills vacancies by using the vertex groups appearing in the last-round subgraph to test earlier subgraphs through vertex splitting, followed by the removal of edgeless vertices. Once the subgraph count ceases to change under this vacancy-filling process, the algorithm enters a pruning stage to extract the answer. The central theoretical conclusion of this paper is that, within the vacancy-filling and correction framework developed here, the structural obstructions relevant to the target clique size can be systematically reduced while preserving the maximum-clique value of the original graph. Under the explicit counting scheme presented in the complexity analysis, the running time of the overall procedure is bounded by O (n₀^33), where n₀ is the number of vertices in the original input graph. Consequently, under the formal framework developed in this paper, the Maximum Clique Problem is claimed to admit a polynomial-time exact procedure.
Lok Ping Leung (Thu,) studied this question.