Pre-Publicación 2015-25
Julio Aracena, Adrien Richard, Lilian Salinas:
Fixed points in conjunctive networks and maximal independent sets in graph contractions
Abstract:
For a graph G, let C be the set of conjunctive networks with interaction graph G, and let H be the set of graphs obtained from G by contracting some edges. Let fix(f) be the number of fixed points in a network f in C, and let mis(h) be the number of maximal independent sets of h in H. Our main result is: mis(G) leq max_{mis(h): h in H} leq max_{fix(f):f in C} leq (3/2)^{m(G)}*mis(G), where m(G) is the maximum size of a matching M of G such that every edge of M is contained in an induced copy of C_4 that contains no other edge of M. Thus, if G has no induced C_4 then max_{mis(h): h in H}=max_{fix(f): f in C}=mis(G), and this contrasts with following complexity result: It is coNP-hard to decide if max_{fix(G):f in C}=mis(G) or if max_{mis(h): h in H}=mis(G), even if G has a unique induced copy of C_4.
Esta prepublicacion dio origen a la(s) siguiente(s) publicación(es) definitiva(s):
Julio ARACENA, Adrien RICHARD, Lilian SALINAS: Fixed points in conjunctive networks and maximal independent sets in graph contractions. Journal of Computer and System Sciences, vol. 88, pp. 145-163, (2017).