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