# Tag Info

What you look for in question Q1 is known as an $f$-factor of the graph. Here $f$ is a non-negative integer valued function on the vertices, $f(v)$ specifying the degree we want in the subgraph at vertex $v$. Q2 is looking for a so called $(g,f)$ factor, where $g(v)$ is a lower bound and $f(v)$ is an upper bound on the degree of the sought subgraph at each ...
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 $... 3 I recently worked on a research paper that answers your questions - specifically, if we have a$k$-regular graph$G$(each vertex in$G$has degree$k$), and a set$S \subseteq \{1, ..., k\}$, what is the complexity of finding a subset of edges of$G$such that each vertex in$G$has degree in$S$? More formally, what is the complexity of finding an$S$-... 3 The case where$\epsilon$is a fixed constant in$(0,1)$represents a partition that each part contains at least a constant fraction of the vertices. This was proven to be NP-complete by Wagner and Wagner. This is also known as balanced minimum cut problem. Note that$|V_i| \leq (1+\epsilon)|V|/2$if and only if$|V_i| \ge (1-\epsilon)|V|/2$for$\epsilon\$ ...