Timeline for Transitive feedback arc set (TFAS): NP-complete?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 1, 2014 at 22:51 | comment | added | dspyz | I found one with nine vertices. See the updated answer | |
| Feb 1, 2014 at 20:02 | comment | added | G. Bach | @dspyz Thank you very much for putting this much effort into this! I was quite a bit confused since just like you, I couldn't see an error in the construction. At least that bit is settled, then. | |
| Feb 1, 2014 at 19:10 | comment | added | dspyz | I'm sorry. I constructed the graph wrong. I fixed it and clingo now reports no TFAS. | |
| Jan 30, 2014 at 14:02 | comment | added | G. Bach | @dspyz I thought the construction was clearer than just a list of the edges, since if my reasoning isn't wrong, all that would be required to verify is whether the tournament above the construction actually has those implication properties. Thanks for pointing out the mistake about edge (3,6)! I also got 8 TFAS for that gadget, the one you listed being one of them. | |
| Jan 30, 2014 at 14:00 | history | edited | G. Bach | CC BY-SA 3.0 |
edited body
|
| Jan 30, 2014 at 6:32 | comment | added | dspyz | I figured it out, see my updated answer: cstheory.stackexchange.com/a/20778/13643 | |
| Jan 30, 2014 at 5:20 | comment | added | dspyz | I just noticed you mentioned the edge (6,3) in the gadget graph, but the image you provided has the edge (3,6) | |
| Jan 30, 2014 at 4:13 | comment | added | dspyz | I'm sorry, I don't follow. Is there any reason you can't just post a list of the edges so I can run it through an ASP solver and try to verify it? According to clingo, your gadget graph has 8 different TFAS's. Here's the smallest one: tfas(edge(5,0)) tfas(edge(6,0)) tfas(edge(7,0)) tfas(edge(6,2)) tfas(edge(7,3)) tfas(edge(1,2)) tfas(edge(1,3)) tfas(edge(7,5)) | |
| Jan 30, 2014 at 2:30 | history | edited | G. Bach | CC BY-SA 3.0 |
added 46 characters in body
|
| Jan 30, 2014 at 2:10 | history | answered | G. Bach | CC BY-SA 3.0 |