title: Graph edge traversal algorithm, some edges required, some optional
body: <p>I have an undirected graph with all vertices of even degree. In this graph there is a set of edges that must be covered exactly once, and a set of edges that should not be covered at all unless absolutely necessary. I need to find a set of one or more paths through the graph such that all of the required edges are covered exactly once, and the number of undesired edges traversed is minimized. No required edge can be traversed by more than one path, but the undesired edges can be traversed by any number of paths. It is not quite a Eulerian path because there are optional edges.</p>
  
  <p>Each individual path's length is limited by a maximum number of required edges it can cover, although a path can cover any number of undesired edges.</p>
  
  <p>The starting points and ending points need not be the same, but there is a set of possible starting points.</p>
  
  <p>Some of the undesired edges are coincident with the required edges -- that is, a pair of vertices might have both a required edge and an undesired edge between them (although there will never be more than one edge of each type between a given pair of vertices).</p>
  
  <p>What's a good algorithm to start with? Fundamentally, I am looking for an algorithm that can find a path that traverses required edges exactly once and avoids undesired edges when possible (but can traverse them more than once if necessary). I can build on that to do the rest.</p>