bounded outdegree bipartite spanners

Question

Given an undirected graph $G = (V,E)$ and an integer $k > 0$, our objective is to find a subgraph $G' = (V ,E')$ where $E' \subseteq E$ such that $G'$ has the three following properties :

• $G'$ is connected. (property $p _1$: connected)
• The vertices of $G'$ are divided into two disjoint subsets $S$ and $T$ ($S \cup T = V$).
• No pair of nodes in $S$ are neighbors in $G'$. The same applies for $T$. (property $p _2$ bipartite). [Note that they can be neighbors in $G$ - but we then eliminate the edge between them when constructing $G'$]
• The nodes in $S$ are degree limited. (property $p _3$ call it outdegree bounded)

The problem seems to be NP-Complete, but I found no solution so far.

---

Here are some of my observations:

• essentially, we are looking for a connected subgraph $G'$ that contains a dominating set $S$ such that every node in $S$ in $G'$ is degree limited to $k$. [and we need to know $S$ too]. [and no pair of nodes in $S$ are neighbors in $G'$]
• $G'$ with $p _1$ and $p _2$ is easily obtained with a rooted spanning tree algorithm + 2-coloring of tree.
• $G'$ with $p _1$ and $p _3$ is easily obtained with a rooted spanning tree algorithm + every node in the tree points to its parent.
• $G'$ with $p_2$ and $p_3$ is trivial, (note that we are looking for any subgraph with the required properties!)
• A close problem to this is the bounded degree spanning tree problem [proven to be NP-Complete with a reduction to Hamiltonian path]
• I see the problem sometimes as a set cover problem. Find any set cover $C$ + restrict the size of each set in $C$ to at most $k$ while keeping the coverage and connectivity properties. [I did not know how to use this observation though]

PS: I am trying to forget it but it always come back to my mind

Answer 1

Perhaps this is a possible weird reduction from 3SAT. The idea is to use the set $S$ with restricted degree to simulate a true/false assignment to the variables using their odd/even distance from the clauses that contain them.

Given a 3CNF formula with $n$ variables; let $c$ be the maximum among the number of occurrences of the variables in the clauses, and let $k = c+2$.

Build $G$ in the following way:

• add a source node $s^T$ linked with $k+1$ nodes of degree 1 (a "fan");
• for every variable $x_i$ add a triangle made of three nodes $\{x_i^S,x_i^+,x_i^-\}$ and edges $(x_i^S,x_i^+)$ (left side), $(x_i^S,x_i^-)$ (base), $(x_i^+,x_i^-)$ (right side);
• add edges from $s^T$ to every $x_i^S$;
• add $k-2$ fan nodes to $x_i^S$;
• for every clause $C_j$ add a node $C_j^T$ linked with $k+1$ fan nodes of degree 1;
• if positive variable $x_k \in C_j$ then add a direct link from $C_j^T$ to $x_k^-$; if negative variable $\bar{x}_k \in C_j$ then add a link from $C^T_j$ to $x_k^-$ with an intermediate node $z_{jk}$

The resulting graph $G$ has a connected, bipartite subgraph ($S\cup T=V$) in which the nodes of only one of the two set (suppose $S$) has max dregree $k$ if and only if the original 3CNF formula is satisfiable.

First of all the fan of the source node $s^T$ forces it to be in the unrestricted set $T$; and the fan of every clause $C_j^T$ forces it to be in $T$, too. Furthermore all nodes $x_i^S$ connected to $s^T$ are forced in the set $S$.

Now, for every variable, only one among $x_i^+, x_i^-$ can be put in $T$ (traverse the base of the triangle or pass through its vertice) because $x_i^S$ is in $S$ and its $k-2$ fan nodes must be connected, so we must drop edge $(x_i^S,x_i^+)$ or edge $(x_i^S,x_i^-)$). Suppose we choose $x_i^+$, and drop the edge $(x_i^S,x_i^-)$; hence $x_i^-$ falls in $S$, and we can use the edges from it to safely connect (satisfy) all the clauses (all because $k=c+2$) that contain $x_i$ and are directly connected to $x_i^-$, but not the clauses that are connected through $z_{ij}$ (which must be in $T$) because in that case $C_j^T$ would fall in $S$. Similarly, if we choose to put $x_i^-$ in $T$ then we can conect all the clauses that contain $\bar{x}_i$ (through $z_{ij}$ which now is in $S$).

At the end the graph $G$ is connected only if every clause contains at least one variable made true by the assignment.