In a DAG, longest path where every vertex has degree at most 2

Question

I have a directed acyclic graph (DAG). How I can find the longest path using only vertices with degree at most 2?

Currently, I try this

def all_simple_paths(g):
  for path in all_paths(g):
      if len(path) > 2:
          center_path = path[1:-1]
          nodes_degree = g.degree(center_path).values()
          if max(nodes_degree) <= 2:
              return path

but that might output any path, rather than the longest path.

Answer 1

First, remove all vertices whose degree is greater than 2 (i.e., their degree was greater than 2 in the original graph). The result is a smaller DAG. This can be done in linear time.

Now, find the longest path in the resulting DAG. This can be done in linear time, too; see https://en.wikipedia.org/wiki/Longest_path_problem.