Random graph partition

Question

I am trying to test some graph partitioning models (they come from the real world, where the graph is slowly self-separating). To do this, I need to be able to evenly distribute this graph among adjacent components (we are also assigned a graph). If the adjacency criterion were not required, I believe that this will be a problem of random partitioning of the set, which can be combinatorially analyzed. Does anyone know of any way to randomly partition graphs into subgraphs (i.e. randomly try one section) or, if this method is not known, randomly try a set of elements? The method of randomizing the number of sections and then randomizing the membership will not work, because for each section size there is a different number of possible sections.

Answer 1

You must distinguish between edge division and vertex-cut partitioning , where you divide the graph along edges or vertices. This greatly affects your problem, as the number of different vertex contractions is much larger than the number of edges. The reason is that you exclusively assign edges to sections at the cutting vertex — unlike edges where you assign vertices to sections — and there are many more edges than vertices (for example, O (n ^ 2) edges for n vertices ) Consequently, a combinatorially large vertex of the cut leads to a larger number of subgraphs that must be checked for connectivity. The naive randomization method is to list all sections, iteratively select one section and check the connectivity of all subgraphs in the selected division. Then you just take the first one. In this case, all solutions have equal probability (uniformly random).