Ngày 17/9/2026, nghiên cứu công bố trên arXiv giới thiệu thuật toán SSLD (Semidefinite Spectral Learning with DSATUR) nhằm cải thiện hiệu quả của thuật toán heuristic DSATUR trong bài toán tô màu đồ thị (Graph Coloring Problem). Bài toán tô màu đồ thị vốn thuộc lớp NP-khó (NP-hard), đóng vai trò quan trọng trong việc phân bổ tần số vô tuyến và lập lịch trình sản xuất (Job Shop Scheduling). Trước đây, DSATUR được xem là một trong những giải pháp heuristic nhanh nhất nhưng thường cần nhiều màu hơn so với các thuật toán tối ưu chuyên sâu.
Nhóm nghiên cứu đề xuất giải pháp tiền xử lý đồ thị trước khi chuyển giao cho DSATUR hoàn thiện. Cụ thể, SSLD áp dụng quy hoạch nửa xác định (Semidefinite Programming - SDP), tương tự phương pháp tính số theta Lovász (Lovász theta number), để tìm và cố định một lớp màu đầu tiên đạt chất lượng cao. Sau khi xác định xong tập đỉnh này, thuật toán DSATUR tiêu chuẩn mới tiếp quản và xử lý phần còn lại của đồ thị. Theo nhóm tác giả, SSLD là hướng tiếp cận đầu tiên cải tiến DSATUR bằng cách tiền xử lý thông qua các lớp màu cố định.
Nhóm tác giả đã tiến hành thử nghiệm SSLD trên hơn 1.600 trường hợp kiểm chuẩn, bao gồm các tập dữ liệu DIMACS, các dạng đồ thị ngẫu nhiên (Erdős–Rényi, Watts–Strogatz, Barabási–Albert), cùng các bài toán thực tế về phân bổ tần số và lập lịch xưởng. Kết quả cho thấy SSLD đạt hiệu quả ngang bằng hoặc vượt trội hơn DSATUR trong hầu hết các trường hợp, đồng thời vượt qua thuật toán cơ sở GISD (vốn dùng tiền xử lý một lớp màu dạng ngây thơ).
Mặc dù mang lại giải pháp tô màu ít màu hơn, SSLD phải đánh đổi bằng thời gian tính toán lớn. Nghiên cứu chỉ ra rằng việc giải quy hoạch nửa xác định khiến thời gian thực thi của SSLD chậm hơn khoảng 195 lần so với thuật toán DSATUR gốc. Nhóm tác giả nhận định phương pháp tiền xử lý một lớp màu dựa trên SDP mở ra hướng nghiên cứu mới để tiếp tục tối ưu hóa hiệu năng tính toán trong tương lai.