in: struct {
(1,2,3) k: int
(1,2,3,4,5) numnodes: int
(1,2,3,4,5) edges: array of array [2] of int
(1,2,3,4,5) adjacents: array of array of int
(1,2,3,4,5) adjacencymatrix: array of array of int
(6) numvars: int
(6) clauses: array of array of int
}
The input may include a natural number in.k, an undirected graph, or a
boolean formula in conjunctive normal form. The graph is given by means of four
different kinds of information: the number of nodes in.numnodes, the
list of edges in.edges, for each node the list of its adjacent nodes
in.adjacents, and the adjacency matrix in.adjacencymatrix. The
nodes are integers between $1$ and in.numnodes, and thus, the $0$’th
position of in.adjacents does not contain useful data and should be
ignored; for any other position $p$, in.adjacents[p] is the list of
nodes adjacent to $p$. For the same reason, the $0$’th row and column of
in.adjacencymatrix do not contain useful data and should be ignored; for
any other row $r$ and column $c$, in.adjacencymatrix[r][c] is $0$ when
there is no edge between the nodes $r$ and $c$, and $1$ otherwise. The boolean
formula is described with the number in.numvars of variables occurring
in the formula, and with the list of clauses in.clauses. Each clause is
a list of literals, and each literal is a positive or negative integer: a
positive integer $x$ represents the $x$’th variable, and a negative integer
$-x$ represents the negation of the $x$’th variable. Such an $x$ takes values
between $1$ and in.numvars.
Note: The input graph has at least one node ($2$ in CLIQUE and UHC, $4$ in 3C), no
repeated edges, nor self-loop edges, the value of in.k is at most the
number of nodes of the graph (and at least $2$ in CLIQUE), and the boolean
formula has at least one clause, with every clause having at least one literal
and no repeated literals.