1
$\begingroup$

Consider the following problem:

Input: A graph $G=(V,E)$ and a matroid $M$ on $E$, given by an independence oracle.

Task: Find a cut $C\subseteq E$ in the graph, such that the rank of $C$ in the matroid is minimum.

Question: What is known about this problem? Is it solvable in polynomial time?

Note: This is a direct generalization of the minimum cut problem. The latter is well known to be solvable in polynomial time. Since both a matroid and the family of cuts have quite a bit of structure, there might be hope to find a polynomial time algorithm for the generalized problem, as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.