Abstract
For a bipartite graph G we consider the problem of finding a maximum size/weight squarefree 2matching and its generalization  the problem of finding a maximum size/weight K_{t,t}free tmatching, where t is an integer greater than two and K_{t,t} denotes a bipartite clique with t vertices on each of the two sides. Since the weighted versions of these problems are NPhard in general, we assume that the weights are vertexinduced on any subgraph isomorphic to K_{t,t}. We present simple combinatorial algorithms for these problems. Our algorithms are significantly simpler and faster than those previously known. We dispense with the need to shrink squares and, more generally subgraphs isomorphic to K_{t,t}, the operation which occurred in all previous algorithms for such tmatchings and instead use socalled halfedges. A halfedge of edge e is, informally speaking, a half of e containing exactly one of its endpoints.
Additionally, we consider another problem concerning restricted matchings. Given a (not necessarily bipartite) graph G = (V,E), a set of k subsets of edges E₁, E₂, …, E_k and k natural numbers r₁, r₂, …, r_k, the Restricted Matching Problem asks to find a maximum size matching of G among such ones that for each 1 ≤ i ≤ k, M contains at most r_i edges of E_i. This problem is NPhard even when G is bipartite. We show that it is solvable in polynomial time if (i) for each i the graph G contains a clique or a bipartite clique on all endpoints of E_i; in the case of a bipartite clique it is required to contain E_i and (ii) the sets E₁, …, E_k are almost vertexdisjoint  the endpoints of any two different sets have at most one vertex in common.
BibTeX  Entry
@InProceedings{paluch_et_al:LIPIcs.ESA.2021.73,
author = {Paluch, Katarzyna and Wasylkiewicz, Mateusz},
title = {{Restricted tMatchings via HalfEdges}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {73:173:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772044},
ISSN = {18688969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14654},
URN = {urn:nbn:de:0030drops146541},
doi = {10.4230/LIPIcs.ESA.2021.73},
annote = {Keywords: restricted 2matchings}
}
Keywords: 

restricted 2matchings 
Collection: 

29th Annual European Symposium on Algorithms (ESA 2021) 
Issue Date: 

2021 
Date of publication: 

31.08.2021 