New answers tagged graph-algorithms
3
The problem is NP-complete. We'll make a series of reductions from max-cut to show this.
Problem 0 (your problem): Given a graph $G$, does G have an induced subgraph with at least k vertices, such that all vertices have even degree within the subgraph?
Problem 1: Given a graph $G$ and subset $A$ of vertices, does $G$ have an induced subgraph with at least $...
16
One example: choosing the property "G contains a node that has an edge to all nodes in G" makes P1 trivial in $O(n + m)$ (pick node with largest degree), but makes P2 the problem of finding the minimum size dominating set, which is NP-hard.
Top 50 recent answers are included
