3
$\begingroup$

Smallest vertex cover which is also an independent set asks about finding an independent set that covers all edges. This problem is known as the independent vertex cover problem and is equivalent to finding if the graph is bipartite.

I am wondering if the following follow-up problem has a name, or has been studied.

If the graph does not have an independent vertex cover (i.e., all edges cannot be covered by an independent set), what is the maximum number of edges that can be covered by an independent subset of vertices, and how does one find such a subset? (an edge is counted if and only if it has (exactly) one endpoint connected to a vertex in the subset).

Thanks!

Improve this question
$\endgroup$
1
  • $\begingroup$ Just a guess: Partial Independent Vertex Cover? $\endgroup$
    – daniello
    Oct 6, 2016 at 5:35

0

Reset to default

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.