Inspired by Biology, DNA reporter strand is the problem of finding a tour in a 2-connected graph such that each edge is covered either once or twice, in opposite directions if used twice and further satisfies a particular permutation through each vertex. Finding such a tour with the minimum length is of the interest. In this talk, it will be briefly shown that it is NP-hard to find such a minimum-length tour and proved that it is fixed-parameter when parameterized by treewidth of the given graph.
Joint work with Juan Besa, David Eppstein, Sid Gupta, Timothy Johnson, Nil Mamano, Pedro Maties