7

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 ...


4

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$ ...


Only top voted, non community-wiki answers of a minimum length are eligible