független részprobléma

Rövid szöveges bemutatás: 
A részproblémák függetlenek, ha az egyes részproblémák megoldásainak semmilyen kombinációja nem rontja el a teljes megoldást. Tehát a részproblémák külön-külön történő megoldása, a teljes feladatnak is megoldása. Könnyen észrevehető, hogy érdemes ilyen független részproblémák keresése, hiszen csökken a probléma mérete (feltesszük, hogy a részprobléma minden esetben kisebb mint az eredeti probléma). Legegyszerűbb példa ilyen típusú feladatokra a gráf keresési, bejárási, színezési problémák. Ilyenkor a két vagy több részgráfra a feladatok egymástól függetlenül megoldhatóak.