Combinatorial optimization

Question

Suppose we have a connected and undirected graph: G=(V,E).

Definition of connected-set: a group of points belonging to V of G forms a valid connected-set iff every point in this group is within T-1 edges away from any other point in the same group, T is the number of points in the group.

Pls note that a connected set is just a connected subgraph of G without the edges but with the points.

And we have an arbitrary function F defined on connected-set, i.e given an arbitrary connected-set CS F(CS) will give us a real value.

Two connected-sets are said disjoint if their union is not a connected set.

For an visual explanation, pls see the graph below: In the graph, the red,black,green point sets are all valid connected-sets, green set is disjoint to red set, but black set is not disjoint to the red one.

Now the question: We want to find a bunch of disjoint connected-sets from G so that: (1)every connected-set has at least K points. (K is a global parameter). (2)the sum of their function values,i.e max(Σ F(CS)) are maximized.

Is there any efficient algorithm to tackle such a problem other than an exhaustive search? Thx!

For example, the graph can be a planar graph in the 2D Euclidean plane, and the function value F of a connected-set CS can be defined as the area of the minimum bounding rectangle of all the points in CS(minimum bounding rectangle is the smallest rectangle enclosing all the points in the CS).

Answer 1

If you can define your function and prove it is a Submodular Function (property analogous to that of Convexity in continuous Optimization) then there are very efficient (strongly polynomial) algorithms that will solve your problem e.g. Minimum Norm Point.

To prove that your function is Submodular you only need to prove the following:

There are several available implementations of the Minimum Norm Point algorithm e.g. Matlab Toolbox for Submodular Function Optimization

Answer 2

I doubt there is an efficient algorithm since for a complete graph for instance, you cannot solve the problem without knowing the value of F on every subgraph (except if you have assumptions on F: monotonicity for instance).

Nevertheless, I'd go for a non deterministic algorithm. Try simulated annealing, with transitions being:

• Remove a point from a set (if it stays connected)
• Move a point from a set to another (if they stay connected)
• Remove a set
• Add a set with one point

Good luck, this seems to be a difficult problem.