# Maximum subgraph edge distance greater than given number

I have a weighted graph G with approximately 75000 nodes. I would like to find subgraph G' induced on a subset of nodes, such that all edge weights in G' are greater than a given constant C and the number of nodes in this subset is maximal. In other words, I want a subgraph with this property, but it's only allowed to remove nodes with their adjecent edges, but not edges only.

Is this a know problem or reducible to one? If yes, is it tractable?

• Add all edges which are still absent with weoghts $>C$, and then remove the edges of weight $\leq C$. Then what you need is finding a largest clique in the resulting graph. – Ilya Bogdanov Oct 10 '15 at 13:51
• Thanks, your reply guided me to realising that what I am looking for can be easily formalised with the notion of Maximal independent set, which is dual to cliques. – user1747134 Oct 11 '15 at 9:59

In one direction, given an edge-weighted graph $G$ and a constant $C$, let $G'$ be the graph obtained from $G'$ by removing all edges with weight greater than $C$ and then forgetting about the weights. Then $X$ is an independent set in $G'$ if and only if all edges in $G[X]$ have weight greater than $C$.
For the other direction, given a graph $G$, make an edge-weighted graph $G'$ by assigning all edges to have weight $C'<C$. Then $X$ is an independent set in $G$ if and only if all edges in $G'[X]$ have weight greater than $C$.
The solutions is: Remove all edges with weight > C. Then the problem is changed to finding maximal induced subgraph with no edges. Each vertex $i$ becomes a variable $a_i \in \{0,1\}$ in the ILP. I want to maximise $\sum_i a_i$ subject to: $a_i + \sum_{j \in Adjacent(i)} a_j \le 1 \, \forall i$. Obviously, the values 0 resp. 1 of variables are interpreted as the absence resp. presence of node $i$ in the subgraph.