Let $G$ be multipartite directed weighted graph with $k$ independent sets (we will call them "layers"). We select exactly one node from each layer and form the induced subgraph $H_k$. That is, $H_k$ has exactly $k$ nodes (one from each layer) and contains all edges from $G$ that have both endpoints in $H_k$.
Our goal is to find $H_k$ such that the total weight of all of its edges is minimized: $$\min_{H_k \subset G}\sum_{e \in H_k} weight(e)$$
(you can assume that the graph is connected, so a solution always exists)
Case #1: Graph is flat
To better illustrate the problem I will give some examples. Consider a special case where all edges in $G$ are from layer $i$ to layer $i+1$:
This problem can be easily solved, by adding 2 new nodes entry and exit to $G$. Then we add edges with $0$ weight from entry to every node in layer #1 and from every node in layer #$k$ to exit. Finally the solution to our problem is the shortest path from entry to exit.
In our example, the minimum weight 4-induced subgraph will be: $A_3, B_1, C_1, D_1$, with total weight $20$.
Case #2: Graph has backward edges
In this case, we allow a layer to have backward edges; that is, a layer $i$ can have edges to any layer $j$ as long as $i \ne j$. For instance, consider the graph from the previous example, but this time add some backward edges (with blue color):
Unfortunately, the previous approach does not work anymore, as the previous approach will give us the same solution $A_3, B_1, C_1, D_1$ with a total weight of $70$, but the minimum subgraph is $A_3, B_2, C_1, D_2$ with total weight $34$
Case #3: Re-define the problem
Clearly, the introduction of "layers" can make the analysis hard. So, we can redefine the problem without requiring $G$ to be multipartite. That is, instead of having layers, we add an edge with $\infty$ weight between every pair on the same layer. Then the minimum weight k-induced subgraph $H_k$, cannot have two nodes from the same layer, as this would imply that $H_k$ contains an edge with $\infty$ weight. Back in our example, the previous graph becomes:
The case #3 is NP-hard
Unfortunately in the general case this problem is NP-hard (because it is an optimization problem), as there is a reduction from k-clique:
Let $R$ be an undirected unweighted graph that we want to check whether it has a $k$-clique. That is, we want to check whether $clique(R,k)$ is True or not. Thus, we create a new directed graph $R\space'$ as follows:
$R\space'$ contains all the nodes from $R$
$\forall$ edge $(u,v)\in R$, we add the edges $(u,v)$ and $(v,u)$ in $R\space'$ with $weight = 1$
$\forall$ edge $(u,v)\notin R$, we add the edges $(u,v)$ and $(v,u)$ in $R\space'$ with $weight = \infty$
Then we find the minimum weight k-induced subgraph $H_k$ in $R'$. It is true that:
$$\sum_{e \in H_k} weight(e) < \infty \Leftrightarrow clique(R,k) = True$$ $:\Rightarrow$ If the total edge weight of $H_k$ is not $\infty$, this implies that for every pair of nodes in $H_k$, there is an edge with weight $1$ in $R\space'$ and thus an edge in $R$. This by definition means that the nodes of $H_k$ form a k-clique in $R$. Otherwise (the total edge weight of $H_k$ is $\infty$) it means that it does not exist a set of $k$ nodes in $R\space'$ that has all edge weights $< \infty$.
$:\Leftarrow$ If $R$ has a k-clique, then there will be a set of $k$ nodes that are fully connected. This set of nodes will have no edge with $\infty$ weight in $R\space'$. Thus, these nodes will form an induced subgraph of $R\space'$ and the total weight will be smaller than $\infty$.
(proof is not formal; I just describe the general idea)
The Question
Although the problem that I described is NP-hard (assuming that my analysis is correct), I want to find an approximation algorithm (along with a proof) that can give me a solution that is at most $n$ times worse than optimal (obviously we want $n$ to be as small as possible).
There is also a paper that solves a similar problem, but I don not know if that helps.
