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 ...
- 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 ...
- 1,339
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 ...
- 1,868
Only top scored, non community-wiki answers of a minimum length are eligible