Timeline for how to reduce 3-colorable graph to this? [closed]
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 22, 2014 at 1:37 | history | closed |
Andrés E. Caicedo Dima Pasechnik Ramiro de la Vega abx Chris Godsil |
Not suitable for this site | |
| Nov 21, 2014 at 21:17 | vote | accept | amir veyseh | ||
| Nov 21, 2014 at 19:44 | answer | added | Tony Huynh | timeline score: 1 | |
| Nov 21, 2014 at 15:22 | comment | added | amir veyseh | @AndreasBlass yes i agree with you,I've tried so many ways to produce S from X by G and its edges but all of them failed.really I don't have any idea to how prove it after several hours of thinking about it | |
| Nov 21, 2014 at 15:08 | comment | added | Andreas Blass | I don't think it's a good idea to use the set of vertices of the graph as the X in your problem. The input to 3-coloring (namely the graph) is only polynomially larger than the set of vertices, but the input to your question, including the family S, could be exponentially larger than X. So "PTime" for your problem could be exponential time relative to the size of X. | |
| Nov 21, 2014 at 14:50 | review | Low quality posts | |||
| Nov 21, 2014 at 18:06 | |||||
| Nov 21, 2014 at 14:40 | review | Close votes | |||
| Nov 22, 2014 at 1:37 | |||||
| Nov 21, 2014 at 14:14 | comment | added | amir veyseh | I want to prove that this problem is NP-complete and I guess 3-colorable graph problem is similar to it maybe not.i'm not sure | |
| Nov 21, 2014 at 14:05 | comment | added | Joonas Ilmavirta | Where does this problem come from? Are you looking for an (implementable) algorithm, a solution to a single problem or something else? Why do you think the problem can be reduced to a 3-coloring problem? | |
| Nov 21, 2014 at 14:01 | history | asked | amir veyseh | CC BY-SA 3.0 |