Even circuits in oriented matroids. (English) Zbl 1498.05047
Summary: 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 cographic matroids in terms of forbidden minors, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen.
MSC:
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C75 | Structural characterization of families of graphs |
| 05C83 | Graph minors |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 52C40 | Oriented matroids in discrete geometry |
References:
| [1] | Robert E. Bixby and William H. Cunningham. Converting linear programs to net-work problems. Math. Oper. Res., 5(3):321-357, 1980. doi:10.1287/moor.5. 3.321. · Zbl 0442.90095 · doi:10.1287/moor.5.3.321 |
| [2] | J. Bang-Jensen and G. Gutin. Digraphs. Springer Monographs in Mathematics. Springer-Verlag London, Ltd., London, 2 edition, 2009. Theory, algorithms and applications. doi:10.1007/978-1-84800-998-1. · Zbl 1170.05002 · doi:10.1007/978-1-84800-998-1 |
| [3] | Robert G. Bland and Michel Las Vergnas. Orientability of matroids. J. Combinato-rial Theory Ser. B, 24(1):94-123, 1978. doi:10.1016/0095-8956(78)90080-1. [BLVS + 99] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler. Oriented matroids, volume 46 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2 edition, 1999. doi:10. 1017/CBO9780511586507. · Zbl 0944.52006 · doi:10.1017/CBO9780511586507 |
| [4] | A. Bachem and A. Reinhold. On the complexity of the farkas-property of oriented matroids. Technical report, University of Cologne, 1989. http://e-archive. informatik.uni-koeln.de/65 Preprint. |
| [5] | Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, 5 edition, 2017. doi:10.1007/978-3-662-53622-3. · Zbl 1375.05002 · doi:10.1007/978-3-662-53622-3 |
| [6] | András Frank andÉva Tardos. An application of simultaneous diophantine ap-proximation in combinatorial optimization. Combinatorica, 7(1):49-65, 1987. doi:10.1007/BF02579200. · Zbl 0641.90067 · doi:10.1007/BF02579200 |
| [7] | Péter Gács and László Lovász. Khachiyan’s algorithm for linear programming. Math. Programming Stud., 14:61-68, 1981. doi:10.1007/bfb0120921. · Zbl 0463.90066 · doi:10.1007/bfb0120921 |
| [8] | Bertrand Guenin and Robin Thomas. Packing directed circuits exactly. Combina-torica, 31(4):397-421, 2011. doi:10.1007/s00493-011-1687-5. · Zbl 1299.05144 · doi:10.1007/s00493-011-1687-5 |
| [9] | L. G. Hačijan. A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR, 244(5):1093-1096, 1979. · Zbl 0414.90086 |
| [10] | D. Hausmann and B. Korte. Algorithmic versus axiomatic definitions of matroids. Math. Programming Stud., 14:98-111, 1981. doi:10.1007/bfb0120924. · Zbl 0449.90066 · doi:10.1007/bfb0120924 |
| [11] | Thor Johnson, Neil Robertson, P. D. Seymour, and Robin Thomas. Directed tree-width. J. Combin. Theory Ser. B, 82(1):138-154, 2001. doi:10.1006/jctb. 2000.2031. · Zbl 1027.05045 · doi:10.1006/jctb.2000.2031 |
| [12] | K. Kawarabayashi and Stephan Kreutzer. The directed grid theorem. In Pro-ceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, page 655-664, New York, NY, USA, 2015. Association for Computing Machinery. arXiv:1411.5681, doi:10.1145/2746539.2746586. · Zbl 1321.05249 · doi:10.1145/2746539.2746586 |
| [13] | Victor Klee, Richard Ladner, and Rachel Manber. Signsolvability revisited. Linear Algebra Appl., 59:131-157, 1984. doi:10.1016/0024-3795(84)90164-2. · Zbl 0543.15016 · doi:10.1016/0024-3795(84)90164-2 |
| [14] | William McCuaig. Pólya’s permanent problem. Electron. J. Combin., 11(1):Re-search Paper 79, 83, 2004. doi:10.37236/1832. · Zbl 1062.05066 · doi:10.37236/1832 |
| [15] | George J. Minty. On the axiomatic foundations of the theories of directed linear graphs, electrical networks, and network programming. J. Math. Mech., 15:485-520, 1966. · Zbl 0141.21601 |
| [16] | Rachel Manber and Jia Yu Shao. On digraphs with the odd cycle property. J. Graph Theory, 10(2):155-165, 1986. doi:10.1002/jgt.3190100203. · Zbl 0593.05032 · doi:10.1002/jgt.3190100203 |
| [17] | James Oxley. Matroid theory, volume 21 of Oxford Graduate Texts in Mathematics. Oxford University Press, Oxford, 2 edition, 2011. doi:10.1093/acprof:oso/ 9780198566946.001.0001. · Zbl 1254.05002 · doi:10.1093/acprof:oso/9780198566946.001.0001 |
| [18] | Neil Robertson, P. D. Seymour, and Robin Thomas. Permanents, pfaffian ori-entations, and even directed circuits. Ann. of Math. (2), 150(3):929-975, 1999. doi:10.2307/121059. · Zbl 0947.05066 · doi:10.2307/121059 |
| [19] | P. D. Seymour. Decomposition of regular matroids. J. Combin. Theory Ser. B, 28(3):305-359, 1980. doi:10.1016/0095-8956(80)90075-1. · Zbl 0443.05027 · doi:10.1016/0095-8956(80)90075-1 |
| [20] | Paul Seymour and Carsten Thomassen. Characterization of even directed graphs. J. Combin. Theory Ser. B, 42(1):36-45, 1987. doi:10.1016/0095-8956(87) 90061-X. · Zbl 0607.05037 · doi:10.1016/0095-8956(87)90061-X |
| [21] | Éva Tardos. A strongly polynomial algorithm to solve combinatorial linear pro-grams. Oper. Res., 34(2):250-256, 1986. doi:10.1287/opre.34.2.250. · Zbl 0626.90053 · doi:10.1287/opre.34.2.250 |
| [22] | Carsten Thomassen. Sign-nonsingular matrices and even cycles in directed graphs. Linear Algebra Appl., 75:27-41, 1986. doi:10.1016/0024-3795(86)90179-5. · Zbl 0589.05050 · doi:10.1016/0024-3795(86)90179-5 |
| [23] | W. T. Tutte. A homotopy theorem for matroids. i, ii. Trans. Amer. Math. Soc., 88:144-174, 1958. doi:10.2307/1993243. · Zbl 0081.17301 · doi:10.2307/1993243 |
| [24] | W. T. Tutte. An algorithm for determining whether a given binary matroid is graphic. Proc. Amer. Math. Soc., 11:905-917, 1960. doi:10.2307/2034435. · Zbl 0097.38905 · doi:10.2307/2034435 |
| [25] | D. J. A. Welsh. Matroid theory. Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. L. M. S. Monographs, No. 8. · Zbl 0343.05002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
