Timeline for Computing the chromatic polynomial of graph modulo $x-3$
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jul 31, 2014 at 15:05 | history | bounty ended | CommunityBot | ||
| S Jul 31, 2014 at 15:05 | history | notice removed | CommunityBot | ||
| Jul 29, 2014 at 14:17 | history | edited | joro | CC BY-SA 3.0 |
Asked for record
|
| S Jul 23, 2014 at 13:45 | history | bounty started | joro | ||
| S Jul 23, 2014 at 13:45 | history | notice added | joro | Draw attention | |
| Jul 23, 2014 at 13:40 | history | edited | joro | CC BY-SA 3.0 |
added 382 characters in body
|
| Jul 22, 2014 at 11:52 | comment | added | joro | @Jernej I don't think the deletion will work. It terminates in trees, not in cliques. Trees are 2-colorable and don't see how to terminate early. Do you see such way? | |
| Jul 22, 2014 at 11:43 | comment | added | Jernej | @Joro. Question - given that you work with 4-regular graphs, isn't it faster to use the edge deleting recursion? I am not sure you can say anything about the time complexity from the execution on instances of a concrete size since run time may as well be a function that "behaves" as a polynomial up to a certain fixed threshold . | |
| Jul 22, 2014 at 11:41 | comment | added | joro | @Jernej I mean the number of calls in the recursion appear polynomial to me. Exponential in 300 will take long. Exponential in 4-regular 4-chromatic order 75 too, though in practice this is fast. Did you notice the link to sage code? | |
| Jul 22, 2014 at 11:33 | comment | added | joro | @Jernej Thanks. I don't want isomorphism. The current sage implementation does 300 vertices 4 regular in about minute. Appears to me hardest are 4-chromatic, though they seem polynomial to me too. | |
| Jul 22, 2014 at 11:28 | comment | added | Jernej | @Joro, Btw, a way to speed up such recursion is to cache graphs, see how this is done for the chromatic polynomial to gain an extreme speedup trac.sagemath.org/ticket/14529 Though this introduces the isomorphism problem and breaks complexity analysis. | |
| Jul 22, 2014 at 10:55 | comment | added | joro | @Jernej What is the fastest way say in Boost to find induced diamonds (K_4 minus edge)? | |
| Jul 22, 2014 at 10:30 | comment | added | Jernej | Errr, I missed that one sorry. | |
| Jul 21, 2014 at 11:59 | comment | added | Emil Jeřábek | Recursion to instances smaller by an additive constant is the standard technique for beating the obvious brute-force search algorithm for a wide variety of NP-hard problems. It normally leads to runtimes of the form $c^n$. Are you familiar with state-of-the-art 3-colouring algorithms such as sciencedirect.com/science/article/pii/S0020019010003595 , ics.uci.edu/~eppstein/pubs/Epp-SODA-01.pdf ? | |
| Jul 21, 2014 at 11:49 | comment | added | joro | Very related question on cstheory: cstheory.stackexchange.com/questions/25299/… | |
| Jul 21, 2014 at 10:36 | history | asked | joro | CC BY-SA 3.0 |