The paternity test is a genetic test that analyzes genetic characteristics (mostly molecular markers) to identify whether two individuals have a parent-child relationship. It is frequently employed in judicial identification and economic species breeding. Because a single marker's discriminability is restricted, numerous markers are typically utilized to produce an accurate result. Obviously, having an excessive number of redundant markers wastes time and resources, and adequate approaches are required to screen reduced and efficient paternity marker sets (PMS). This study established a non-redundant PMS-screening scheme based on the exhaustive algorithm and greedy algorithm. When screening PMS, the greedy algorithm selects markers based on the parental dispersity index (PDI), a uniquely defined metric that outperforms polymorphic information content (PIC) and probability of exclusion (PE). With the conjunctive use of the two algorithms the optimal solutions were found for more than 99.7% of solvable cases in three groups of random sample experiments in this study. This scheme effectively reduces the number of markers in PMS, so conserving people and experimental resources and laying the groundwork for the widespread implementation of paternity assignment technology in economic species breeding.