Spanning Circuits in Regular Matroids
From MaRDI portal
Publication:4973048
DOI10.1145/3355629zbMATH Open1454.68057arXiv1607.05516OpenAlexW2979548720WikidataQ127112331 ScholiaQ127112331MaRDI QIDQ4973048
Daniel Lokshtanov, Petr A. Golovach, Fedor V. Fomin, Saket Saurabh
Publication date: 2 December 2019
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Abstract: 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 Gavenv{c}iak, Kr'al', 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 Gavenv{c}iak, Kr'al', and Oum by showing that for regular matroids - the Minimum Spanning Circuit problem, deciding whether there is a circuit with at most ell elements containing T, is FPT parameterized by k=ell-|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 ell 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.
Full work available at URL: https://arxiv.org/abs/1607.05516
Combinatorial aspects of matroids and geometric lattices (05B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
This page was built for publication: Spanning Circuits in Regular Matroids
