Retractions To Pseudoforests

• For a fixed graph H, let RET(H) denote the problem of deciding whether a given input graph is retractable to H. We classify the complexity of 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 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.

Keyword

retraction

computational complexity

universal algebra

constraint satisfaction

TECHNOLOGY

TEKNIKVETENSKAP

Publication and Content Type

ref (subject category)

art (subject category)