Matching problems with delta-matroid constraints

Naonori Kakimura, Mizuyo Takamatsu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Given an undirected graph G = (V, E) and a directed graph D = (V, A), the master/slave matching problem is to find a matching of maximum cardinality in G such that for each arc (u; v) ∈ A with u being matched, v is also matched. This problem is known to be NP-hard in general, but polynomially solvable in a special case where the maximum size of a connected component of D is at most two. This paper investigates the master/slave matching problem in terms of delta-matroids, which is a generalization of matroids. We first observe that the above polynomially solvable constraint can be interpreted as delta-matroids. We then introduce a new class of matching problem with delta-matroid constraints, which can be solved in polynomial time. In addition, we discuss our problem with additional constraints such as capacity constraints.

Original languageEnglish
Title of host publicationTheory of Computing 2012 - Proceedings of the Eighteenth Computing
Subtitle of host publicationThe Australasian Theory Symposium, CATS 2012
Number of pages10
Publication statusPublished - 2012
Externally publishedYes
EventTheory of Computing 2012 - 18th Computing: The Australasian Theory Symposium, CATS 2012 - Melbourne, VIC, Australia
Duration: 2012 Jan 312012 Feb 3

Publication series

NameConferences in Research and Practice in Information Technology Series
ISSN (Print)1445-1336


OtherTheory of Computing 2012 - 18th Computing: The Australasian Theory Symposium, CATS 2012
CityMelbourne, VIC


  • Constrained matching
  • Delta-matroid
  • Mixed matrix theory
  • Polynomial-time algorithm

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications
  • Hardware and Architecture
  • Information Systems
  • Software


Dive into the research topics of 'Matching problems with delta-matroid constraints'. Together they form a unique fingerprint.

Cite this