{"ID":2848248,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.26975","arxiv_id":"2510.26975","title":"Constructive Characterization and Recognition Algorithm for Grafts with a Connected Minimum Join","abstract":"Minimum joins in a graft $(G, T)$, also known as minimum $T$-joins of a graph $G$, are said to be connected if they determine a connected subgraph of $G$. Grafts with a connected minimum join have gained interest ever since Middendorf and Pfeiffer showed that they satisfy Seymour's min-max formula for joins and $T$-cut packings; that is, in such grafts, the size of a minimum join is equal to the size of a maximum packing of $T$-cuts. In this paper, we provide a constructive characterization of grafts with a connected minimum join. We also obtain a polynomial time algorithm that decides whether a given graft has a connected minimum join and, if so, outputs one. Our algorithm has two bottlenecks; one is the time required to compute a minimum join of a graft, and the other is the time required to solve the single-source all-sink shortest path problem in a graph with conservative $\\pm 1$-valued edge weights. Thus, our algorithm runs in $O(n(m + n\\log n) )$ time. In the nondense case, it improves upon the time bound for this problem due to Sebő and Tannier that was introduced as an application of their results on metrics on graphs.","short_abstract":"Minimum joins in a graft $(G, T)$, also known as minimum $T$-joins of a graph $G$, are said to be connected if they determine a connected subgraph of $G$. Grafts with a connected minimum join have gained interest ever since Middendorf and Pfeiffer showed that they satisfy Seymour's min-max formula for joins and $T$-cut...","url_abs":"https://arxiv.org/abs/2510.26975","url_pdf":"https://arxiv.org/pdf/2510.26975v1","authors":"[\"Nanano Kita\"]","published":"2025-10-30T19:59:34Z","proceeding":"cs.DM","tasks":"[\"cs.DM\",\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}