# Find the maximum induced (weighted) subgraph with edge weights greater than some minimum

I have a (fully connected) weighted undirected graph. I want to find a maximal induced subgraph whose edge weights are all above some minimum value. Or, if not a maximal subgraph, then with some minimum number of edges.

I'm struggling to find the best starting point for this problem.

• Do you want maximal or maximum? – Chao Xu Feb 28 '18 at 3:15
• Thanks for the Q. I'm looking for an induced subgraph with the largest number of vertices, all of whose edges have a weight > some minimum. I thought that was maximal but happy to be wrong. Alternatively, a subgraph that has some minimum number of nodes satisfying the edge weight minimum constraint. It seems to me to be a combination of induced subgraph enumeration and constraint satisfaction on edge weight. – intronic Feb 28 '18 at 7:08
• This is NP-hard. Consider a graph $G$ on $n$ vertices. Create a complete graph $K_n$ with weights 0 if the edge is not in $G$, $1$ otherwise. The maximum induced subgraph of $K_n$ with edge weight at least $1$ is a maximum clique in graph $G$. – Chao Xu Feb 28 '18 at 8:25
• OK sort of obvious now you say it - thanks for your help! – intronic Feb 28 '18 at 8:49