The problem
Can the vertices of a graph be split into three groups, 0, 1 and 2, so that no edge joins two vertices of the same group? Do not answer the question: write it as a formula, the way lesson 2 reduces problems to SAT.
Use variable 3 * v + c + 1 for “vertex v is in group c”. Return a list of clauses; a clause is a list of literals, k for “variable k is True” and -k for “variable k is False”. The formula must be satisfiable exactly when the split exists, and every assignment that satisfies it must describe a split: each vertex has at least one True group variable, and giving each vertex any one of its True groups puts no edge inside a group.
colouring_formula(2, [(0, 1)])
# for example
# [[1, 2, 3], [4, 5, 6], [-1, -4], [-2, -5], [-3, -6]]
Limits
- Up to 3,000 vertices. At most 4n + 3E clauses: the formula must be built in polynomial time and stay small.
- Edges join two different vertices, and no edge is listed twice.
Builds on HARD-2 Reductions.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | One vertex | Not run | |
| 2 | A triangle | Not run | |
| 3 | Four, all joined | Not run | |
| 4 | An odd wheel | Not run | |
| 5 | An even wheel | Not run | |
| 6 | The Petersen graph | Not run | |
| 7 | A path with no edges at one end | Not run | |
| 8 | 300 vertices | Not run | |
| 9 | 3,000 vertices | Not run |