# 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) < \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.

• You say "you can assume that the graph is connected, so a solution always exists", but a solution to the problem as currently stated always exists regardless. Did you mean to include the constraint that the output graph is connected? – j_random_hacker Dec 7 '17 at 18:15
• In a similar vein, even if the input graph is connected, this does not imply that any particular induced subgraph is also connected. In particular, the optimal induced subgraph may be disconnected. – j_random_hacker Dec 7 '17 at 18:17
• Are delta_1 and delta_2 supposed to be images? They're broken. delta_3 is also broken in a different way. – j_random_hacker Dec 7 '17 at 18:22
• @j_random_hacker Any approximation algorithm for your problem would also be an approximation algorithm for Maximum Clique with the same approximation ratio. This is not so clear. – Yuval Filmus Dec 7 '17 at 19:13
• Your NP-hardness proof shows that the problem is inapproximable, since the gap between the Yes and No instances is infinite. – Yuval Filmus Dec 7 '17 at 19:14

## 1 Answer

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.