Add bootstrap percolation functions

[flippenc]

Bootstrap number is defined in: https://arxiv.org/pdf/1703.10741.pdf and models the spread of an 'infection' throughout a graph

def is_k_bootstrap_good(G,k):
    """
    assumes G has at least k vertices
    if G has more than k vertices, it must be connected to be k_bootstrap_good
    returns True if there exists a set of k vertices such that G is fully infected 
    """
    G.relabel()
    for s in itertools.combinations(G.vertices(), k):
        if k_percolate(G,set(s),k):
            return True
    return False

def k_percolate(G,infected,k):
    """
    returns True if the set 'infected' fully k-infects the graph G
    """
    uninfected = set(G.vertices()) - set(infected)
    newInfections = True
    while newInfections:
        newInfections = False
        for v in uninfected:
            if len(set(G.neighbors(v)).intersection(infected)) >= k:
                infected.add(v)
                uninfected-=set([v])
                newInfections = True
                break
    return len(uninfected) == 0

def is_2_bootstrap_good(G):
    """
    assumes G has at least 2 vertices
    returns True if G contains a subset of 2 vertices which 2-infect the whole graph
    EXAMPLES:
    sage: is_2_bootstrap_good(k4)
    True
    sage: is_2_bootstrap_good(graphs.ThomsenGraph())
    True
    sage: is_2_bootstrap_good(graphs.CycleGraph(4))
    True
    sage: is_2_bootstrap_good(graphs.CycleGraph(5))
    False
    sage: is_2_bootstrap_good(ce83)
    True
    sage: is_2_bootstrap_good(graphs.PetersenGraph())
    False
    sage: is_2_bootstrap_good(p4)
    False
    """
    return is_k_bootstrap_good(G,2)

def is_3_bootstrap_good(G):
    """
    assumes G has at least 3 vertices
    returns True if G contains a subset of 3 vertices which 3-infect the whole graph
    EXAMPLES:
    sage: is_3_bootstrap_good(graphs.BullGraph())
    False
    sage: is_3_bootstrap_good(graphs.ThomsenGraph())
    True
    sage: is_3_bootstrap_good(graphs.CycleGraph(4))
    False
    sage: is_3_bootstrap_good(graphs.BidiakisCube())
    False
    sage: is_3_bootstrap_good(graphs.CycleGraph(5))
    False
    sage: is_3_bootstrap_good(willis_page35_fig52)
    True
    sage: is_3_bootstrap_good(ce68)
    True
    """
    return is_k_bootstrap_good(G,3)

[jaritaes99]

I'm thinking of adding it to Properties, what do you think?

[thenealon]

Fine with me to add it. is_2_bootstrap_good(G) and is_3_bootstrap_good(G) are efficiently computable properties; is_k_bootstrap_good and k_percolate are helper functions.

In fact, is_k_bootstrap_good(G,k) is an infinite family of efficiently computable properties. (each is polynomial, but unbounded overall). Do we have a list of "parameterized properties" or something? Is there a word for those, which I am forgetting?

[jaritaes99]

I'm not sure if there is a parameterized properties list, probably something to check on. Will add them to efficiently computable properties in the meanwhile. Will create issue about it.