Minimum weight k-induced subgraph 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) &lt; \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 $&lt; \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.
The problem cannot be approximated. Consider the reduction that you described from k-clique to your problem but this time assign zero weight to the original edges. Any (multiplicative) approximation algorithm also solves the k-clique problem this is because it must return 0 if there is a k-clique.