11
$\begingroup$

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?

$\endgroup$
0
4
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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)$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.