Skip to main content
Share Your Experience: Take the 2024 Developer Survey
2 votes
Accepted

Enumerating all Vertex Covers of Size at most $k$

The algorithm fails in the case, when there are no edges left to cover, because then it does not have a structure to branch on. Consider for example the case where the graph is edgeless, then we have $...
Christian Komusiewicz's user avatar
1 vote
Accepted

What is known about the complexity of Network Diversion?

We have a recent preprint where we show it's polynomial-time on planar graphs: https://arxiv.org/abs/2305.01314. In general graphs, it remains open whether it is polynomial-time or NP-complete. An FPT ...
Laakeri's user avatar
  • 1,786

Only top scored, non community-wiki answers of a minimum length are eligible