Dependency Algorithm - find a minimum set of packages to install

Question

I'm working on an algorithm which goal is to find a minimum set of packages to install package "X".

I'll explain better with an example:

X depends on A and (E or C)
A depends on E and (H or Y)
E depends on B and (Z or Y)
C depends on (A or K)
H depends on nothing
Y depends on nothing
Z depends on nothing
K depends on nothing

The solution is to install: A E B Y.

Here is an image to describe the example:

Is there an algorithm to solve the problem without using a brute-force approach?

I've already read a lot about algorithms such as DFS, BFS, Dijkstra, etc... The problem is that these algorithms are unable to handle the "OR" condition.

UPDATE

I don't want to use external libraries.

The algorithm doesn't have to handle circular dependencies.

UPDATE

One possible solution could be to calculate all the possible paths of each vertex and, for each vertex in the possible path, doing the same. So, the possible path for X would be (A E),(A C). Now, for each element in those two possible paths we can do the same: A = (E H),(E Y) / E = (B Z),(B Y), and so on... At the end we can combine the possible paths of each vertex in a SET and choose the one with minimum length.

What do you think?

Answer 1

Unfortunately, there is little hope to find an algorithm which is much better than brute-force, considering that the problem is actually NP-hard (but not even NP-complete).

A proof of NP-hardness of this problem is that the minimum vertex cover problem (well known to be NP-hard and not NP-complete) is easily reducible to it:

Given a graph. Let's create package P_v for each vertex v of the graph. Also create package X what "and"-requires (P_u or P_v) for each edge (u, v) of the graph. Find a minimum set of packages to be installed in order to satisfy X. Then v is in the minimum vertex cover of the graph iff the corresponding package P_v is in the installation set.

Answer 2

"I dint get the problem with "or" (the image is not loading for me). Here is my reasoning . Say we take standard shortest route algo like Dijkstras and then use equated weightage to find the best path . Taking your example Select the best Xr from below 2 options

Xr= X+Ar+Er
Xr= X+Ar+Cr

where Ar = is the best option from the tree A=H(and subsequent child's) or A=Y(and subsequent childs)

The idea is to first assign standard weight for each or option (since and option is not a problem) . And later for each or option we repeat the process with its child nodes till we reach no more or option .

However , we need to first define , what best choice means, assume that least number of dependencies ie shortest path is the criteria . The by above logic we assign weight of 1 for X. There onwards

X=1
X=A and E or C hence X=A1+E1 and X=A1+C1
A= H or Y, assuming H and Y are  leaf node hence A get final weight as 1
hence , X=1+E1 and X=1+C1

Now for E and C
E1=B1+Z1 and B1+Y1 . C1=A1 and C=K1.
Assuming B1,Z1,Y1,A1and K1 are leaf node 

E1=1+1 and 1+1 . C1=1 and C1=1
ie E=2 and C=1

Hence
X=1+2 and X=1+1 hence please choose X=>C as the best route

Hope this clears it . Also we need to take care of cyclical dependencies X=>Y=>Z=>X , here we may assign such nodes are zero at parent or leaf node level and take care of dependecy."