{
  "id": "1708.00582",
  "version": "v1",
  "published": "2017-08-02T02:42:43.000Z",
  "updated": "2017-08-02T02:42:43.000Z",
  "title": "Excluded $t$-factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-matchings, and Matroids",
  "authors": [
    "Kenjiro Takazawa"
  ],
  "comment": "23 pages, 7 figures, A preliminary version of this paper appears in Proceedings of the 19th IPCO (2017)",
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.DS"
  ],
  "abstract": "We propose a framework for optimal $t$-matchings excluding the prescribed $t$-factors in bipartite graphs. The proposed framework is a generalization of the nonbipartite matching problem and includes several problems, such as the triangle-free $2$-matching, square-free $2$-matching, even factor, and arborescence problems. In this paper, we demonstrate a unified understanding of these problems by commonly extending previous important results. We solve our problem under a reasonable assumption, which is sufficiently broad to include the specific problems listed above. We first present a min-max theorem and a combinatorial algorithm for the unweighted version. We then provide a linear programming formulation with dual integrality and a primal-dual algorithm for the weighted version. A key ingredient of the proposed algorithm is a technique to shrink forbidden structures, which corresponds to the techniques of shrinking odd cycles, triangles, squares, and directed cycles in Edmonds' blossom algorithm, a triangle-free $2$-matching algorithm, a square-free $2$-matching algorithm, and an arborescence algorithm, respectively.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-08-02T02:42:43.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "bipartite graphs",
      "unified framework",
      "matching algorithm",
      "shrink forbidden structures",
      "triangle-free"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}