Combinatorial optimization

Question

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

Definition of a connected set: a group of points belonging to V of a group G forms a real connected set if each point of this group is within the boundaries of T-1 from any other point in the same group, T is the number of points in the group.

Note that a connected set is just a connected subgraph of G without edges, but with points.

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

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

For a visual explanation, see the graph below: In the graph, the red, black, green sets of dots are valid connected sets, the green set does not intersect with the red, but the black set is not disjoint for red.

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

Is there an effective algorithm to solve such a problem, besides an exhaustive search? thanks!

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

Answer 1

If you can define your function and prove that it is a Submodular function (a property similar to the convexity properties in continuous optimization), then there are very efficient (highly polynomial) algorithms that will solve your problem, for example, Minimum normal point .

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

There are several available implementations of the minimum norm algorithm, for example. Matlab Toolbox for optimizing submodular functions

Answer 2

I doubt that there is an efficient algorithm, since for a complete graph, for example, you cannot solve the problem without knowing the values ​​of F on each subgraph (unless you have assumptions about F: monotonicity, for example).

However, I would go for a non-deterministic algorithm. Try simulated annealing, with the transitions:

• Remove a point from the set (if connected)
• Move a point from the set to another (if they remain connected)
• Delete set
• Add Single Point Set

Good luck, this seems like a difficult problem.

Answer 3

For such a general F challenge is to develop an optimized algorithm, far from brute force approach.
For example, since we want to find the CS link where F ( CS ) maximizes, should we assume that we really want to find max (Σ F ( CS )) for all CS or the highest value of F from all possible CS, max (F (cs i ))? We do not know for sure.
Moreover, F is arbitrary; we cannot estimate the probability of the presence of F(cs+p1) > F(cs) => F(cs+p1+p2) > F(cs) .

However, we can still discuss this:

It seems that we can deduce from this problem that we can consider each CS independently, that is, if n = F(cs1) adding any cs2 (being disjoint from cs1) does not affect the value of n .

It also seems plausible, and it is here that we should get some gain so that the calculation of F can be done starting from any point CS, and, generally speaking, if CS = cs1+cs2 , F(CS) = F(cs1+cs2) = F(cs2+cs1) .

Then we want to introduce memoization into the algorithm in order to speed up the process when CS gradually grows to find max (F (cs)) [considering F general, an approach to dynamic programming, for example, starting with CS made from all points and then decreasing it little by little seems to be of little interest].

Ideally, we could start with a CS consisting of a point, increasing it by one, checking and saving the values ​​of F (for each subset). Each test first checks if the value of F exists so as not to calculate it; then repeat the process for another point, etc., find the best subsets that maximize F. For a large number of points, this is a very long experience.

A more reasonable approach would be to try out random points and increase the CS to a given size, and then try a different area than the larger CS obtained in the previous step. You can try to evaluate the probability described above and direct the algorithm in a certain way depending on the result.

But, again, due to the lack of properties of F, we can expect that the exponential space will be needed through memoization (for example, saving F (p1, ..., pn) for all subsets). And exponential complexity.

Answer 4

I would use dynamic programming. You can start rephrasing your problem as a problem with node coloring:

• Your goal is to assign a color to each node. (In other words, you are looking for coloring nodes)
• Available colors are black and white.
• To appreciate the coloration, you need to study the set of “maximum connected sets of black nodes”.
  • A set of black knots is called connected if the induced subgraph is connected
  • A connected set of black nodes is called maximal, none of the nodes in the set has a black neighbor in the original graph, which is not contained in the set)
• Your goal is to find a coloring that maximizes ΣF (CS). (Here you summarize the "maximum connected sets of black nodes")
• You have additional restrictions specified in the original message.

Perhaps you could look for an algorithm that does something like the following

• Select node
• Try to color the selected node white
  • Find the color of the remaining nodes that maximize ΣF (CS)
• Try to color the selected node black
  • Find the color of the remaining nodes that maximize ΣF (CS)

Each time you color a white node, then you can check if the graph has become “decomposable” (I composed this word, it is not official):

• A partially colored graph is called “decomposable” if it contains a pair of non-white nodes that are not connected in any way that does not contain a white node.

If your partially colored graph is decomposable, you can divide your problem into two problems.

EDIT: I added an alternative idea and deleted it again. :)