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

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

<p>Build $G$ in the following way:</p>

<ul>
<li>add a source node $s^T$ linked with $k+1$ nodes of degree 1 (a "fan");</li>
<li>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);</li>
<li>add edges from $s^T$ to every $x_i^S$;</li>
<li>add $k-2$ fan nodes to $x_i^S$;</li>
<li>for every clause $C_j$ add a node $C_j^T$ linked with $k+1$ fan nodes of degree 1;</li>
<li>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}$</li>
</ul>

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

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

<p>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 (<em>all</em> 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$). </p>

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

CC BY-SA 3.0
2012-11-14T04:57:24.837Z
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
CC BY-SA 3.0
2012-11-14T21:13:28.167Z
may I contact you by email regarding this solution? - are you the author of "The Complexity of Camping" ?
AJed
CC BY-SA 3.0
2012-11-14T22:28:42.663Z
@Ajed: yes you can find my email on that paper
Marzio De Biasi
CC BY-SA 3.0
2012-11-14T00:17:41.337Z
2012-11-14T00:27:54.777Z
2012-11-14T00:27:54.777Z
Marzio De Biasi
<p>Given an undirected graph $G = (V,E)$ and an integer $k &gt; 0$, our objective is to find a subgraph $G' = (V ,E')$ where $E' \subseteq E$ such that $G'$ has the three following properties :  </p>

<ul>
<li>$G'$ is connected. (property $p _1$: connected)</li>
<li>The vertices of $G'$ are divided into two disjoint subsets $S$ and $T$ ($S \cup T = V$). </li>
<li>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'$]</li>
<li>The nodes in $S$ are degree limited. (property $p _3$ call it outdegree bounded)</li>
</ul>

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

<hr>

<p>Here are some of my observations: </p>

<ul>
<li>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'$] </li>
<li>$G'$ with $p _1$ and $p _2$ is easily obtained with a rooted spanning tree algorithm + 2-coloring of tree. </li>
<li>$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. </li>
<li>$G'$ with $p_2$ and $p_3$ is trivial, (note that we are looking for any subgraph with the required properties!) </li>
<li>A close problem to this is the bounded degree spanning tree problem [proven to be NP-Complete with a reduction to Hamiltonian path] </li>
<li>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] </li>
</ul>

<p>PS:  I am trying to forget it but it always come back to my mind</p>

CC BY-SA 3.0
2012-11-12T20:35:08.930Z
Just a clarification: is $G$ a directed graph? (you use "... maximal *outdegree* ...")
Marzio De Biasi
CC BY-SA 3.0
2012-11-12T20:41:52.553Z
$G$ is undirected, $G'$ is directed - I fixed it above.
AJed
CC BY-SA 3.0
2012-11-12T21:11:39.673Z
(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
CC BY-SA 3.0
2012-11-12T22:47:16.993Z
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
CC BY-SA 3.0
2012-11-13T02:11:55.567Z
@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
CC BY-SA 3.0
2012-11-13T02:14:43.517Z
@NealYoung. Regarding the connectivity and outdegree boundness, I agree with you that it was not clear. What I meant, (can be found in the new edit), that I want one of the sets $S$ or $T$ of the bipartite spanner graph be degree connected. The subgraph (spanning) graph must be connected (in the undirected sense).
AJed
CC BY-SA 3.0
2012-11-13T02:16:47.677Z
@NealYoung: regarding the algorithm you proposed (which I also proposed), it does not work. Because this guarantees the outdegree boundness and connectivity [but not the bipartitness] -- that is: I want to color the rooted tree into two colors (bipartite) such that the nodes of one of the colors has degree at most $k$. [I will fix the definition of the problem]
AJed
<cc.complexity-theory><np-hardness><graph-colouring><set-cover><bounded-degree>
bounded outdegree bipartite spanners
AJed
# bounded outdegree bipartite spanners

(Asked by: username_0 on 2012-11-12)

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

**Tags:** cc.complexity-theory, np-hardness, graph-colouring, set-cover, bounded-degree

> **Comments:**
> **username_1**: Just a clarification: is $G$ a directed graph? (you use "... maximal *outdegree* ...")  
> **username_0**: $G$ is undirected, $G'$ is directed - I fixed it above.  
> **username_1**: (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.  
> **username_2**: 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)?  
> **username_0**: @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.  
> **username_0**: @NealYoung. Regarding the connectivity and outdegree boundness, I agree with you that it was not clear. What I meant, (can be found in the new edit), that I want one of the sets $S$ or $T$ of the bipartite spanner graph be degree connected. The subgraph (spanning) graph must be connected (in the undirected sense).  
> **username_0**: @NealYoung: regarding the algorithm you proposed (which I also proposed), it does not work. Because this guarantees the outdegree boundness and connectivity [but not the bipartitness] -- that is: I want to color the rooted tree into two colors (bipartite) such that the nodes of one of the colors has degree at most $k$. [I will fix the definition of the problem]  

---

## 1 answers

### Answer by username_1 on 2012-11-14. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: 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 !  
> **username_0**: may I contact you by email regarding this solution? - are you the author of "The Complexity of Camping" ?  
> **username_1**: @Ajed: yes you can find my email on that paper  

---

