# Constrained Ordering

The constrained ordering problem is described in the technical report UIB-2005-03 (available as DVI, PS, PDF) that also contains the definition of a reduction technique and the discussion of its properties. We have implemented this reduction to be able to decide for all 224 constrained ordering problems using quadruples whether they are efficiently solvable or NP-complete.

The information on this page can be used to independently verify our results. More specifically, section 5.4 of the technical report describes the calculations that we have performed.

#### Source code

The calculation has been performed by the C++ program co.cc (as html). The reduction is implemented by backtracking with a configurable upper bound on the number of calls, and precalculation to speed it up. The union-find algorithm is used to maintain the disjoint sets that represent mutually CO-reducible problems.

#### Log file

The program logs on `stderr` the reductions it could perform. Every line of that file, unless empty, contains one reduction in the following format:

```0xAAAAAA<=0xBBBBBB CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
```
For all reductions b=1 is assumed. The information means that the problem P1 is CO-reducible to the problem P2 using b=1 and R, where P1, P2 and R are specified as follows.

• The 6-character field `AAAAAA` is the 24-bit hexadecimal number A encoding the source of the reduction P1. The i-th bit of A is set if and only if P1 contains the i-th permutation. The 24 permutations of 4 elements are sorted in reverse lexicographical order. For example, bit 0 corresponds to the permutation (4321).
• The 6-character field `BBBBBB` is the 24-bit hexadecimal number B encoding the target of the reduction P2. The encoding is the same as for A.
• The 30-character field `CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC` is the 120-bit hexadecimal number C encoding the constant R. The i-th bit of C is set if and only if R contains the i-th combination of 4 out of 5 elements. The 120 combinations of 4 elements out of 5 are sorted in reverse lexicographical order. For example, bit 0 corresponds to the combination (5432).

All hexadecimal numbers are written starting with the most significant bit on the left end, to the least significant bit 0 on the right end. For example, line 698547 of the log is:

```0x900000<=0xe00a2c 530400000000000040000000000000
```
This means that the constrained ordering problem (4,{(1234),(1342)}) is CO-reducible to the constrained ordering problem (4,{(1234),(1243),(1324),(3124),(3214),(4123),(4213),(4231)}) using b=1 and R={(1235),(1245),(1324),(1325),(1425),(3452)}.

#### Verification

Our calculation can be verified in two steps.

1. Verify that all entries in the log file are indeed CO-reductions.
2. Construct the strongly connected components of the reduction graph.

Independent programs have been written for the verification of both steps.

1. The first Haskell program verify1.hs (as html) inputs from `stdin` reduction data and checks if it represents valid CO-reductions. If this is the case, it outputs to `stdout` some of the edges of the reduction graph, namely
• the edges corresponding to the input,
• the edges for symmetrical problems as described in Section 3.1 of the technical report, and
• the edges with 4-exclusion as their target as described in Section 5.1 of the technical report.
When this program is fed with the log file it yields 34260920 edges.
2. The second C++ program verify2.cc (as html) inputs from `stdin` edge data of a graph, calculates its strongly connected components, and outputs them to `stdout`. When this program is fed with the output of the first program it yields the nine components shown in Figure 5 of the technical report. The reductions between these nine components are part of the log file.

In order to preserve clarity of expression, both programs have not been optimised for efficiency very much. Your computer should have about 2 GB of memory to be able to run both programs.

#### Erratum

The technical report UIB-2005-03 contains the following error:

• page 5: In the third line of the right-most box in figure 3, replace "{(213),(312),(321)}" by "{(123),(231),(321)}". (The former is symmetric to the problem in the second line of that box, and the class represented by the latter is missing.)

Last changes 2006.01.30, Walter Guttmann