Skip to main content
deleted 30 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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 $\alpha(G \setminus x) < \alpha(G)$$a(G \setminus x) < a(G)$. Note that if $\alpha(G \setminus x) < \alpha(G)$$a(G \setminus x) < a(G)$, then $\alpha(G \setminus x)=\alpha(G)-1$$a(G \setminus x)=a(G)-1$. Therefore, if there were such an algorithm, we could simply run it and then recurse to compute $\alpha(G)$$a(G)$ in polynomial time.

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 $\alpha(G \setminus x) < \alpha(G)$. Note that if $\alpha(G \setminus x) < \alpha(G)$, then $\alpha(G \setminus x)=\alpha(G)-1$. Therefore, if there were such an algorithm, we could simply run it and then recurse to compute $\alpha(G)$ in polynomial time.

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.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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 $\alpha(G \setminus x) < \alpha(G)$. Note that if $\alpha(G \setminus x) < \alpha(G)$, then $\alpha(G \setminus x)=\alpha(G)-1$. Therefore, if there were such an algorithm, we could simply run it and then recurse to compute $\alpha(G)$ in polynomial time.