4 votes

3 Matroid Intersection, a Special Case

Your problem is a multi-budgeted matroid intersection with two budgets. There is a PTAS for that [1]. However, your case is so special, better algorithm exists. You can assume there is only a single ...
Chao Xu's user avatar
  • 4,367
1 vote

Is this edge-partitioning NP-Hard?

This question boils down to answering to simpler questions. Can you find a graph with 6 edges where it is impossible to partition the edges? In a graph of more than 6 edges can you always find a ...
Martin Vatshelle's user avatar
1 vote

Complexity and Algorithm for specific Vertex Separator Problem

I understand that the question is about the time bound, not about the correctness of the reduction. The claim does not sound obvious (although a bound of $\mathcal{O}(n^3n^2k)$ can be shown with a ...
Vinicius dos Santos's user avatar

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