0
$\begingroup$

I define a list to be a path where every vertex along the path has precisely two edges, except possibly the starting and ending vertex. In the language of electric circuits, I'm interested in finding all components that are in series for a given circuit. I'm specifically interested in finding all maximal lists. As noted in the comments:

if $a \rightarrow b \rightarrow c \rightarrow d$ is a list, then so, too, is $a \rightarrow b$. However, since this list is contained within the first, (it's a sub-list, I guess) I want the largest list containing it.

Is there an efficient way of doing this?

My thoughts are something that seems too complex - start at an arbitrary vertex that has not yet been visited. If its degree is 2, then it lies on a list. Move along this list until you find a vertex that has degree 1 or degree > 2 (you've found the end of the list), or until you end up back at your original vertex (the graph is a loop). Move back along the list, marking all vertices along it as visited, and writing down the nodes you've visited until you find the other end. Repeat until you're out of non-visited vertices.

On the other hand, if your initial vertex does not lie on a list, then it is potentially an end point of one. Check the degree of all vertices connected to it. For any of them that have degree 2, continue as above.

This seems drastically inefficient. Is there:

a) A term for such a thing?

b) An efficient algorithm for finding them?

I've asked on math stack exchange and they mentioned that this sounds like an "ear decomposition", but I don't think so, due to the constraint that all nodes along the path must have 2 edges only.

$\endgroup$
  • $\begingroup$ If you implement this algorithm correctly, then it should work in $O(V)$ time, using $O(V)$ space. Try getting inspiration from BFS/DFS. Also, you aren't mentioning it, but I think you're looking for maximal paths. Moreover, according to your definition, a cycle is also a path - but that's a special case that you can easily detect. $\endgroup$ – Yuval Filmus Aug 8 '17 at 14:06
  • $\begingroup$ An efficient way of doing what? What exactly is the algorithmic problem? I understand that the input to the algorithm is a directed graph, but what is the desired output? Do you want to find a single list? Find all lists? (Presumably you only want maximum-length lists? So if $a \to b \to c \to d$ is a list, you don't want the algorithm to also report $a \to b \to c$ or $c \to d$. Right?) Can you edit the question to clarify these points? $\endgroup$ – D.W. Aug 8 '17 at 20:30
  • $\begingroup$ Cross-posted: math.stackexchange.com/q/2385540/14578, cs.stackexchange.com/q/79858/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W. Aug 8 '17 at 20:31
  • $\begingroup$ @D.W. in the original post, I was advised to post it here $\endgroup$ – Michael Stachowsky Aug 9 '17 at 12:50
  • $\begingroup$ @D.W. edited accordingly. You are correct. I want all maximal lists $\endgroup$ – Michael Stachowsky Aug 9 '17 at 12:52

Your Answer

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

Browse other questions tagged or ask your own question.