Timeline for Is this kind of "Gerrymandering" NP-complete?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 6, 2020 at 18:59 | answer | added | Adam P. Goucher | timeline score: 5 | |
| Jul 17, 2020 at 12:55 | history | edited | Rodrigo de Azevedo | CC BY-SA 4.0 |
Added link to question on Math SE. Added CS.CC tag.
|
| Mar 3, 2019 at 22:16 | vote | accept | Frunobulax | ||
| Mar 3, 2019 at 21:56 | answer | added | domotorp | timeline score: 10 | |
| Mar 3, 2019 at 21:12 | comment | added | Gerry Myerson | The m.se post was math.stackexchange.com/questions/3119994/… | |
| Mar 3, 2019 at 19:41 | comment | added | Joseph O'Rourke | The term in general use is "$4$-connected" (as opposed to $8$-connected). | |
| Mar 3, 2019 at 19:37 | history | edited | Frunobulax | CC BY-SA 4.0 |
clarify "connected"
|
| Mar 3, 2019 at 19:34 | comment | added | Frunobulax | @AndreasBlass Yes, you're right. I'll change that. | |
| Mar 3, 2019 at 13:05 | comment | added | Andreas Blass | Conjecture: You meant the usual meaning of "connected", not "each square of each region must share at least one edge with at least one other square of the same region". The latter requires only that each connected component of a region contains at least two squares. | |
| Mar 3, 2019 at 12:12 | comment | added | domotorp | (This is, btw, exactly the situation in your diagram for $n=7$.) | |
| Mar 3, 2019 at 12:10 | comment | added | domotorp | For simplicity, suppose $n$ is odd. What about the special case of the problem when you have exactly $(\frac{n+1}2)^2$ voters? In this case the only way you can win is if you can create $\frac{n+1}2$ regions with exactly $\frac{n+1}2$ voters. I would guess that already this version is NP-complete. | |
| Mar 3, 2019 at 12:00 | review | First posts | |||
| Mar 3, 2019 at 13:00 | |||||
| Mar 3, 2019 at 11:56 | history | asked | Frunobulax | CC BY-SA 4.0 |