Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
These graphs are the incidence graphs of cubic graphs, a.k.a. 2-stretches of 3-regular graphs. I'll write $I(G)$ for the incidence graph of $G$.
Given a graph $G$ and an integer $k$, it's NP-complete to determine if $G$'s crossing number is at most $k$ (i.e., whether $G$ can be drawn in the plane with at most $k$ edges crossing each other), even if $G$ is restricted to be cubic. Clearly, the crossing number is not affected by adding an extra vertex in the middle of each edge. (Source: Hlineny, "Crossing number is hard for cubic graphs", J. Combin. Theor. B 96(4):455–471; DOI.)
It's possible that the bandwidth problem for these graphs is NP-complete, since it is NP-complete for trees where every vertex has degree at most three. (Source: problem GT40 in Garey and Johnson for general graphs; for low-degree trees, Garey, Graham, Johnson and Knuth, "Complexity results for bandwidth minimization", SIAM J. Appl. Math. 34:477-495; Citeseer.)
Various NP-complete graph problems remain so on cubic graphs and these lead to NP-complete problems on the corresponding incidence graphs that are reasonably natural. For example, asking if a cubic graph $G$ has a dominating set of size at most $k$ is equivalent to asking if $I(G)$ is a union of at most $k$ copies of $I(K_{1,3})$. Likewise, an independent set in the cubic graph corresponds to a set of disjoint copies of $I(K_{1,3})$ in $I(G)$.
