Documentation of KTHlist graph format

[jakobnordstrom]

I looked quickly at the KTHlist format description on the CNFgen page https://massimolauria.net/cnfgen/graphformats.html#orgfe822f4 .

The added examples are very nice, but the description you give is not correct. You might want to have a more liberal graph parser, but if so you should note that CNFgen will also accept certain violations of the format and will decide to interpret undefined inputs in a certain way. You should not say that these violations are part of the format, which is how it is described now.

So, two passages need to be corrected.

First, for "simple" it is very much the case that if a vertex v has u in its adjacency list then v must be listed in the adjacency list of u (there is a typo here repeating v, BTW). This requirement is strict, and the graph is considered undefined otherwise. However, it is of course perfectly fine of you say that as far as CNFgen goes, an edge {u,v} is considered to be in graph when either u is in the list of v or when v is in the list of u.

Second, the way the KTHlist format is specified, a bipartite graph must list only the neighbour lists of the left-hand vertices, which have to be numbered consecutively from 1 onwards. That is, from the KTHlist point of view the only acceptable format is

c listing only left side vertices
11
1 : 7 8 9 0
2 : 6 7 9 0
3 : 8 9 11 0
4 : 8 10 11 0
5 : 6 10 11 0

But then you can note that CNFgen is more liberal that it will also (try to) compute a bipartition of any graph if instructed to do so. Therefore, from a CNFgen point of view --- but only from a CNFgen point of view --- the graph above is the same as

c listing left and right side vertices
11
1 : 7 8 9 0
2 : 6 7 9 0
3 : 8 9 11 0
4 : 8 10 11 0
5 : 6 10 11 0
6 : 2 5 0
7 : 1 2 0
8 : 1 3 4 0
9 : 1 2 3 0
10 : 4 5 0
11 : 3 4 5 0

The reason for the choice for KTHlist is to allow code that uses this format to be efficient (to avoid having to compute a bipartition) and also to make the input format well-defined. As you note, the CNFgen way of interpreting things here leads to that a perfectly legitimate bipartite graph, encoded in the strictest compliance with the CNFgen requirements, will nevertheless be declared by CNFgen to be an illegal input. This seems slightly funky to me. For KTHlist, the bipartite graph is either well-defined, and if so uniquely defined, or is not well-defined. Needless to say, both options are perfectly possible, and the choice is ultimately a matter of taste. But a description of KTHlist should be a correct description of KTHlist.

The point in both of these examples is that you have to distinguish clearly between how a format is specified and how CNFgen uses the format.

[MassimoLauria]

I decided to adhere strictly to the specification of bipartite graph and to consider illegal to list right-left edges. Both in the input and the output. See commit b93bfc5