2018arXiv (Cornell University)Open access

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

Maximilian Fürst

Open full text 0 citations

Abstract

If $G(M)$ denotes the subgraph of a graph $G$ induced by the set of vertices that are covered by some matching $M$ in $G$, then $M$ is an induced or a uniquely restricted matching if $G(M)$ is $1$-regular or if $M$ is the unique perfect matching of $G(M)$, respectively. Let $\nu_s(G)$ and $\nu_{ur}(G)$ denote the maximum cardinality of an induced and a uniquely restricted matching in $G$. Golumbic, Hirst, and Lewenstein (Uniquely restricted matchings, Algorithmica 31 (2001) 139-154) posed the problem to characterize the graphs $G$ with $\nu_{ur}(G) = \nu_{s}(G)$. We prove that the corresponding decision problem is NP-hard, which suggests that a good characterization is unlikely to be possible.

Open-access reader

About this research paper

What this paper is about

If $G(M)$ denotes the subgraph of a graph $G$ induced by the set of vertices that are covered by some matching $M$ in $G$, then $M$ is an induced or a uniquely restricted matching if $G(M)$ is $1$-regular or if $M$ is the unique perfect matching of $G(M)$, respectively. Let $\nu_s(G)$ and $\nu_{ur}(G)$ denote the maximum cardinality of an induced and a uniquely restricted matching in $G$. Golumbic, Hirst, and Lewenstein (Uniquely restricted matchings, Algorithmica 31 (2001) 139-154) posed the problem to characterize the graphs $G$ with $\nu_{ur}(G) = \nu_{s}(G)$. We prove that the corresponding decision problem is NP-hard, which suggests that a good characterization is unlikely to be possible.

Why it matters

A significance statement is not available in the OpenAlex record.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

If $G(M)$ denotes the subgraph of a graph $G$ induced by the set of vertices that are covered by some matching $M$ in $G$, then $M$ is an induced or a uniquely restricted matching if $G(M)$ is $1$-regular or if $M$ is the unique perfect matching of $G(M)$, respectively. Let $\nu_s(G)$ and $\nu_{ur}(G)$ denote the maximum cardinality of an induced and a uniquely restricted matching in $G$. Golumbic, Hirst, and Lewenstein (Uniquely restricted matchings, Algorithmica 31 (2001) 139-154) posed the problem to characterize the graphs $G$ with $\nu_{ur}(G) = \nu_{s}(G)$. We prove that the corresponding decision problem is NP-hard, which suggests that a good characterization is unlikely to be possible.

Key concepts: Combinatorics, Matching (statistics), Cardinality (data modeling), Mathematics, Characterization (materials science), Induced subgraph, Graph, Bipartite graph

Related papers

Back to paper searchBrowse research topicsOriginal source
On the hardness of deciding the equality of the induced and the uniquely restricted matching number — Research Paper | ScholarLens