×

Retractions to pseudoforests. (English) Zbl 1215.05063

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.

MSC:

05C15 Coloring of graphs and hypergraphs
08A70 Applications of universal algebra in computer science
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI