|
|
|
|
|
|
by maweki
3842 days ago
|
|
|
Well, you can always transform a true hamiltonian cycle to two cycles of a subgraph if you have a any A->B, C->D in the cycle where also A->D, B->C is in the graph. That's any 4 clique which isn't that hard, considering that the arrows can be transitive for that matter (I think, no proof attached). Also, to show np completeness one must show reduction in both directions. I somehow doubt that any SAT-Problem is reducible to secret-santa, if secret santa isn't exactly hamiltonian cycle anyways. |
|
|