How to find the maximum subgraph of a bipartite graph with valence constraint?

Unfortunately this is NP-hard, so there are probably no polynomial time algorithms to solve it. Below is an abbreviation for the NP-hard problem Independent Set , where we are given a graph G = (V, E) (with n = | V | and m = | E |) and an integer k, and the task is to determine, is it possible to find a set of k or more vertices in such a way that no two vertices in the set are connected by edges:

• For each vertex v_i in G, create a red vertex r_i in H.
• For each edge (v_i, v_j) in G, create the following in H:
  • black top b_ij,
  • n + 1 red vertices t_ijk (1 <= k <= n + 1),
  • n black vertices u_ijk (1 <= k <= n),
  • n edges (t_ijk, u_ijk) (1 <= k <= n)
  • n edges (t_ijk, u_ij {k-1}) (2 <= k <= n + 1)
  • three edges (r_i, b_ij), (r_j, b_ij) and (t_ij1, b_ij).
• For each pair of vertices v_i, v_j create the following:
  • black top c_ij,
  • two edges (r_i, c_ij) and (r_j, c_ij).
• Set the threshold to m (n + 1) + k.

Call the set of all r_i R, the set of all b_ij B, the set of all c_ij C, the set of all t_ij T and the set of all u_ij U.

The general idea is that we force each black vertex b_ij to select at most 1 of the two red vertices r_i and r_j corresponding to the endpoints of edge (i, j) in G. We do this by giving each of these b_ij vertices 3 outgoing edges , one of which (one for t_ij1) is "mandatory", that is, any solution in which the vertex t_ij1 is not selected can be improved by selecting it, as well as n other red vertices to which it connects (via the "path of disgust" which alternates between vertices at t_ijk and vertices at u_ijk), getting rid of r_i or r_j to restore the property that no black vertex has 3 or more neighbors in the solution, if necessary, and then finally restore the connectivity by choosing the desired vertex from C. (Vertices c_ij are "connectors":they only exist to ensure that any subset of R we include could be turned into one connected component.)

First, assume that there is an IS of size k in G. We will show that there is a connected induced subgraph X with at least m (n + 1) + k red nodes in H, in which every black vertex has most 2 neighbors in X.

First, include in X k vertices from R corresponding to vertices in IS (such a set should exist by assumption). Since these vertices form IS, no vertex in B is adjacent to more than one of them, so for each vertex b_ij we can safely add it, and the "hermit path" 2n + 1 vertices starting from t_ij1 in X as Well. Each of these twist paths contains n + 1 red vertices, and there are m such paths (one for each edge in G), so X now has m (n + 1) + k red vertices. Finally, to ensure that X is connected, add every vertex c_ij to it such that r_i and r_j are already in X: note that this does not change the total number of red vertices in X.

Suppose now that there is a connected induced subgraph X with at least m (n + 1) + k red nodes in H, in which each black vertex has at most two neighbors in X. We will show that there is an IS in G of size k.

The only red vertices in H are those in R and those in T. There are only n vertices in R, so if X does not contain all m wiggly paths, it must have at most (m-1) (n + 1) + n = m (n + 1) -1 red vertices, which contradicts the assumption that it has at least m (n + 1) + k red vertices. So X must contain all m wiggly paths. This leaves k other red vertices in X, which must be from R. None of these vertices can be adjacent to the same vertex in B, since then the B-vertex will be adjacent to three vertices: so these k vertices correspond IS in G.

Since a YES instance of IS implies a YES instance for a constructed instance of your problem and vice versa, the solution of a constructed instance of your problem exactly matches the solution of an IS instance; and since the construction is clearly polynomial, this establishes that your problem is NP-hard.