Timeline for Is the graph minicut with the node cardinality constraint NP-hard?
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 15, 2020 at 13:46 | comment | added | smapers | Great, I agree. | |
| Apr 15, 2020 at 13:42 | comment | added | Ben Barber | @smpapers, you're right, that only works if the parts are balanced rather than bounded -- if the partition is into parts of size as equal as possible then they're equivalent because the total number of possible crossing edges is fixed. Happily the reduction I sketch is to balanced max-cut, and so balanced min-cut, which is a special case of bounded min-cut (so the general case is still NP-hard). | |
| Apr 13, 2020 at 12:50 | comment | added | smapers | Could you elaborate your first claim? I imagine something like that to be true, but don't see the exact correspondence. | |
| Mar 14, 2020 at 9:51 | history | answered | Ben Barber | CC BY-SA 4.0 |