0
$\begingroup$

A list of 132 subgraphs (each with 4 nodes) is also available. A given node is available in multiple subgraphs.

How can I find 17 subgraphs that are mutually exclusive (i.e., one node can be present only in one of the 17 subgraphs) and cover all 67 nodes?

Since we have 67 nodes and want 17 mutually exclusive subgraphs (with 4 nodes each), two subgraphs out of 17 will have one common node. That is acceptable.

In fact, we want 16 subgraphs with 4 nodes each and one subgraph with 3 nodes.

SG is the list of subgraphs.

SG=Uncompress["1:eJyNl81SFEEQhEddFRRFEUTxj0VAfgRxQQFFEbhy8hE4EFEnD/\
AIPjhbGTFTOtOVOZeO2cmvs6pju2q6hxd/fl/+rarqajAezu3q+nLw7y+7NX6w2z4s+\
rA6HlJiRRLwGHYJiHf6ER7APrAoGREew4SAOGiIJelBCQ9gayyKJpYk4aKtd4m7/v6eD+\
99+MiITUnAY7lLQLzfj/AAtsWiZER4LEvCRdvuEhP+fpLt0yCyHQTxQfPPfWJET4/\
CfwvxYT/CU7AdRqwlROShPVy0zzJKYRdCnGIeQaxLQkfx6TaSUTa6BMRHtVjyCCKLEkTPK\
JtdAuLjfgTqdpcRo4SIPDKiFaXQHYLw6bbXJSBO19M5oT2yPILw6fZF5lHoHxCf1GLJIwj\
tkeXRilLoUkH4dPvaJSA+radzQntkecz4+\
2dV3R32GeGiHUiPQoeBOMs8gtAeO9LDRTuUHoUeBHGuFkseQWiPLA+\
Iz2vRvjGPjAiPkfTI+lh4aMID2HeZR6HDQJxnHkFoj93EA+\
KLhih0mJYHJTyAHbEoe5LIPCC+rOq6/cGIrMO08qDEkYyiCRftp1xLoQct+\
PtXFan9IFAvvxhxLAkX7URGKVQlxNfMI4hDSegoWWVDfMMIiG+\
bPXbKPLKaCw9NZDsZ4rt+BPbYGSNOEyLyyIhWlMJOxq0RB//sVoD7HL0V4C5GT/T+wM/\
JuAPR0xZuOPQMg+sPPV0gSfpFRpL0S4iTI/\
164FxIOz8WSjsuFkr7GBZKOwwWivLOOgwWSmsfC6VViYXSippv9int/P/v0xsmF2k4"]
$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.