Timeline for Planar Exact Cover by even-size sets
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jul 1, 2019 at 5:05 | history | bounty ended | Yota Otachi | ||
| S Jul 1, 2019 at 5:05 | history | notice removed | Yota Otachi | ||
| Jul 1, 2019 at 5:05 | vote | accept | Yota Otachi | ||
| Jun 30, 2019 at 20:14 | answer | added | domotorp | timeline score: 2 | |
| Jun 26, 2019 at 6:32 | comment | added | domotorp | @Marzio probably this won't follow from their method, as they write in the paper "We have proved the NP-completeness of Planar 3DM. However it must be stressed that this does not imply NP-completeness for k-dimensional matching (k DM) for k > 3 by the simple argument used in the general (i.e., nonplanar) case of this problem. This is due to the fact that this argument involves an essentially nonplanar construction. Thus we cannot conclude that Planar k DM is NP-complete for any k > 3, although we conjecture that this is the case." | |
| Jun 25, 2019 at 7:45 | comment | added | Marzio De Biasi | you're right ... we should examine the details of the planar X3C reduction if the doubling could work. | |
| Jun 25, 2019 at 2:49 | comment | added | Yota Otachi | @MarzioDeBiasi I think your reduction doesn't preserve the planarity. | |
| Jun 24, 2019 at 15:08 | comment | added | Marzio De Biasi | You can simply double the problem: $U' = \{ x_1,..., x_n, x'_1,...,x'_n \}$ $F'_i = \{x_{i_1}, x_{i_2}, x_{i_3}\} \cup \{x'_{i_1}, x'_{i_2}, x'_{i_3}\}$ And you get a planar instance of X3C in which each $|F'_i| = 6$. | |
| S Jun 24, 2019 at 12:34 | history | bounty started | Yota Otachi | ||
| S Jun 24, 2019 at 12:34 | history | notice added | Yota Otachi | Draw attention | |
| Jun 19, 2019 at 16:03 | history | edited | Yota Otachi | CC BY-SA 4.0 |
edited body
|
| Jun 7, 2019 at 3:00 | history | tweeted | twitter.com/StackCSTheory/status/1136830263948926976 | ||
| Jun 6, 2019 at 11:19 | history | edited | Yota Otachi | CC BY-SA 4.0 |
added 2 characters in body
|
| Jun 6, 2019 at 7:04 | history | edited | Yota Otachi | CC BY-SA 4.0 |
added 1865 characters in body; edited title
|
| Jun 3, 2019 at 5:05 | history | edited | Yota Otachi | CC BY-SA 4.0 |
added 131 characters in body
|
| Jun 2, 2019 at 13:06 | history | asked | Yota Otachi | CC BY-SA 4.0 |