Matching orderable and separable hypergraphs

DOI10.1007/S11590-022-01854-0MaRDI QIDQ2136876zbMATH OpenOpenAlexFDO

Authors Shmuel Onn

Publication date 16 May 2022

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.00902

zbMATH Keywords

combinatorial optimizationhypergraphmatchingthreshold graph

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: A perfect matching in a hypergraph is a set of edges that partition the set of vertices. We study the complexity of deciding the existence of a perfect matching in orderable and separable hypergraphs. We show that the class of orderable hypergraphs is strictly contained in the class of separable hypergraphs. Accordingly, we show that for each fixed $k$, deciding perfect matching for orderable $k$-hypergraphs is polynomial time doable, but for each fixed $kgeq3$, it is NP-complete for separable hypergraphs.

Recommendations

• On matchings in hypergraphs
• On a criterion for matchability in hypergraphs
• A condition for matchability in hypergraphs
• On a hypergraph matching problem
• On the ordering of graphs with respect to their matching numbers
• On the ordering of a class of graphs with respect to their matching numbers
• On ordering of complements of graphs with respect to matching numbers
• On ordering of complements of graphs with respect to matching numbers
• Separable and equatable hypergraphs
• Matching of given sizes in hypergraphs

Cites work

• A condition for matchability in hypergraphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Santa claus meets hypergraph matchings
• Threshold graphs and related topics

Cited in

(1)

• Separable and equatable hypergraphs

This page was built for publication: Matching orderable and separable hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136876)