1
$\begingroup$

Given an undirected graph $G$ (can be cyclic) with the promise that all its faces have $3$ sides, is it possible to find the minimum distance between a source and any other vertices in LogSpace or in LogDCFL, at least under the constraint that between any two vertices there are polynomially many paths?

$\endgroup$
3
  • $\begingroup$ @StefanKohl: Please limit the flood of minor edits to a handful per day. See meta.mathoverflow.net/questions/599 . $\endgroup$ Oct 16, 2015 at 15:42
  • $\begingroup$ @EmilJeřábek: o.k.. $\endgroup$
    – Stefan Kohl
    Oct 16, 2015 at 15:45
  • 3
    $\begingroup$ What do you mean by "all its faces have 3 sides"? Faces are not a concept that makes sense for arbitrary (non-planar) graphs. And when you say "between any two vertices there are polynomially many paths", you mean simple paths, right? But in an undirected graph that's still a very strong restriction. $\endgroup$ Oct 17, 2015 at 4:43

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.