dependencies - algorithm to resolve version scope based dependency -

i have problem on dependency algorithm, dependency similar maven dependency, except it's strict version scope based.

for example:

component a, version 1 depends on: component b, version 1~3; , component c, version 2~3 component d, version 1 depends on: component b, version 2~4; , component c, version 1~2 

now, want dependencies when want install component a, version 1 , component d, version 1. because depend on component b,c need correct algorithm correct version of b , c

further more, may need upgrade component , d. example, have below new versions:

component a, version 2 depends on: component b, version 3~5; , component c, version 4~5 component a, version 3 depends on: component b, version 6~7; , component c, version 4~5 component d, version 2 depends on: component b, version 3~4; , component c, version 3~4 

now need algorithm correct version of , d can upgrade , dependencies. 1 problem here component a, version 3 , component d, version 2 has dependency conflict of component b

is there existing algorithm resolve such problem? or similar(easier) problem. have suggestion?

as there should not lots of data, don't consider performance.

thanks in advance!

this problem np-hard via following reduction 3sat. given 3cnf formula, each variable, there component 2 versions, , each clause, there component 3 versions. install 1 version of "super" component, depends on of clause components not picky versions. each clause, clause component 1 depends on first variable appear in clause, version 1 required if literal positive, , 0 if it's negative. clause component 2 depends on second variable, etc. can install super component if , if formula satisfiable.

in light of reduction, makes sense formulate problem constraint satisfaction. each component variable possible values versions of component, plus "not installed" if not having component installed option. every component version depends on version of component b, there constraint involving variable , b, restricting choices of versions particular subset of product of domains. , b in first example, {(1, 1), (1, 2), (1, 3)}, since version 1 depends on b versions 1~3. if version 2 of available well, constraint {(1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5)}. if didn't have install or b, {(none, none), (none, 1), (none, 2), (none, 3), (none, 4), (none, 5), (1, 1), (1, 2), (1, 3), (2, 3), (2, 4), (2, 5)}.

since instances small, want complete backtracking search, possibly constraint propagation. common algorithm constraint propagation ac-3, enforces arc consistency, namely, removing consideration versions won't work, based on what's been eliminated. example, given constraint {(1, 1), (1, 2), (1, 3)}, can eliminate b = none, since none never appears. choices b restricted, can make inferences b's dependency c, etc. when there's no more simplification left do, have guess; 1 strategy pick component fewest versions left , recursively try of them (backtracking).