The complexity of the matroid homomorphism problem

DOI10.37236/11119MaRDI QIDQ6162136zbMATH OpenFDO

Authors Cheolwon Heo, Hyobin Kim, Siggers Mark

Publication date 15 June 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/11119

zbMATH Keywords

binary matroidmatroid homomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• A note on maxflow-mincut and homomorphic equivalence in matroids
• Complexity of tree homomorphisms
• On the complexity of matroid isomorphism problem
• On the Complexity of Matroid Isomorphism Problems
• scientific article; zbMATH DE number 878894

Cites work

• 2-Isomorphic Graphs
• A proof of the CSP dichotomy conjecture
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• Bi‐arc graphs and the complexity of list homomorphisms
• List homomorphisms to reflexive graphs
• On the complexity of H-coloring
• Testing linear-invariant non-linear properties

Cited in

(5)

• On the Complexity of Some Enumeration Problems for Matroids
• Matroid Complexity and Nonsuccinct Descriptions
• On the Complexity of Matroid Isomorphism Problems
• On the complexity of matroid isomorphism problem
• A note on maxflow-mincut and homomorphic equivalence in matroids

This page was built for publication: The complexity of the matroid homomorphism problem

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