<p>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.</p>

<p>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.</p>

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

CC BY-SA 2.5
2010-12-02T23:30:27.530Z
2010-12-02T23:38:39.300Z
2010-12-02T23:38:39.300Z
David Eppstein
<p>Is the following problem in P?</p>

<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.</p>

<p>I know the exact spanning tree is in P. </p>

<p>Thanks a lot.</p>

<ds.algorithms><complexity-classes>
Exact version of matroid, given the input weight is in unary.
jian
# Exact version of matroid, given the input weight is in unary.

(Asked by: username_0 on 2010-12-02)

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.

**Tags:** ds.algorithms, complexity-classes


---

## 1 answers

### Answer by username_1 on 2010-12-02. Score: 8 | Accepted answer

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.


---

