Retractions To Pseudoforests
2010 (English)In: SIAM JOURNAL ON DISCRETE MATHEMATICS, ISSN 0895-4801, Vol. 24, no 1, 101-112 p.Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
Society for Industrial and Applied Mathematics , 2010. Vol. 24, no 1, 101-112 p.
retraction, computational complexity, universal algebra, constraint satisfaction
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-56791DOI: 10.1137/080738866ISI: 000277834800007OAI: oai:DiVA.org:liu-56791DiVA: diva2:322279