5
$\begingroup$

Is the following problem in P?

We are given a matroid M. Each element in M has a weight encoded using some unary notation. We are also give an integer K also encoded in unary bits. The question is whether there is a base of M that has weight EXACTLY K.

I know the exact spanning tree is in P.

Thanks a lot.

$\endgroup$
7
$\begingroup$

This problem appears to be considered in "Random pseudo-polynomial algorithms for exact matroid problems", P. M. Camerini, G. Galbiati and F. Maffioli, Journal of Algorithms Volume 13, Issue 2, June 1992, Pages 258-273.

They give a randomized polynomial time for the problem, but they seem to be assuming that the input matroid is representable over the reals, rather than allowing arbitrary matroids. They also state that it is unknown whether it is solvable in P.

However, if all elements of M have weight 0 or 1, then it is easy to solve as a matroid intersection problem.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.