Constrained Ordering

This page contains information about the implementation of the constrained ordering reduction technique.

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.

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 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:


Last changes 2006.01.30, Walter Guttmann