algorithm - Directed maximum weighted bipartite matching allowing sharing of start/end vertices -

algorithm - Directed maximum weighted bipartite matching allowing sharing of start/end vertices -

let g (u u v, e) weighted directed bipartite graph (i.e. u , v 2 sets of nodes of bipartite graph , e contains directed weighted edges u v or v u). here example:

in case:

u = {a,b,c} v = {d,e,f} e = {(a->e,7), (b->d,1), (c->e,3), (f->a,9)}

definition: directionalmatching (i made term create things clearer): set of directed edges may share start or end vertices. is, if u->v , u'->v' both belong directionalmatching v /= u' , v' /= u may u = u' or v = v'.

my question: how efficiently find directionalmatching, defined above, bipartite directional weighted graph maximizes sum of weights of edges?

by efficiently, mean polynomial complexity or faster, know how implement naive brute forcefulness approach.

in illustration above maximum weighted directionalmatching is: {f->a,c->e,b->d}, value of 13.

formally demonstrating equivalence of problem other known problem in graph theory valuable.

thanks!

note 1: question based on maximum weighted bipartite matching _with_ directed edges relaxation allowed edges in matching share origin or destination. since relaxation makes big difference, created independent question.

note 2: maximum weight matching. cardinality (how many edges present) , number of vertices covered matching irrelevant right result. maximum weight matters.

note 2: during research solve problem found paper, think helpful others trying find solution: alternating cycles , paths in edge-coloured multigraphs: survey

note 3: in case helps, can think of graph equivalent 2-edge coloured undirected bipartite multigraph. problem formulation turn into: find set of edges without colour-alternating paths or cycles has maximum weight sum.

note 4: suspect problem might np-hard, not experienced reductions haven't managed prove yet.

yet example:

imagine had

4 vertices: {u1, u2} {v1, v2}

4 edges: {u1->v1, u1->v2, u2->v1, v2->u2}

then, regardless of weights, u1->v2 , v2->u2 cannot in same directionalmatching, neither can v2->u2 , u2->v1. u1->v1 , u1->v2 can, , can u1->v1 , u2->v1.

define new undirected graph g' g follows.

g' has node (a, b) weight w each directed border (a, b) weight w in g g' has undirected border ((a, b),(b, c)) if (a, b) , (b, c) both directed edges in g

http://en.wikipedia.org/wiki/line_graph#line_digraphs

now find maximal (weighted) independent vertex set in g'.

http://en.wikipedia.org/wiki/vertex_independent_set

edit: stuff after point works if of border weights same - when border weights have different values more hard problem (google "maximum weight independent vertex set" possible algorithms)

typically np-hard problem. however, g' bipartite graph -- contains cycles. finding maximal (weighted) independent vertex set in bipartite graph not np-hard.

the algorithm run on g' follows.

find connected components of g', h_1, h_2, ..., h_k for each h_i 2-coloring (say reddish , blue) of nodes. cookbook approach here depth-first search on h_i alternating colors. simple approach color each vertex in h_i based on whether corresponding border in g goes u v (red) or v u (blue). the 2 options nodes select h_i either reddish nodes or bluish nodes. take colored node set higher weight. example, reddish node set has weight equal h_i.nodes.where(node => node.color == red).sum(node => node.w). phone call higher-weight node set n_i. your maximal weighted independent vertex set union(n_1, n_2, ..., n_k).

since each vertex in g' corresponds 1 of directed edges in g, have maximal directionalmatching.

algorithm graph complexity-theory matching