On the hardness of deciding the equality of the induced and the uniquely restricted matching number

DOI10.1016/j.ipl.2019.03.011zbMath1473.05291arXiv1812.09038OpenAlexW2906557035MaRDI QIDQ2414056

Yanyan Li

Publication date: 10 May 2019

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityuniquely restricted matchinginduced matchingstrong matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Acyclic matchings in graphs of bounded maximum degree

Cites Work

• Unnamed Item
• NP-completeness of some generalizations of the maximum matching problem
• Induced matchings
• Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
• A lower bound on the acyclic matching number of subcubic graphs
• Lower bounds on the uniquely restricted matching number
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• Generalized subgraph-restricted matchings in graphs
• Maximum induced matchings close to maximum matchings
• XSAT and NAE-SAT of linear CNF classes
• Equality of distance packing numbers
• The graphs with maximum induced matching and maximum matching the same size
• Graphs in which some and every maximum matching is uniquely restricted
• Paths, Trees, and Flowers
• Uniquely restricted matchings