6
$\begingroup$

Definition: A matching in a graph $G$ is a subgraph consisting of pairwise disjoint edges. If the subgraph is an induced subgraph, the matching is an induced matching. The largest size of an induced matching in $G$ is called its induced matching number and denoted by $a(G)$.

Let $G$ be a bipartite graph. Is it possible to characterize the set of vertices $x$ of $G$ such that $a(G \setminus x)<a(G)$ ?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Would you please be more specific: are you asking "send me all characterizations of this set that you happen to know" (at one extreme there is is always the tautological one, at the other there is always the 'discrete characterization' consisting of the list of all such sets---of course, both are maximally unenlightening), or are you asking for a specific type of characterization? @selva $\endgroup$
    – Peter Heinig
    Commented May 23, 2017 at 7:42
  • 2
    $\begingroup$ Tangential comment on the topic of induced matchings being more complicated than matchings: while many objects attached to matchings can be efficiently found for bipartite graphs, it was proved by L.J. Stockmeyer, V.V. Vazirani, and K. Cameron around thirty years ago that even restricted to bipartite graphs, it is an NP-complete problem to find a maximum induced matching in a given graph. Intuitively: the hardness of the maximum-independent-set problem infects the induced-matching problem. I recognize that your question is not about the set of maximum matchings (though closely related to it). $\endgroup$
    – Peter Heinig
    Commented May 23, 2017 at 7:57
  • 1
    $\begingroup$ And on the topic of your question being too general: a nearly-tautological answer would be "Let $\mathfrak{M}$ denote the set of all largest induced matchings of $G$. Then $x\in V(G)$ is a vertex with the property $a(G\setminus x)<a(G)$ if and only if $x \in \bigcap_{\mathcal{M}\in\mathfrak{M}} (\cup\mathcal{M})$." This is a characterization of sorts. Since $\mathfrak{M}$ can be expected to typically have little humanly understandable structure (whatever that means), this is not an enlightening characterization, though. $\endgroup$
    – Peter Heinig
    Commented May 23, 2017 at 8:03

1 Answer 1

Reset to default
3
$\begingroup$

It is unlikely that a nice characterization exists because the problem of computing the size of a maximum induced matching is a well-known NP-hard problem, even for bipartite graphs (as mentioned by Peter Heinig). Therefore, unless P=NP, there is no polynomial-time algorithm that can test if a given vertex $x$ satisfies $a(G \setminus x) < a(G)$. Note that if $a(G \setminus x) < a(G)$, then $a(G \setminus x)=a(G)-1$. Therefore, if there were such an algorithm, we could simply run it and then recurse to compute $a(G)$ in polynomial time.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .