1
$\begingroup$

I am working on a problem where I need to find values for nodes in a graph of k-nodes. Here an example:

enter image description here

The properties are:

  • Each big node (A..H) is connected to at least one blue node
  • Each blue node has exactly 3 edges
  • The value of each blue node equals the XOR of each connected node.

For this specific case, we have:

0 = A ⊕ B ⊕ C
1 = B ⊕ D ⊕ E
2 = C ⊕ F ⊕ G
3 = B ⊕ C ⊕ D
4 = G ⊕ F ⊕ H
5 = D ⊕ E ⊕ G

I am trying to find if there is a solution. Bruteforce is obviously not a solution :(

$\endgroup$
3
  • 1
    $\begingroup$ As I'm sure you're aware, XOR-SAT is solvable efficiently. $\endgroup$
    – cody
    Commented May 14 at 21:02
  • 1
    $\begingroup$ Not sure what it means to XOR values and get more than 1 though. Are these bitvectors? $\endgroup$
    – cody
    Commented May 14 at 21:03
  • $\begingroup$ @cody It's an XOR operation on a whole binary number, rather than just on single bit. Imagine 3 XOR 5. Convert to binary: 011 XOR 101 = 110. You just apply XOR to each bit 1-by-1, in-line. So XOR first bit in both numbers. XOR second bit, XOR third bit... and so on $\endgroup$ Commented May 15 at 6:04

1 Answer 1

3
$\begingroup$

You can express this as an instance of XOR-SAT, then find a solution using Gaussian elimination. I am assuming that each value $1,2,3,$ represents a bit-vector of some appropriate length, and you are doing bitwise XOR. The variables are the individual bits of $A,B,C,\dots$, and each equation yields one clause per bit position.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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