1
$\begingroup$

Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?

Given an undirected graph G, is there another graph, H, such that:

  • all vertices of G are in H
  • H is allowed extra vertices not in G
  • if a and b are connected in G, a and b are also connected in in H (possibly with at least some of the extra vertices in the H path from a to b)
  • if c and d are not connected in G, c and d are not connected in H
  • each vertex in H has degree at most 3
  • the edges of H can be enumerated in logspace given an input G

Maybe this could be called a logspace reduction of G to a graph that has max degree of 3 that preserves connectivity?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

For each edge $(u,v)$ in $G$, add vertices $w_{u,v}$ and $w_{v,u}$ to $H$, and add the edge $(w_{u,v},w_{v,u})$ to $H$.

For each vertex $u$ in $G$, if $u$ has edges $(u,v_1),\dots,(u,v_k)$, then add edges $(w_{u,v_i},w_{u,v_{i+1}})$ and $(u,w_{u,v_1})$ to $H$; and add edges $(w_{v_i,u},w_{v_{i+1},u})$ and $(w_{v_1,u},v)$ to $H$.

I believe this $H$ satisfies all of your properties. Also, I believe it can be constructed in logspace (please check me and verify for yourself).

$\endgroup$

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.