Is there an algorithm for this decision problem that is better than brute-force?

Question

Apologies for the vague title. This decision problem has applications to graph coloring but I have not found a name for it in the literature.

I am trying to improve my algorithm for a decision problem. The problem input is a graph and hypergraph which have the same vertex set, $(V, E, H)$ where $V$ is the set of vertices, $E$ is the set of edges, and $H$ is the set of hyperedges.

The Hostile Soldiers and Alliances Game

Imagine there is a set of soldiers (vertices) such that for every pair of soldiers, either:

• The two soldiers are hostile towards each other (there is an edge between them), or
• They are indifferent towards each other (there is not an edge between them)

The soldiers can also be involved in a set of alliances (hyperedges).

Two alliances $A$ and $B$ can go to war if there exists:

• some nonempty set of soldiers $X \subseteq A \setminus B$, and
• some nonempty set of soldiers $Y \subseteq B \setminus A$

such that every soldier in $X$ is hostile to every soldier in $Y$, i.e., $X$ and $Y$ form a biclique.

The war results in a new alliance made up of all the soldiers who did not participate in the hostile biclique, $(A \cup B) \setminus (X \cup Y)$. An alliance cannot go to war with itself.

Now imagine that your goal is to come up with a sequence of wars (biclique, hyperedge, hyperedge) such that the last war produces an alliance with zero members. Each edge in $E$ can be used at most once in the sequence of wars.

Pictured is an example

This problem is in NP, since a proof certificate can have at most $|E|$ bicliques. I suspect that this problem is NP-complete but I have not found a reduction yet.

My algorithm attempt

function decide(graph, hypergraph) -> bool:
    for each pair of hyperedges A, B in hypergraph:
        for each biclique X, Y in A, B:
            C = (A \/ B) - (X \/ Y)
            
            if C is empty:
                return True
            
            if decide(graph - biclique, hypergraph + C):
                return True

    return False

I am not sure of the time complexity of this algorithm, but since it is brute-force looking for a sequence of wars, I would not be surprised if it is factorial in the number of bicliques (which itself is exponential in the number of vertices).

I have not seen a case yet where a solution requires that a hyperedge is used twice in the sequence of wars. I haven't been able to prove it, but if so, then I could change the algorithm to recur on (graph - biclique, (hypergraph + C) - (A + B)), that is, the algorithm could eliminate $A$ and $B$ from the search after using them in a war.

Are there any opportunities for improving this algorithm?

Answer 1

I figured out that this problem is isomorphic to CNF-SAT where:

• Each hyperedge $H = {v_1, v_2, ... v_n}$ corresponds to a clause $(v_1 \lor v_2 ... \lor v_n)$
• Each edge $(u, v)$ corresponds to the clause $(\neg u \lor \neg v)$

And a "war" between hyperedges corresponds to a particular form of resolution, where:

• $(\bigvee_a^A a \lor \bigvee_b^B b)$
• $(\bigvee_c^C c \lor \bigvee_d^D d)$
• $\bigwedge_{(b, c)}^{B \times C} (\neg b \lor \neg c)$

resolves to:

• $(\bigvee_a^A a \lor \bigvee_d^D d)$

Moreover, any CNF-SAT instance can be converted into the form $\bigwedge(a \lor b \lor ... c) \land \bigwedge (\neg d \lor \neg e)$ by replacing any negated literal $\neg x_i$ with a new variable $n_i$ and introducing a new clause $(\neg x_i \lor \neg n_i)$.

Therefore there is no "sequence of wars" that leads to an empty hyperedge unless NP = coNP.