Return to Question

Given an undirected graph $G=(V,E)$ with non-negative edge weights $c_{ij}$ for each $(i,j)\in E$ and an integer $M$, the problem asks to determine the minimum-weight set of edges $S\subseteq E$, such that the pairwise connectivity (the total number of node pairs connected by at least one path) in the edge-induced subgraph $G[S]:=(V[S],S)$ is at least $M$. Here, $V[S]:=\bigcup_{(i,j)\in S}\{i,j\}$.

Formally, for any edge subset $S\subseteq E$, let $$F(S):=|\left\{\{i,j\}\,:\,i,j\in V[S],~i\neq j,~\text{there exists a path from } i \text{ to } j \text{ in graph } G[S] \right\}|.$$ Then the problem can be formulated as $$\min_{S\subseteq E}\left\{\sum_{(i,j)\in S}c_{ij}\,:\,F(S)\geq M\right\}.$$

I have already proven that when the edge-induced subgraph $G[S]$ is required to be connected, the problem can be reduced from the "$k$-minimum spanning tree problem" (which is NP-hard). This is because that in this case, the subgraph $G[S]$ can be determined as a tree subgraph, and thus the constraint imposed on the pairwise connectivity of $G[S]$ directly translates to the constraint on the number of nodes in $G[S]$.

However, I am currently struggling to prove the NP-hardness of the problem when the subgraph is not required to be connected. While I believe the problem remains NP-hard, I am seeking a proof of it.

Given an undirected graph $G=(V,E)$ with non-negative edge weights $c_{ij}$ for each $(i,j)\in E$ and a positive integer $M$, the problem asks to determine the minimum-weight set of edges $S\subseteq E$, such that the pairwise connectivity (the total number of node pairs connected by at least one path) in the edge-induced subgraph $G[S]:=(V[S],S)$ is at least $M$. Here, $V[S]:=\bigcup_{(i,j)\in S}\{i,j\}$.

Formally, for any edge subset $S\subseteq E$, let $$F(S):=|\left\{\{i,j\}\,:\,i,j\in V[S],~i\neq j,~\text{and there exists a path from } i \text{ to } j \text{ in } G[S] \right\}|.$$ Then the problem can be formulated as $$\min_{S\subseteq E}\left\{\sum_{(i,j)\in S}c_{ij}\,:\,F(S)\geq M\right\}.$$

I have already proven that when the edge-induced subgraph $G[S]$ is required to be connected, the problem can be reduced from the "$k$-minimum spanning tree problem" (which is NP-hard). This is because that in this case, the subgraph $G[S]$ can be determined as a tree subgraph, and $F(S)=\binom{|V[S]|}{2}$. Therefore, the constraint imposed on the pairwise connectivity of $G[S]$ (i.e., $F(S)\geq M$) directly translates to the constraint on the number of nodes (i.e., $|V[S]|\geq k$ with $\binom{k}{2}\geq M$ and $\binom{k-1}{2}<M$).

However, I am currently struggling to prove the NP-hardness of the problem when the subgraph $G[S]$ is not required to be connected. While I believe the problem remains NP-hard, I am seeking a proof of it.

Given an undirected graph $G=(V,E)$ with non-negative edge weights $c_{ij}$ for each $(i,j)\in E$ and an integer $M$, the problem asks to determine the minimum weight of edges $S\subseteq E$, such that the pairwise connectivity (the total number of node pairs connected by at least one path) in the edge-induced subgraph $G[S]:=(V[S],S)$ is at least $M$. Here, $V[S]:=\bigcup_{(i,j)\in S}\{i,j\}$.

Formally, for any edge subset $S\subseteq E$, let $$F(S):=|\left\{\{i,j\}\,:\,i,j\in V[S],~i\neq j,~\text{there exists a path from } i \text{ to } j \text{ in graph } G[S] \right\}|.$$ Then the problem can be formulated as $$\min_{S\subseteq E}\left\{\sum_{(i,j)\in S}c_{ij}\,:\,F(S)\geq M\right\}.$$

I have already proven that when the edge-induced subgraph $G[S]$ is required to be connected, the problem can be reduced from the "$k$-minimum spanning tree problem" (which is NP-hard). This is because that in this case, the subgraph $G[S]$ can be determined as a tree subgraph, and thus the constraint imposed on the pairwise connectivity of $G[S]$ directly translates to the constraint on the number of nodes in $G[S]$.

However, I am currently struggling to prove the NP-hardness of the problem when the subgraph is not required to be connected. While I believe the problem remains NP-hard, I am seeking a proof of it.

Given an undirected graph $G=(V,E)$ with non-negative edge weights $c_{ij}$ for each $(i,j)\in E$ and an integer $M$, the problem asks to determine the minimum-weight set of edges $S\subseteq E$, such that the pairwise connectivity (the total number of node pairs connected by at least one path) in the edge-induced subgraph $G[S]:=(V[S],S)$ is at least $M$. Here, $V[S]:=\bigcup_{(i,j)\in S}\{i,j\}$.

Formally, for any edge subset $S\subseteq E$, let $$F(S):=|\left\{\{i,j\}\,:\,i,j\in V[S],~i\neq j,~\text{there exists a path from } i \text{ to } j \text{ in graph } G[S] \right\}|.$$ Then the problem can be formulated as $$\min_{S\subseteq E}\left\{\sum_{(i,j)\in S}c_{ij}\,:\,F(S)\geq M\right\}.$$

I have already proven that when the edge-induced subgraph $G[S]$ is required to be connected, the problem can be reduced from the "$k$-minimum spanning tree problem" (which is NP-hard). This is because that in this case, the subgraph $G[S]$ can be determined as a tree subgraph, and thus the constraint imposed on the pairwise connectivity of $G[S]$ directly translates to the constraint on the number of nodes in $G[S]$.

However, I am currently struggling to prove the NP-hardness of the problem when the subgraph is not required to be connected. While I believe the problem remains NP-hard, I am seeking a proof of it.

I am working on the NP-hardness proof of a problem. Given an undirected graph with non-negative edge weights and an integer M, the problem asks to determine the minimum edge-weighted subgraph such that the pairwise connectivity (the total number of node pairs connected by at least one path) in the subgraph is at least M.

I have already proven that when the subgraph is required to be connected, the problem

"Given an undirected graph with non-negative edge weights and an integer M, find a connected subgraph with minimum edge weights such that the pairwise connectivity of the subgraph is at least M"

can be reduced from the "k-minimum spanning tree problem" (which is NP-hard). This is because that in the connected case, the subgraph can be selected as a tree subgraph, and thus the constraint imposed on the pairwise connectivity of the subgraph directly translates to the constraint on the number of nodes in the subgraph.

However, I am currently struggling to prove the NP-hardness of the problem when the subgraph is not required to be connected. While I believe the problem remains NP-hard, I am seeking a proof of it.

Given an undirected graph $G=(V,E)$ with non-negative edge weights $c_{ij}$ for each $(i,j)\in E$ and an integer $M$, the problem asks to determine the minimum weight of edges $S\subseteq E$, such that the pairwise connectivity (the total number of node pairs connected by at least one path) in the edge-induced subgraph $G[S]:=(V[S],S)$ is at least $M$. Here, $V[S]:=\bigcup_{(i,j)\in S}\{i,j\}$.

Formally, for any edge subset $S\subseteq E$, let $$F(S):=|\left\{\{i,j\}\,:\,i,j\in V[S],~i\neq j,~\text{there exists a path from } i \text{ to } j \text{ in graph } G[S] \right\}|.$$ Then the problem can be formulated as $$\min_{S\subseteq E}\left\{\sum_{(i,j)\in S}c_{ij}\,:\,F(S)\geq M\right\}.$$

I have already proven that when the edge-induced subgraph $G[S]$ is required to be connected, the problem can be reduced from the "$k$-minimum spanning tree problem" (which is NP-hard). This is because that in this case, the subgraph $G[S]$ can be determined as a tree subgraph, and thus the constraint imposed on the pairwise connectivity of $G[S]$ directly translates to the constraint on the number of nodes in $G[S]$.

However, I am currently struggling to prove the NP-hardness of the problem when the subgraph is not required to be connected. While I believe the problem remains NP-hard, I am seeking a proof of it.