## Contributed Session Mon.1.H 3012

#### Monday, 10:30 - 12:00 h, Room: H 3012

**Cluster 2: Combinatorial optimization** [...]

### Matching

**Chair: Sigrid Knust**

**Monday, 10:30 - 10:55 h, Room: H 3012, Talk 1**

**Sigrid Knust**

Scheduling sports tournaments on a single court based on special 2-factorizations

**Abstract:**

We consider a sports tournament for an odd number of teams where every team plays exactly two matches in each round and all matches have to be scheduled consecutively on a single court. We construct schedules for any number

of teams minimizing waiting times by using special 2-factorizations of the complete graph (Hamiltonian 2-factorization, solutions to special cases of the Oberwolfach problem).

**Monday, 11:00 - 11:25 h, Room: H 3012, Talk 2**

**Mizuyo Takamatsu**

Matching problems with delta-matroid constraints

**Coauthor: Naonori Kakimura**

**Abstract:**

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)* in *A* with *u* being matched, *v* is also matched. This problem is known to be NP-hard, but polynomially solvable in a special case where the maximum size of a connected component of *D* is at most two.

As a generalization of the above polynomially solvable problem, we introduce a class of the delta-matroid matching problem. In this problem, given an undirected graph *G=(V,E)* and a projection of a linear delta-matroid *(V,F)*, we find a maximum cardinality matching *M* such that the set of the end vertices of *M* belongs to *F*. We first show that it can be solved in polynomial time if the delta-matroid is generic, which enlarges a polynomially solvable class of constrained matching problems. In addition, we design a polynomial-time algorithm when the graph is bipartite and the delta-matroid is defined on one vertex side. This result is extended to the case where a linear matroid constraint is additionally imposed on the other vertex side.

**Monday, 11:30 - 11:55 h, Room: H 3012, Talk 3**

**Michael Kapralov**

On the communication and streaming complexity of maximum bipartite matching

**Coauthors: Ashish Goel, Sanjeev Khanna**

**Abstract:**

Consider the following communication problem. Alice and Bob are given a bipartite graph *G* with *2n* nodes whose edges are partitioned adversarially into two sets. Alice holds the first set, and Bob holds the second set. Alice sends Bob a message that depends only on her part of the graph, after which Bob must output a matching in *G*. What is the minimum size of the message that allows Bob to recover a matching of size at least *(1-ε)* times the maximum matching in *G*, as a function of *n*? The minimum message size is the one-round communication complexity of approximating bipartite matching, which is also a lower bound on the space needed by a one-pass streaming algorithm to obtain a *(1-ε)*-approximation. In this talk we are interested in the best approximation one can obtain with linear communication and space. Prior to our work, only the trivial *1/2* approximation was known.

We show that Alice and Bob can achieve a *2/3*-approximation with a message of linear size, and then build on our techniques to design a *deterministic* streaming *1-1/e* approximation in a single pass for the case of vertex arrivals. Finally, we show that both results are best possible.