3
$\begingroup$

In Graph factorization, a $k$-factor of a graph $G$ is a spanning $k$-regular subgraph which has the same vertex set as $G$. Now I have a random graph $g$ (i.e. complete graph for simplicity) and I want to obtain all the $k$-factors in a list.

My strategy is

  1. get the edges and vertex of $G$: getpairs and getvetex
  2. create all the subsets of getpairs: allsublist, which is equivalent to create all the possible subgraphs.
    • check whether each elements (i.e. number) in every subset is repeated $k$ times (i.e. terms), which corresponds to check every subgraph is $k$-regular graph.
    • check each terms have the same vertex set getvetex of $G$
  3. store the correct subsets (i.e. $k$-factors) in selectlists.
  4. repeat steps 3-4 (namely the for-loop)

Here is the code for the above task:

n = 5;
g= CompleteGraph[n];
getpairs = EdgeList[g] /. UndirectedEdge -> List;
getvetex = VertexList[g];

selectlists = {};
kregular = 2;
allsublist = Subsets[getpairs];
For[ii = 1, ii <= Length[allsublist], ii++,
   terms = Cases[Tally@Flatten@allsublist[[ii]], {x_, kregular} :> x];
   If[terms!={} && terms==DeleteDuplicates@Flatten@allsublist[[ii]] && SameQ[SortBy[terms,Greater],getvetex],
    AppendTo[selectlists, allsublist[[ii]]];];
 ];

For-Loop is quite inefficient and create all Subsets will also take long time when there are many edges in the graph with large n.

Let's say n currently is small n<=6, can one get rid of the for-loop? Are there simple ways to do it? Thank you very much in advance!

$\endgroup$
2
  • $\begingroup$ How large do you expect your graphs to be? In general you want to avoid loops in Mathematica, but for something like $n=20$, you have $2^{190}$ subsets which is not going to be feasible and may need a procedural approach. Also, how do you feel about isomorphic graphs? May be able to reduce the computation if we can ignore isomorphic graphs. $\endgroup$
    – bRost03
    Jul 23 at 15:54
  • $\begingroup$ Let's say the graph currently is limited to n<=6? if we current ignore the large n case, get rid of for-loops can still somehow speed up a bit? @bRost03 $\endgroup$
    – Xuemei
    Jul 23 at 16:05
2
$\begingroup$

One big speed-up you can get is realizing a $k$-regular graph has $kn/2$ edges so you don't have to generate all subsets of the edges. This goes from considering $2^{n(n-1)/2}$ subsets to $\binom{n (n-1) /2}{kn/2}$ which is a large savings. I am still thinking if there's a way to get more savings by constraints involving spanning sets or regular sets. Either way, here's a more functional solution as opposed to your procedural one. For $n=7$, $k=2$ this is 30x faster than your code on my machine.

edges[n_] := EdgeList@CompleteGraph[n];
kEdges[k_, n_] := If[OddQ[k n], Print["No k-factors"]; Abort[];, 
  Subsets[edges[n], {k n/2}]]
regularSpanQ[edges_, k_] := Equal @@ Append[Last@Thread[Tally@Flatten[List @@@ edges]], k]

then for example

With[{k = 2, n = 6}, Graph /@ Select[kEdges[k, n], regularSpanQ[#, k] &]]

gives

enter image description here

$\endgroup$
5
  • $\begingroup$ thank you very much! It's a really good point that one can reduce the Subsets with some conditions. $\endgroup$
    – Xuemei
    Jul 23 at 16:20
  • $\begingroup$ just one question, will the method ( i.e. Subsets[edgeslist, {k n/2}]]) work for non-complete graph such as PetersenGraph[5,1] (although many vertices but few edges)? @bRost03 $\endgroup$
    – Xuemei
    Jul 24 at 7:59
  • $\begingroup$ Yes, that condition is from the fact that your $k$-factor is $k$-regular and has nothing to do with the underlying graph $\endgroup$
    – bRost03
    Jul 24 at 11:31
  • $\begingroup$ the condition n is the number of vertex, right? $\endgroup$
    – Xuemei
    Jul 24 at 14:37
  • $\begingroup$ @Xuemei Correct $\endgroup$
    – bRost03
    Jul 24 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.