Deciding First Order Properties of Matroids

DOI10.1007/978-3-642-31585-5_24zbMATH Open1367.03022arXiv1108.5457OpenAlexW2281935918MaRDI QIDQ3167015FDOQ3167015

Tomáš Gavenčiak, Sang-Il Oum, Daniel Král'

Publication date: 1 November 2012

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: Frick and Grohe [J. ACM 48 (2006), 1184-1206] introduced a notion of graph classes with locally bounded tree-width and established that every first order logic property can be decided in almost linear time in such a graph class. Here, we introduce an analogous notion for matroids (locally bounded branch-width) and show the existence of a fixed parameter algorithm for first order logic properties in classes of regular matroids with locally bounded branch-width. To obtain this result, we show that the problem of deciding the existence of a circuit of length at most k containing two given elements is fixed parameter tractable for regular matroids.

Full work available at URL: https://arxiv.org/abs/1108.5457

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35) Decidability of theories and sets of sentences (03B25)

Cited In (4)

• On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)
• Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming
• First order convergence of matroids
• Covering Vectors by Spaces: Regular Matroids

This page was built for publication: Deciding First Order Properties of Matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167015)