Proving hardness of The Plauge’s problem

Yesterday, I found a quite exciting problem, which can be used to construct a public-key cryptosystem. The problem is as follows: given an undirected graph G = (V,E), partition the graph into disjoint partitions such that each partition contains exactly one node, which we will denote ‘middle node’, and all nodes being adjacent to the middle node. For a more detailed description, see [1].

It was posed as a question in [1] if the problem is NP-complete or not. We show (a bit informally) that the decision version of the problem is equivalent to the decision version of 3-SAT. For an arbitrary number of clauses, we construct subgraphs in the following way:

Here, the 3-SAT formula is (a \lor b \lor c)(\neg a \lor d \lor e)(\neg b \lor \neg d \lor c). The black nodes are forced to be middle nodes, and therefore either a green or a red node must be middle node. To provide dependence among variables, the variables must be linked at least once using operator-subgraphs. These are shown as dashed lines. The long-dashed lines are connected using Equality graphs, while the short-dashed are connected with Negation graphs. For instance, if we set a = \textsf{true}, then the same variable the remaining clauses must be forced to a = \textsf{true}. Below, we see the graphs that provide that operation.

For completeness, we provide nodes for basic logic operations in the graph representation. Since we by definition have no two-input logical operations in 3-SAT, these are not used in the reduction.

The colored nodes are ‘connector nodes’ which will be replaced by the nodes at the end of the dashed lines. If a partition is found, then it must necessarily be a solution to the 3-SAT formula. We will not prove this, but we advise the reader verify the claim for the simple graph. It is then hopefully easy and enough convincing to see that the graph construction can be generalized to any 3-SAT formula. The Or-operator is quite complex and is satisfiable if and only if at least one of the inputs are true. It is as follows:

The purpose of the Or-graph is to assert that at least one of the literals in each clause is true. If not, then the Or-graph is not possible to partition properly. So if there exists at least one clause that is no satisfiable, then an oracle for 3-SAT should output \textsf{No}. Likewise, the oracle for The Plague’s problem will output \textsf{No}. Our reduction is complete.

To prove that the reduction is polynomial, we note that the number of edges grows only linearly with the number of clauses. For the reverse reduction, see [1].


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s