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

2018/12/21 by Maximilian Fürst, Fürst, Maximilian
Computer Science · Mathematics · Medicine · Neuroscience · #05C70 #Advanced Graph Theory Research #Chronic Myeloid Leukemia Treatments #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory #Nuclear Receptors and Signaling

paper · pdf · doi:10.48550/arxiv.1812.09038

openalex publication_date 2018/12/21 · openalex created_date 2025/11/01 · openalex updated_date 2026/07/28

Abstract

If G(M) denotes the subgraph of a graph G induced by the set of vertices\nthat are covered by some matching M in G, then M is an induced or a\nuniquely restricted matching if G(M) is 1-regular or if M is the unique\nperfect matching of G(M), respectively. Let \ν_s(G) and \ν_ur(G)\ndenote the maximum cardinality of an induced and a uniquely restricted matching\nin G. Golumbic, Hirst, and Lewenstein (Uniquely restricted matchings,\nAlgorithmica 31 (2001) 139-154) posed the problem to characterize the graphs\nG with \ν_ur(G) = \ν_s(G). We prove that the corresponding decision\nproblem is NP-hard, which suggests that a good characterization is unlikely to\nbe possible.\n

Related

• On the equality of the induced matching number and the uniquely restricted matching number for subcubic graphs
• Graphs in which some and every maximum matching is uniquely restricted
• Some bounds on the uniquely restricted matching number
• Uniquely Restricted Matchings in Interval Graphs
• Determining All Maximum Uniquely Restricted Matching in Bipartite Graphs