A Quadratic-Time Solution to the Minimum Dominating Set Problem: A Breakthrough Algorithm
Frank Vega · 2025
This paper presents an algorithm to compute the Minimum Dominating Set (MDS) in general undirected graphs by transforming them into chordal graphs, where MDS can be solved in linear time. The approach handles isolated nodes explicitly, constructs a chordal graph using tuple nodes representing vertices and their closed neighborhoods, and ensures chordality via a clique structure. The MDS is computed on the transformed graph and mapped back to the original, yielding an exact solution. Correctness is validated through domination preservation and minimality proofs, with a running time of O(n 2 ) for n vertices, outperforming typical exponential-time methods for general graphs. An alternative Mixed Integer Linear Programming (MILP) implementation for chordal graphs is provided via pip install baldor , confirming correctness for small to medium-sized graphs despite higher complexity than linear-time alternatives and providing strong evidence that P = NP.