Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650202 | Discrete Mathematics | 2009 | 9 Pages |
The instance of the problem of finding 2-factors in an orientated graph with forbidden transitions consists of an orientated graph GG and for each vertex vv of GG, a graph HvHv of allowed transitions at vv. Vertices of the graph HvHv are the edges incident to vv. An orientated 2-factor FF of GG is called legal if all the transitions are allowed, i.e. for every vertex vv, the two edges of FF adjacent to it form an edge in HvHv. Deciding whether a legal 2-factor exists in GG is NP-complete in general. We investigate the case when the graphs of allowed transitions are taken from some fixed class CC. We provide an exact characterization of classes CC so that the problem is NP-complete. In particular, we prove a dichotomy for this problem, i.e. that for any class CC it is either polynomial or NP-complete.