Timeline for Is this graph problem NP-Hard?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Oct 20, 2019 at 12:27 | vote | accept | dineshdileep | ||
| Oct 3, 2019 at 13:46 | comment | added | Elle Najt | You may have more luck here: cstheory.stackexchange.com or here: or.stackexchange.com | |
| Oct 3, 2019 at 13:46 | comment | added | Elle Najt | There is a natural local search or MCMC you can try as a practical approach, although as Bullet51s answer shows it won't always succeed. The states of the chain are your set of $K$ nodes. A move of the Markov chain (or local search) is to randomly update the position of one of the nodes using your objective function. However, since clique is a special case, and clique is hard to approximate you'll need to impose more structure on the graph to prove an approximation bound. Can you solve the problem on trees / bounded treewidth? Anyhow, maybe worth coding and trying MCMC optimization heuristics. | |
| Oct 3, 2019 at 2:46 | answer | added | LeechLattice | timeline score: 5 | |
| Oct 3, 2019 at 0:05 | history | asked | dineshdileep | CC BY-SA 4.0 |