Finding spanning trees with perfect matchings

Bérczi, Kristóf; Király, Tamás; Kobayashi, Yusuke; Yamaguchi, Yutaro; Yokoi, Yu

doi:https://doi.org/10.1016/j.dam.2025.04.001

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

アクセス数:65件（2025-08-30 08:07 集計）

固定URL: https://hdl.handle.net/11094/101394

閲覧可能ファイル

ファイル	フォーマット	利用条件	サイズ	閲覧回数	利用開始日	説明	information
DiscreteApplMath_371_137	pdf	なし	613 KB	18	2025.06.03

Creative Commons : 表示

論文情報

ファイル出力 EndNote Basic出力 Mendeley出力

タイトル	Finding spanning trees with perfect matchings
著者	著者名 Bérczi, Kristóf
	著者名 Király, Tamás
	NRID 1000040581591 1000040581591 著者名 Kobayashi, Yusuke
	NRID 1000030780895 1000030780895 researchmap permalink ygussany ygussany Scopus Author ID 56508797000 56508797000 著者名 Yamaguchi, Yutaro
	NRID 1000060805480 1000060805480 著者名 Yokoi, Yu
キーワード等	Algorithm
	NP-hardness
	Spanning tree
	Perfect matching
内容	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.
抄録	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.
出版者	Elsevier B.V.
収録物名	Discrete Applied Mathematics
巻(号)	371
ページ	137-147
刊行年月	2025-04-11
言語	英語
ハンドルURL	https://hdl.handle.net/11094/101394
PISSN	0166218X
関連情報 (isIdenticalTo)	DOI (出版社版) https://doi.org/10.1016/j.dam.2025.04.001
アクセス権	open access
権利情報	This article is licensed under a Creative Commons Attribution 4.0 International License.
出版タイプ	Version of Record
カテゴリ	学術雑誌論文 Journal Article

資源タイプ	学術雑誌論文
ローカル資源タイプ	学術雑誌論文
DCMI資源タイプ	text
DCTERMS.bibliographicCitation	Discrete Applied Mathematics. 2025, 371, p. 137-147
DC.title	Finding spanning trees with perfect matchings
DC.creator	Bérczi, Kristóf
	Király, Tamás
	Kobayashi, Yusuke
	Yamaguchi, Yutaro
	Yokoi, Yu
DC.publisher	Elsevier B.V.
DC.language' scheme='DCTERMS.RFC1766	英語
DC.type' scheme='DCTERMS.DCMIType	text
DCTERMS.issued' scheme='DCTERMS.W3CDTF	2025-04-11
DC.identifier	https://doi.org/10.1016/j.dam.2025.04.001
DC.subject	Algorithm
	NP-hardness
	Spanning tree
	Perfect matching
DC.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.
DCTERMS.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.
DC.rights	This article is licensed under a Creative Commons Attribution 4.0 International License.
DC.format	101394
citation_title	Finding spanning trees with perfect matchings
citation_author	Bérczi, Kristóf
	Király, Tamás
	Kobayashi, Yusuke
	Yamaguchi, Yutaro
	Yokoi, Yu
citation_publisher	Elsevier B.V.
citation_language	英語
citation_date	2025-04-11
citation_journal_title	Discrete Applied Mathematics
citation_volume	371
citation_firstpage	137
citation_lastpage	147
citation_doi	https://doi.org/10.1016/j.dam.2025.04.001
citation_public_url	https://hdl.handle.net/11094/101394

Finding spanning trees with perfect matchings

閲覧可能ファイル

論文情報

論文詳細を表示