2016/07/19 by Fedor V. Fomin, Fomin, Fedor V., Petr A. Golovach +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1607.05516
openalex publication_date 2016/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the fundamental Matroid Theory problem of finding a circuit in a matroid spanning a set T of given terminal elements. For graphic matroids this corresponds to the problem of finding a simple cycle passing through a set of given terminal edges in a graph. The algorithmic study of the problem on regular matroids, a superclass of graphic matroids, was initiated by Gavenčiak, Král', and Oum [ICALP'12], who proved that the case of the problem with |T|=2 is fixed-parameter tractable (FPT) when parameterized by the length of the circuit. We extend the result of Gavenčiak, Král', and Oum by showing that for regular matroids - the Minimum Spanning Circuit problem, deciding whether there is a circuit with at most ℓ elements containing T, is FPT parameterized by k=ℓ-|T|; - the Spanning Circuit problem, deciding whether there is a circuit containing T, is FPT parameterized by |T|. We note that extending our algorithmic findings to binary matroids, a superclass of regular matroids, is highly unlikely: Minimum Spanning Circuit parameterized by ℓ is W[1]-hard on binary matroids even when |T|=1. We also show a limit to how far our results can be strengthened by considering a smaller parameter. More precisely, we prove that Minimum Spanning Circuit parameterized by |T| is W[1]-hard even on cographic matroids, a proper subclass of regular matroids.