Hello, this is my first post!

Please have a look at this problem:

--->

Bip-Dominating-Set (BDS): Let G(L,R,E) be a bipartite graph and k a positive integer. Is there a subset S of L s.t. |S|<=k and S dominates R?

Trip-Dominating-Set (TDS): Let G(L,C,R,E) be a tripartite graph and k a positive integer. Is there a subset S of L s.t. |S|<=k and S dominates both C and R?

Prove that if TDS is in P, then BDS is in P.

EDIT: I forgot something important!!!

A set X of vertices dominates another set Y of vertices iff

for each y in Y there exists a vertex x in X such that there is an edge x->y.

In other words, If there are vertices in Y that aren't reached by edges starting from vertices in X, then X doesn't dominate Y.

Let f:A->B be a function. A dominates B iff f is surjective. Just joking :-)

<---

There is a painfully obvious reduction so maybe I'm missing something.

If G(L,R,E) is a bipartite graph, isn't G(L,0,R,E) a tripartite graph (where 0 is the empty graph)?

If empty graphs are not acceptable, I may just add a vertex v and all the edges from the vertices in L to v. The new graph would be G(L,{v},R,E U E') where E' is the set of the new vertices.

Then S (Yes/No) is the solution to BDS(G(L,R,E)) if and only if S is the solution to TDS(G(L,{v},R,E U E')).

Gandalf