On Maximum Cost $K_{t,t}$‐Free t ‐Matchings of Bipartite Graphs
Márton Makai · SIAM Journal on Discrete Mathematics · 2007
Frank examined the maximum $K_{t,t}$‐free t‐matching problem of simple bipartite graphs. As the $C_6$‐free 2‐matching problem is NP‐hard (Geelen), this is a promising generalization of restricted 2‐matchings. Given an arbitrary family $\mathcal{T}$ of $K_{t,t}$‐subgraphs of the underlying graph, a $\mathcal{T}$‐free t‐matching is a subgraph of maximum degree at most t that contains no member of $\mathcal{T}$. We show that the maximum size $\mathcal{T}$‐free t‐matching problem also admits a nice min‐max formula. Given an integer cost function on the edge‐set which is vertex‐induced on any member of $\mathcal{T}$, we also show an integer min‐max formula for the maximum cost of $\mathcal{T}$‐free t‐matchings. As the maximum cost $C_4$‐free 2‐matching problem is NP‐hard (Király), we cannot expect a nice characterization in general.