patternMinor
Minimum weight k-induced subgraph
Viewed 0 times
subgraphweightminimuminduced
Problem
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 tha
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 tha
Solution
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.
Context
StackExchange Computer Science Q#85077, answer score: 2
Revisions (0)
No revisions yet.