Gene selection is critical in cancer classification due to high-dimensional gene expression data. This study introduces a novel approach based on Minimal Dominant Independent Set (MDIS) algorithms, leveraging graph theory to model gene interactions. Two methods are proposed: MDIS weighted by Fisher scores and node degrees (MDIS-Weighted), and a simple greedy MDIS. These methods are compared with traditional approaches using all genes and the Fisher filter method selecting top 100, 200, and 300 genes. Results demonstrate that MDIS-based methods significantly reduce dimensionality while maintaining or improving classification accuracy using SVM and 1-Nearest Neighbor classifiers across five cancer datasets. MDIS-Weighted consistently performed well, achieving accuracies comparable to or better than using all genes while selecting only 2–8% of the original gene set.