Even circuits in oriented matroids

DOI10.5070/C62156875zbMATH Open1498.05047arXiv2010.08988OpenAlexW4220755252MaRDI QIDQ5052170FDOQ5052170

Authors: Karl Heuer, Raphael Steiner, Sebastian Wiederrecht 

Publication date: 21 November 2022

Published in: Combinatorial Theory (Search for Journal in Brave)

Abstract: In this paper we generalise the even directed cycle problem, which asks whether a given digraph contains a directed cycle of even length, to orientations of regular matroids. We define non-even oriented matroids generalising non-even digraphs, which played a central role in resolving the computational complexity of the even dicycle problem. Then we show that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids. Our main result is a precise characterisation of the class of non-even oriented bond matroids in terms of forbidden minors, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen.

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

Recommendations

• Recognizing Even-Cycle and Even-Cut Matroids
• Strong orientations without even directed circuits
• Even cycles in directed graphs
• Stabilizer theorems for even cycle matroids
• Circuit-cocircuit reversing systems in regular matroids

zbMATH Keywords

oriented matroidscircuitsregular matroidseven cycle problem

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Oriented matroids in discrete geometry (52C40) Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Cites Work

• Oriented Matroids
• Decomposition of regular matroids
• Pólya's permanent problem
• Permanents, Pfaffian orientations, and even directed circuits
• Title not available (Why is that?)
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• Khachiyan’s algorithm for linear programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Directed tree-width
• Title not available (Why is that?)
• Digraphs
• Sign-nonsingular matrices and even cycles in directed graphs
• Signsolvability revisited
• An application of simultaneous diophantine approximation in combinatorial optimization
• Graph theory
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Converting Linear Programs to Network Problems
• Algorithmic versus axiomatic definitions of matroids
• Title not available (Why is that?)
• Characterization of even directed graphs
• Packing directed circuits exactly
• On digraphs with the odd cycle property
• The directed grid theorem

Cited In (6)

• Stabilizer theorems for even cycle matroids
• Circuit-cocircuit reversing systems in regular matroids
• On the number of circuit-cocircuit reversal classes of an oriented matroid
• Recognizing Even-Cycle and Even-Cut Matroids
• Recognizing even-cycle and even-cut matroids
• Strong orientations without even directed circuits

This page was built for publication: Even circuits in oriented matroids

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