# interesting graph question- need some help..

Hi All,
I need to solve the following problem. I have a direct weighted (edge)
graph, and set of "origin" nodes.
There are 2 special characteristics to "origin" nodes:
1) Part of the origin nodes are "split" into 2 nodes- vi and vi'-
(their union represent just 1 node.-> vi). We'll call them "split"
nodes.
2) Some nodes doesn't have incoming edges. We will call these nodes-
"initiators" and the have some weigh associated with them.

i.e each origin node can be a "split" or "initiator" node.
We will call this graph "new" graph.

I have to visit every "initiator" node and at least one (or both) of
every "split" node in the minimum cost.
For the "split" nodes we should be careful:

1) i can't visit vi' without visit vi- always there is a direct edge
from vi to vi'. (it means that either i can visit them together in the
same component or never visit vi')

2) say that i choose to visit vertex vi but not vi', then it means
that i can "remove" vi' from the list of the vertices because i already
cover the "origin" node of vi and vi'. So i don't have to reconsider
vi' in any other component.

For example: this graph includes 5 origin nodes: v1 ,v2...v5
1) v2,v4,v5 are splits into v2,v2',v4,v4' and v5,v5'.
2) v1 and v3 are initiators. v1 weight is (a+x1) and v3 is also (a+x1).

3) the transition cost from node ni to nj, are in the matrix below:
moving from v2 to v4 is: (a+x2)
the empty cells mean that there is no edge between the nodes.

to

v1 v2 v2' v3 v4 v4' v5 v5'

f v1 x2
v2 a (a+x2) (a+x2)
v2' 0 0
v3 x2 x2
v4 a (a+x2)
v4' 0
v5 a
v5'

here are 2 examples (out of many) of 2 optional paths using
the matrix: (v1' and v3' are initiators)

1) v1' -> v2 -> v4 -> v4' -> v5 : cost- (a+x1)-cost of v1'+
(x2)+(a+x2)+(a)+(0)- transition cost: total: 3a+x1+2x2
2) v3': cost- (a+x1)

total cost: 4a+2x1+2x2

- this example is correct, we cover all origin nodes

or

1) v1' -> v2 -> v5 : cost- (a+x1)-cost of v1'+(x2)+(a+x2)= 2a+x1+2x2
2) v3' -> v4: cost: (a+x1)+(x2)=a+x1+x2

total cost: 3a+2x1+3x2

- this example is correct, we cover all origin nodes

Generally, how should i solve this problem, what is the complexity of
this problem? Does anyone know any good reference ?

any help will be appreciated,
Kiwi

.