3
$\begingroup$

For a given weighted graph $G = (V, E)$, there is a simple algorithm for finding the minimum weight circuit by running Dijkstra's algorithm $|E|$ times.

Also for a matroid $M = (E, I)$ one can use the greedy Rado-Edmonds algorithm to find a basis of minimum weight.

I'm interested whether an algorithm for all weighted binary matroids, not just weighted graphic matroids, exists? Specifically an algorithm polynomial on the size of the ground set, using the independence oracle model?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ providing refs would be good (eg Wikipedia if this is there) $\endgroup$
    – Dima Pasechnik
    Commented Nov 6, 2022 at 21:26

1 Answer 1

Reset to default
2
$\begingroup$

The problem is NP-hard (even in the unweighted case) via a well-known connection to coding theory. Namely, if $A$ is the parity check matrix of a binary linear code $C$, then the distance of $C$ is the size of a shortest circuit in the binary matroid represented by $A$. In The intractability of computing the minimum distance of a code, Vardy proved that computing the distance of a binary linear code is NP-hard.

However, for proper minor-closed classes of binary matroids, Geelen, Gerards, and Whittle conjecture that the problem is solvable in polynomial-time. See the paper Computing girth and cogirth in perturbed graphic matroids or Finding Shortest Circuits in Binary Matroids on the Matroid Union Blog for more information.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ cf. For regular matroids: deciding whether a regular matroid has a circuit of length at most k containing two fixed elements is fixed-parameter tractable. arxiv.org/abs/1108.5457 $\endgroup$
    – Sang-il
    Commented Nov 7, 2022 at 15:14
  • $\begingroup$ @Sang-il Thanks! Hope you're doing well. $\endgroup$
    – Tony Huynh
    Commented Nov 7, 2022 at 19:27

You must log in to answer this question.

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