Given an undirected graph $G = (V, E)$ and an integer $k$, is there a partition of the vertices into two (nonempty, nonoverlapping) subsets so that $k$ or more edges have one end in each subset?

I'm a little confused on showing how the problem is NP, in terms of a certificate and certifier.


2 Answers 2


The certificate is a coloring of the vertices into red and blue (i.e., a partition into two sets). Given such a certificate, you can iterate through all the edges and count the number of edges whose endpoints have different colors. This count you can compare against $k$ and answer accordingly YES or NO.

  • $\begingroup$ Would the certifier/verifier just be a comparison of the count of number of edges and k, so something like verifier v(Count, k)? and what would the length of the certificate be? I'm thinking it would just be a number as it is the number of vertices right? $\endgroup$
    – anon.g
    Mar 13, 2019 at 19:35
  • $\begingroup$ @anon.g The certificate has say a number 0 or 1 for each vertex, so it has length linear in the number of vertices. This is given to the verifier, which runs in time linear in the number of edges: check each edge, increment count if necessary, and at the end do the comparison against $k$. $\endgroup$
    – Juho
    Mar 13, 2019 at 19:40

Problems that ask “is there an X with property Y” are very often in NP: If it is possible to show in polynomial time that an X has property Y, but also if for every X with property Y there is a proof that it has property Y that can be checked in polynomial time (this covers those cases where a proof that X has property Y is itself hard to find).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.