5
$\begingroup$

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$:

delta_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):

delta_2

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:

delta_3


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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – j_random_hacker Dec 7 '17 at 18:15
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Dec 7 '17 at 18:17
  • $\begingroup$ Are delta_1 and delta_2 supposed to be images? They're broken. delta_3 is also broken in a different way. $\endgroup$ – j_random_hacker Dec 7 '17 at 18:22
  • 1
    $\begingroup$ @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. $\endgroup$ – Yuval Filmus Dec 7 '17 at 19:13
  • 1
    $\begingroup$ Your NP-hardness proof shows that the problem is inapproximable, since the gap between the Yes and No instances is infinite. $\endgroup$ – Yuval Filmus Dec 7 '17 at 19:14
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.