2
$\begingroup$

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.

enter image description here

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

An Example Proof where the answer is "Yes"

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.