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.

  • $\begingroup$ Do you want maximal or maximum? $\endgroup$ – Chao Xu Feb 28 '18 at 3:15
  • $\begingroup$ 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. $\endgroup$ – intronic Feb 28 '18 at 7:08
  • 2
    $\begingroup$ 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$. $\endgroup$ – Chao Xu Feb 28 '18 at 8:25
  • $\begingroup$ OK sort of obvious now you say it - thanks for your help! $\endgroup$ – intronic Feb 28 '18 at 8:49

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.