HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Hard computational problem on special class of bipartite graphs

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemgraphshardcomputationalbipartitespecialclass

Problem

I am interested in the properties of a class of bipartite graphs $G(X \cup Y, E)$ where all nodes in $X$ are 3-regular, all nodes in $Y$ are 2-regular, and $|X|=|2Y/3|$. First, Is this a well known class of graphs? Secondly,


Is there an example of intractable computational problem restricted to this class of bipartite graphs?

Solution

Given a 3-regular graph $G = \{V,E\}$ you can build a bipartite graph $G'$ with the required properties picking $X = V$ and $Y = E$ and for every edge $e_k = (u_i,u_j) \in E$ add edges $(u_i, e_k), (e_k, u_j)$. So I think that you can find some hard problems starting from hard problems on 3-regular graphs.

For example SUBGRAPH ISOMORPHISM is NP-hard for your class of graphs.

The reduction is from Hamiltonian cycle on 3-regular graphs: given a 3-regular graph $G$, build the corresponding $G' = \{X \cup Y, E'\}$ and check for a subgraph $H'$ which is a closed simple cycle of length $2|V|$. $G'$ has a subgraph isomorphic to $H'$ if and only if $G$ has an Hamiltonian cycle.

Context

StackExchange Computer Science Q#18754, answer score: 4

Revisions (0)

No revisions yet.