3
$\begingroup$

Is the shortest circuit/cocircuit problem on transversal matroids or gammoids NP-hard? Is there anything known about this? It is known that the shortest circuit on binary matroid is NP-hard. But I can not find any reference on transversal matroids or gammoids.

This is a followup question of A minimum set hitting every base of a matroid

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The shortest circuit problem for Transversal matroids is NP-hard, by a reduction from Clique. See Theorem 2.1 in "Reliable Assignments of Processors to Tasks and Factoring on Matroids" by Charles J. Colbourn and Ehab S. Elmallah ( http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.6967 ).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .