Deciding first order properties of matroids

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

Authors 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)

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)

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.

Recommendations

• Decomposition width of matroids
• Decomposition width of matroids
• A Parametrized Algorithm for Matroid Branch-Width
• Tree automata and pigeonhole classes of matroids. I
• Parameterized and Exact Computation

Cited In (7)

• Decomposition width of matroids
• Decomposition width of matroids
• Tree automata and pigeonhole classes of matroids. I
• Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
• First order convergence of matroids
• On the number of circuits in regular matroids (with connections to lattices and codes)
• 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)