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

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?

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.