2
$\begingroup$

I'm working on the following problem:

I would like to see if it possible to decompose a complete geometric graph on $8$ vertices into $5$ planar star-forests. As doing this by hand was hopeless, I want to try and do it computationally, using this dataset. The idea here was, to check all partitions of edges into $5$ sets, and check whether any of them correspond to such a composition.

However, as there are many such positions, I am having trouble generating them all, and cannot even begin checking their properties. I have been using the following python function: from more_itertools import set_partitions.

I would now like to ask for some help figuring out another way to check this, ideally generating a desired decomposition right away, but am unsure on how to do so.

Any help is greatly appreciated!

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ You probably know this paper Decomposition of Geometric Graphs into Star-Forests? $\endgroup$
    – kabenyuk
    Commented Jan 8 at 16:06
  • 1
    $\begingroup$ Iterating over all partitions might indeed be quite wasteful, as many of them will certainly not be star forests. One option to reduce the number of cases could be to first fix the centers of the star forests and then look at all star forests with these given centers? Another approach that some colleagues of mine have successfully used for similar problems is to phrase the problem as a SAT instance or an integer linear program (ILP) and then solve it using a SAT-solver or ILP-solver. $\endgroup$
    – Patrick Schnider
    Commented Jan 9 at 8:50
  • $\begingroup$ mathoverflow.net/q/286801/46140 seems relevant $\endgroup$
    – Peter Taylor
    Commented Jan 9 at 10:05
  • $\begingroup$ @PatrickSchnider Hi, thank you for the answer! The SAT/ILP idea sounds very interesting. Could you list some references for how this is done? $\endgroup$
    – Jeja
    Commented Jan 9 at 20:03

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .