# bounded outdegree bipartite spanners

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

-
Just a clarification: is $G$ a directed graph? (you use "... maximal outdegree ...") –  Marzio De Biasi Nov 12 '12 at 20:35
$G$ is undirected, $G'$ is directed - I fixed it above. –  AJed Nov 12 '12 at 20:41
(continue) ... Bounded-degree spanning tree problem remains NP-complete for every fixed $k \geq 2$ (see Wikipedia). And - if $G'$ is undirected - your problem seems to have a solution iif there exists a spanning tree with max-degree = 3: given a max-degree=3 spanning tree, then it is a valid solution (connected,bipartite); the other way, given a valid solution we can transform it to a max-degree=3 spanning tree just deleting its loops. –  Marzio De Biasi Nov 12 '12 at 21:11
I think your problem statement is unclear. By property p1 ("connected"), since G' is directed, do you mean it is strongly connected? Or do you mean that if you undirect the edges of G' it becomes connected? (In the latter case, your problem is trivial: take G' to be a spanning tree of G, directing all edges towards one root.) Perhaps you mean that G' should be an induced subgraph of G (obtained by some vertex subset and all edges within the subset)? –  Neal Young Nov 12 '12 at 22:47
@MarzioDeBiasi - Yes, there is a solution to my problem if there is a solution to the bounded degree spanning tree, but not the opposite. This is because I restrict that only one of the sets $S$ or $T$ be degree bounded. In bounded deg sp. tree. - both sets (i.e. $V$) is degree bounded. I guess I need to clarify this point more. –  AJed Nov 13 '12 at 2:11

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.

-
The last step of building the graph is neat ! I tried to use to the 3CNF once, but I guess this is what I was missing ! –  AJed Nov 14 '12 at 4:57
may I contact you by email regarding this solution? - are you the author of "The Complexity of Camping" ? –  AJed Nov 14 '12 at 21:13
@Ajed: yes you can find my email on that paper –  Marzio De Biasi Nov 14 '12 at 22:28