2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ If I understand this correctly, the problem is to find the lowest weight connected subgraph. Since if there is at least one path from each vertex to any other, the graph is connected. $\endgroup$
    – rus9384
    Commented Jun 12 at 8:57
  • $\begingroup$ The problem is indeed to find the lowest weight subgraph such that its pairwise connectivity is at least $M$. It does not require "there is at least one path from each vertex to any other" but require that "the number of connected node pairs in the subgraph is at least a given number, i.e., $F(S)\geq M$". Therefore, such a subgraph may not be connected, and could be a union of many trees (a forest). $\endgroup$
    – HonestSJ
    Commented Jun 12 at 9:16
  • $\begingroup$ The $NP$-hardness is about the worst case. Even if there is no requirement for a graph to be connected it does not mean that the worst case can't be a connected graph. $\endgroup$
    – rus9384
    Commented Jun 12 at 9:34
  • $\begingroup$ Thanks for your response! I think there might be some misunderstanding. The input to my problem consists only of an edge-weighted graph and an integer, and the output is a subgraph with the lowest weight that satisfies certain conditions. I understand your point that we can prove a problem is NP-hard by showing that a restricted version of the problem is NP-hard. However, the restriction should be applied to the input, not the output (e.g., the requirement for the output to be connected). I hope this clarifies my views. $\endgroup$
    – HonestSJ
    Commented Jun 12 at 9:52
  • $\begingroup$ If the input consists of constantly (e.g. 2, 3 or a million, independent on the input size) many isolated connected subgraphs, the problem is trivally still NP-hard. However, if the size of each isolated connected subgraph is required to be subpolynomial, the problem is likely not NP-hard. $\endgroup$
    – rus9384
    Commented Jun 12 at 10:59

1 Answer 1

1
$\begingroup$

This is still reducible from the k-minimum spanning tree problem.

To reduce an instance, add a big number $W > \sum_{e \in E} c_e$ to every edge weights. Now, any optimal solution will use the minimum number of edges, which is $k - 1$ if $M = \binom{k}{2}$, therefore the solution is a tree (assuming at least one connected solution exists).

$\endgroup$
2
  • $\begingroup$ Thank you for your response! I believe the proof may have a bit of confusion about how to modify an unconnected solution to a connected one while maintaining $F(S) \geq M$ and without worsening the objective value. However, I think your basic idea should be right. I've commented on a more complex proof (which may not be correct). Thank you again for your consideration. $\endgroup$
    – HonestSJ
    Commented Jun 12 at 7:05
  • $\begingroup$ @HonestSJ I think this answer is correct. You don't need to treat disconnected input any different. But if you need the input to be connected, just add edges of sufficiently high weights. $\endgroup$ Commented Jun 13 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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