Even circuits in oriented matroids

DOI10.5070/C62156875MaRDI QIDQ5052170zbMATH OpenOpenAlexFDO

Authors Karl Heuer, Raphael Steiner, Sebastian Wiederrecht

Publication date 21 November 2022

Published in Combinatorial Theory (Search for Journal in Brave)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 3133252 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 3227800 (Why is no real title available?)
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• Algorithmic versus axiomatic definitions of matroids
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• An application of simultaneous diophantine approximation in combinatorial optimization
• Characterization of even directed graphs
• Converting Linear Programs to Network Problems
• Decomposition of regular matroids
• Digraphs
• Directed tree-width
• Graph theory
• Khachiyan’s algorithm for linear programming
• On digraphs with the odd cycle property
• Oriented Matroids
• Packing directed circuits exactly
• Permanents, Pfaffian orientations, and even directed circuits
• Pólya's permanent problem
• Sign-nonsingular matrices and even cycles in directed graphs
• Signsolvability revisited
• 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)