• This event has passed.

# Cheolwon Heo (허철원), The complexity of the matroid-homomorphism problems

## May 2 Monday @ 4:30 PM - 5:30 PM KST

Room B332, IBS (기초과학연구원)

### Speaker

Cheolwon Heo (허철원)
Applied Algebra and Optimization Research Center (AORC), Sungkyunkwan University

In this talk, we introduce homomorphisms between binary matroids that generalize graph homomorphisms. For a binary matroid $N$, we prove a complexity dichotomy for the problem $\rm{Hom}_\mathbb{M}(N)$ of deciding if a binary matroid $M$ admits a homomorphism to $N$. The problem is polynomial-time solvable if $N$ has a loop or has no circuits of odd length, and is otherwise $\rm{NP}$-complete. We also get dichotomies for the list, extension, and retraction versions of the problem.
This is joint work with Hyobin Kim and Mark Siggers at Kyungpook National University.

## Details

Date:
May 2 Monday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:
, ,

Room B332