You say: "a path is the connexion between a source node and one or multiple sink nodes". Do you mean a "connexion is a path..."? Either way, perhaps your Connexion signature can be rewritten
sig Connexion {from: Node, to: set Node}
That will dramatically reduce the complexity. It may not eliminate the skolemization problem. To address that you should quantify over Connexion:
all c: Connexion | ...