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?

Improve this question
$\endgroup$
2
  • 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
    Commented Oct 10, 2015 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
    Commented Oct 11, 2015 at 9:59

2 Answers 2

Reset to default
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$.

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?

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .