Finding spanning trees with perfect matchings

Bérczi, Kristóf; Király, Tamás; Kobayashi, Yusuke et al.

Discrete Applied Mathematics, 2025, 371, 137-147

Number of Access:65（2025-08-30 13:55 Counts）

Identifier to cite or link to this item: https://hdl.handle.net/11094/101394

Link to primary information 

File Format Terms of use Size Views Date.Available Description information
DiscreteApplMath_371_137 pdf None 613 KB 19 2025.06.03  
Creative Commons : Attribution

Item Information

Output File Export EndNote Basic Export Mendeley

Title
Finding spanning trees with perfect matchings
Creator
CreatorName
Bérczi, Kristóf
CreatorName
Király, Tamás
NRID
1000040581591 1000040581591
CreatorName
Kobayashi, Yusuke
NRID
1000030780895 1000030780895
researchmap permalink
ygussany ygussany
Scopus Author ID
56508797000 56508797000
CreatorName
Yamaguchi, Yutaro
NRID
1000060805480 1000060805480
CreatorName
Yokoi, Yu
Subject
Algorithm
NP-hardness
Spanning tree
Perfect matching
Description
Bérczi K., Király T., Kobayashi Y., et al. Finding spanning trees with perfect matchings. Discrete Applied Mathematics 371, 137 (2025); https://doi.org/10.1016/j.dam.2025.04.001.
Abstract
We investigate the tractability of a simple fusion of two fundamental structures on graphs, a spanning tree and a perfect matching. Specifically, we consider the following problem: given an edge-weighted graph, find a minimum-weight spanning tree among those containing a perfect matching. On the positive side, we design a simple greedy algorithm for the case when the graph is complete (or complete bipartite) and the edge weights take at most two values. On the negative side, the problem is NP-hard even when the graph is complete (or complete bipartite) and the edge weights take at most three values, or when the graph is cubic, planar, and bipartite and the edge weights take at most two values. We also consider an interesting variant. We call a tree strongly balanced if on one side of the bipartition of the vertex set with respect to the tree, all but one of the vertices have degree 2 and the remaining one is a leaf. This property is a sufficient condition for a tree to have a perfect matching, which enjoys some structural property in addition. When the underlying graph is bipartite, strongly balanced spanning trees can be written as matroid intersection, and this fact was utilized to design approximation algorithms for several NP-hard problems, e.g., the traveling salesman problem and a kind of connectivity augmentation problem. The natural question is its tractability in nonbipartite graphs. As a negative answer, it turns out NP-hard to test whether a given graph has a strongly balanced spanning tree or not even when the graph is subcubic and planar.
Publisher
Elsevier B.V.
Source Title
Discrete Applied Mathematics
Volume (Issue)
371
Page
137-147
Date of Issued
2025-04-11
Language
English
Handle URL
https://hdl.handle.net/11094/101394
PISSN
0166218X
Relation.isIdenticalTo
DOI (Publisher Version)
https://doi.org/10.1016/j.dam.2025.04.001
Access Rights
open access
CopyRight
This article is licensed under a Creative Commons Attribution 4.0 International License.
oaire:version
Version of Record
Category
学術雑誌論文 Journal Article