1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ilya Bogdanov Oct 10 '15 at 13:51
  • $\begingroup$ 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. $\endgroup$ – user1747134 Oct 11 '15 at 9:59
1
$\begingroup$

Your problem is not polynomial (unless P=NP), because your problem is polynomially equivalent to maximum independent set, which is NP-hard.

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$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

I found a solution using ILP, but I don't think it's tractable.

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.

But I'd still be interested in a polynomial (well, quadratic at worst) solution. Could it exist?

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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