Leverage computational reducibility of vertex covers and independent sets to cover/packing problems for sets.

reducibility.py

# https://homes.di.unimi.it/cesa-bianchi/Algo2/Note/np.pdf

from itertools import chain
from itertools import combinations
from pdb import set_trace as brk

def powerset(iterable):
    """Computes the powerset of an iterable."""
    if iterable is None: return None
    s = tuple(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

class Graph:
    """Encodes an undirected graph."""
    def __init__(self, v=None, e=None):
        self.v = v or []
        self.e = e or []

def set_cover(U, S, k):
    """Check is there's a cover for U of <= k subsets in S."""
    for set_of_subs in filter(lambda x, k=k: len(x) in range(1,k+1), powerset(S)):
        if len(set.union(*set_of_subs)) != len(U): continue
        return True
    return False

def set_packing(U, S, k):
    """Check if there are at least k disjoint subsets of U in S."""
    for set_of_subs in filter(lambda x, k=k: len(x)>=k, powerset(S)):
        union_set = set.union(*set_of_subs)
        if len(union_set) != sum(map(len, set_of_subs)): continue
        return True
    return False

def vertex_cover(g, k):
    """Check if there's a vertex cover of <= k vertices.
   
    It reduces the vertex cover problem to a set cover one
    using a quadratic approach - O(|V|*|E|). That implements
    part of the proof that a vertex cover problem is
    polynomially reducible to a set cover one.
    """
    v, e = g.v, g.e
    S = []
    for vertex in v:
        s = set()
        for edge in e:
            if vertex in edge: s.add(edge)
        S.append(s)
    return set_cover(e, S, k)

def independent_set(g, k):
    """Check if there's an independent set of >= k vertices."""
    v, e = g.v, g.e
    S = []
    for vertex in v:
        s = set()
        for edge in e:
            if vertex in edge: s.add(edge)
        S.append(s)
    return set_packing(e, S, k)

class Literal:
    def __init__(self, boolean):
        assert (len(boolean) == 2 or
                boolean.startswith('!') and len(boolean) == 3)
        self.boolean = boolean

    def __neg__(self):
        if self.boolean.startswith('!'):
            return Literal(self.boolean[1:])
        else:
            return Literal('!' + self.boolean)

    def __hash__(self):
        return hash(self.boolean)

    def __repr__(self):
        return self.boolean

def three_sat(C):
    """Check if all the clauses in C can be satisfied."""
    g = Graph()
    edges = []
    for clause in C:
        clause = tuple(map(Literal, clause))
        g.v.extend(clause)
        for i, j in combinations(clause, r=2):
            edges.append((i, j))
        for l in clause:
            for v in g.v:
                if l.boolean == (-v).boolean:
                    edges.append((l, v))
    g.e = list(map(tuple, map(set, edges)))
    return independent_set(g, len(C))

#def independent_set(g, k):
#    """Check if there's an independent set of >= k vertices.
#
#    This implements the brute-force algorithm whose complexity
#    can be estimated to be of O(2**n * n**2) - it's actually
#    better than that but still the slowest procedure one could
#    think of.
#    """
#    result = []
#    v, e = g.v, list(map(lambda x: set(x), g.e))
#    for s in powerset(v):
#        dependent = False
#        for i in range(len(s)):
#            for j in range(len(s)):
#                if i == j: continue
#                if {s[i], s[j]} in e: dependent = True
#                if dependent: break
#            if dependent: break
#        if not dependent: result.append(s)
#    return max(map(len, result)) >= k

#def vertex_cover(g, k):
#    """Check if there's a vertex cover of <= k vertices."""
#    n = len(g.v)
#    return independent_set(g, n-k)

if __name__ == '__main__':
    cases = (
        [],
        [1],
        [1, 2, 3],
        'a',
        'ab',
    )

    expected = (
        [()],
        [(), (1,)],
        [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)],
        [(), ('a',)],
        [(), ('a',), ('b',), ('a', 'b')],
    )

    for case, exp in zip(cases, expected):
        actual = list(powerset(case))
        assert exp == actual, f'Expected: {exp}, Actual: {actual}'

    g = Graph()
    g.v.extend(('a', 'b', 'c', 'd', 'e', 'f'))
    g.e.extend((('a', 'b'), ('a', 'c'), ('c', 'd'), ('e', 'f')))

    C = [('x1', 'x1', 'x1'), ('!x1', '!x1', '!x1')]