Induced H from an undirected G with given threshold

Quote:

Originally Posted by PeterGrant

some hint?

Well, at least a start.

In the naive approach all possible subsets of N vertices are simply checked out. Since there are 2^N such subsets that algorithm is exponential O(2^N).

I have a suggestion for a greedy algorithm but unfortunately I have no proof it will always find a solution if one exists.

Lets say the subset is the whole initial set of vertices. This subset corresponds to the =equality so the sought after >inequality obviously is not true and this subset is not a solution.

Now what happens if we remove one vertice from the subset? Then the right-hand side of the >inequality becomes 1 less. And all edges leading up to the removed vertice will become invalidated so their x values will be removed from the left-hand side of the >inequality. So the removal of one vertice will shift the balance of the >inequality and if this makes it true a solution subset has been found.

The idea now is that all vertices in the current subset are considered for removal one by one until either a solution subset is found or none was found. In the latter case the vertice with the smallest sum of invalidated x values is removed forming a new current subset. This removal procedure is repeated over and over again until either a solution is found or the subset becomes empty. In each iteration the right-hand side is reduced by 1 and the left-hand side is reduced a little as possible in an effort to keep the >inequality tipped as much as possible towards true.

This algorithm is polynominal O(N*N). And who knows, maybe there's some graph theoretical property I don't know about that tells it always finds a solution indeed if one exists?