CI²MA - Publicaciones | Prepublicaciones


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.

Descargar en formato PDF PDF