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 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 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.
A full version of this contribution is available as arXiv:1108.5457.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Yuster, R., Zwick, U.: Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. In: Proc. STOC 1994, pp. 326–335. ACM (1994)
Courcelle, B.: The monadic second-order logic of graph I. Recognizable sets of finite graphs. Inform. and Comput. 85, 12–75 (1990)
Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic. In: Rozenberg, G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformations. Foundations, vol. 1, pp. 313–400. World Scientific (1997)
Dawar, A., Grohe, M., Kreutzer, S.: Locally excluding a minor. In: Proc. LICS 2007, pp. 270–279. IEEE Computer Society Press (2007)
Downey, R.G., Fellows, M.R., Vardy, A., Whittle, G.: The parametrized complexity of some fundamental problems in coding theory. SIAM J. Comput. 29, 545–570 (1999)
Dvořák, Z., Král’, D., Thomas, R.: Deciding first-order properties for sparse graphs. In: Proc. FOCS 2010, pp. 133–142 (2010)
Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algor. Appli. 3, 1–27 (1999)
Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica 27, 275–291 (2000)
Frick, M., Grohe, M.: Deciding first-order properties of locally tree-decomposable structures. Journal of the ACM 48, 1184–1206 (2001)
Gaifman, H.: On local and non-local properties. In: Proc. of Herbrand Symposium, Logic Colloquium 1981. North-Holland, Amsterdam (1982)
Hliněný, P.: On Matroid Properties Definable in the MSO Logic. In: Rovan, B., Vojtáš, P. (eds.) MFCS 2003. LNCS, vol. 2747, pp. 470–479. Springer, Heidelberg (2003)
Hliněný, P.: A parametrized algorithm for matroid branch-width. SIAM J. Computing 35(2), 259–277 (2005)
Hliněný, P.: Branch-width, parse trees and monadic second-order logic for matroids. J. Combin. Theory Ser. B 96, 325–351 (2006)
Hliněný, P.: On Matroid Representability and Minor Problems. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 505–516. Springer, Heidelberg (2006)
Hliněný, P., Oum, S.: Finding branch-decomposition and rank-decomposition. SIAM J. Computing 38, 1012–1032 (2008)
Hliněný, P., Whittle, G.: Matroid tree-width. European J. Combin. 27, 1117–1128 (2006)
Hliněný, P., Whittle, G.: Addendum to matroid tree-width. European J. Combin. 30, 1036–1044 (2009)
Kawarabayashi, K., Thorup, M.: Minimum k-way cut of bounded size is fixed-parameter tractable. In: Proc. FOCS 2011, pp. 160–169. IEEE (2011)
Oum, S., Seymour, P.: Approximating clique-width and branch-width. J. Combin. Theory, Ser. B 96, 514–528 (2006)
Oxley, J.G.: Matroid theory. Oxford University Press (1992)
Peleg, D.: Distance-dependent distributed directories. Info. Computa. 103, 270–298 (1993)
Robertson, N., Seymour, P.D.: Graph minors X. Obstructions to tree-decompositions. J. Combin. Theory Ser. B 52, 153–190 (1991)
Seymour, P.: Decomposition of regular matroids. J. Combin. Theory Ser. B 28, 305–359 (1980)
Seymour, P.: Recognizing graphic matroids. Combinatorica 1, 75–78 (1981)
Truemper, K.: A decomposition theory for matroids V. Testing of matrix total unimodularity. J. Combin. Theory Ser. B 49, 241–281 (1990)
Truemper, K.: Matroid decomposition. Academic Press (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gavenčiak, T., Král, D., Oum, Si. (2012). Deciding First Order Properties of Matroids. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds) Automata, Languages, and Programming. ICALP 2012. Lecture Notes in Computer Science, vol 7392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31585-5_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-31585-5_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31584-8
Online ISBN: 978-3-642-31585-5
eBook Packages: Computer ScienceComputer Science (R0)