2
$\begingroup$

Let the Edge Cover Equilibrium Problem be the following:

  • INPUT: a simple undirected graph $G$.
  • OUTPUT:
    • YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge covers of $G$ having even cardinality.
    • NO, otherwise.

Question:

Which is the best known algorithm to solve it? Has such problem been investigated in the literature? What do we know about it? Can this equilibrium property be reduced to checking some other property of $G$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.