Feder, Tomás; Hell, Pavol; Jonsson, Peter; Krokhin, Andrei; Nordh, Gustav Retractions to pseudoforests. (English) Zbl 1215.05063 SIAM J. Discrete Math. 24, No. 1, 101-112 (2010). Summary: For a fixed graph \(H\), let \(\text{RET}(H)\) denote the problem of deciding whether a given input graph is retractable to \(H\). We classify the complexity of \(\text{RET}(H)\) when \(H\) is a graph (with loops allowed) where each connected component has at most one cycle, i.e., a pseudoforest. In particular, this result extends the known complexity classifications of \(\text{RET}(H)\) for reflexive and irreflexive cycles to general cycles. Our approach is based mainly on algebraic techniques from universal algebra that previously have been used for analyzing the complexity of constraint satisfaction problems. Cited in 14 Documents MSC: 05C15 Coloring of graphs and hypergraphs 08A70 Applications of universal algebra in computer science 68R10 Graph theory (including graph drawing) in computer science Keywords:retraction; computational complexity; universal algebra; constraint satisfaction PDFBibTeX XMLCite \textit{T. Feder} et al., SIAM J. Discrete Math. 24, No. 1, 101--112 (2010; Zbl 1215.05063) Full Text: DOI