[Rule] FEEDBACK ARC SET to MAXIMUM LIKELIHOOD RANKING

[isPANN]

Source: FEEDBACK ARC SET (MinimumFeedbackArcSet)
Target: MAXIMUM LIKELIHOOD RANKING (MaximumLikelihoodRanking)

Motivation: FAS and MLR are the same problem: rank items to minimize disagreement. A digraph is directly a skew-symmetric comparison matrix. The reduction is the identity mapping from adjacency structure to matrix.

Reference: Garey & Johnson, Computers and Intractability, A12 MS11; Rafsky 1977 (private communication)

GJ Source Entry

[MS11] MAXIMUM LIKELIHOOD RANKING
INSTANCE: n x n antisymmetric matrix A of integers (a_ij + a_ji = constant for each pair), positive integer B.
QUESTION: Is there a permutation pi of {1, ..., n} such that the sum of a_{pi(i),pi(j)} over all i > j is at most B?

Reference: [Rafsky, 1977]. Transformation from FEEDBACK ARC SET.
Comment: NP-complete in the strong sense.

Reduction Algorithm

Given a MinimumFeedbackArcSet instance (directed graph G = (V, A)), construct a MaximumLikelihoodRanking instance directly.

Set n = |V|. Build the n x n skew-symmetric matrix M (c = 0):

For each pair of distinct vertices i, j:

• If arc (i -> j) exists in A and arc (j -> i) does not: set M[i][j] = +1, M[j][i] = -1
• If arc (j -> i) exists in A and arc (i -> j) does not: set M[i][j] = -1, M[j][i] = +1
• If both arcs (i -> j) and (j -> i) exist: set M[i][j] = 0, M[j][i] = 0
• If neither arc exists: set M[i][j] = 0, M[j][i] = 0

Set M[i][i] = 0 for all i.

This satisfies M[i][j] + M[j][i] = 0 for all pairs (c = 0, skew-symmetric).

Objective correspondence

For a ranking pi, the MLR cost is:

cost(pi) = sum over (a,b) where a ranked after b of M[a][b]
         = (number of backward one-dir arcs) * 1
           + (number of forward one-dir arcs) * (-1)
           + 0 * (bidirectional and no-arc pairs)
         = backward - forward
         = 2 * backward - |one-dir arcs|

Since |one-dir arcs| is a constant, minimizing cost = minimizing backward one-dir arcs.

Total FAS = backward one-dir arcs + |bidirectional pairs| (each bidirectional pair always contributes one backward arc, regardless of ordering). Since |bidirectional pairs| is constant, minimizing FAS = minimizing backward one-dir arcs = minimizing MLR cost.

Set the MLR bound:

B = 2 * k - |one-dir arcs|

where k is the FAS bound. Then cost(pi) <= B iff FAS(pi) <= k.

Solution Extraction

Given the optimal permutation pi from the MLR solution (config[item] = rank):

1. Enumerate all arcs (i -> j) in the original graph G.
2. An arc (i -> j) is backward iff config[i] > config[j] (i ranked after j).
3. The set of backward arcs is the minimum feedback arc set.

Size Overhead

Target metric (code name)	Expression
num_items	num_vertices

The matrix is n x n where n = |V|. Each entry is computed in O(1) from the adjacency structure.

Example

Source instance (MinimumFeedbackArcSet):
Directed graph G with 5 vertices {0, 1, 2, 3, 4} and 7 arcs:

• Arcs: (0->1), (1->2), (2->0), (2->3), (3->4), (4->2), (0->4)

Two cycles: 0->1->2->0 and 2->3->4->2.
Minimum FAS = 2 (e.g., remove {(2->0), (4->2)}, leaving DAG with topological order 0,1,2,3,4).

All arcs are one-directional. |one-dir arcs| = 7. |bidir| = 0. |no-arc| = 3.

Constructed skew-symmetric matrix (c = 0):

M = [[ 0,  1, -1,  0,  1],
     [-1,  0,  1,  0,  0],
     [ 1, -1,  0,  1, -1],
     [ 0,  0, -1,  0,  1],
     [-1,  0,  1, -1,  0]]

Verify: M[i][j] + M[j][i] = 0 for all pairs.

Verification with ranking pi = [0, 1, 2, 3, 4]:
Backward arcs (config[i] > config[j] and arc i->j exists):

• (2->0): config[2]=2 > config[0]=0, M[2][0] = +1
• (4->2): config[4]=4 > config[2]=2, M[4][2] = +1
  Forward arcs contribute -1 each (5 forward arcs).

MLR cost = 2*1 + (-1)5 + 0 = 2 - 5 = -3.
B = 22 - 7 = -3.
cost <= B: -3 <= -3. FAS = 2.

Alternative ranking [2, 0, 1, 3, 4] (FAS = 3, arcs 0->1, 2->3, 0->4 backward... actually let's just verify the extraction):
The extraction from ranking [0,1,2,3,4] gives backward arcs {(2->0), (4->2)} = FAS of size 2.

Validation Method

• Closed-loop test: reduce MinimumFeedbackArcSet to MaximumLikelihoodRanking, solve target with BruteForce, extract backward arcs, verify they form a valid FAS.
• Test with a DAG: FAS = 0, cost = -|A|.
• Test with 5-vertex example above (has no-arc pairs): verify skew-symmetric property.
• Test with bidirectional arcs: verify M[i][j] = M[j][i] = 0.
• Verify M[i][j] + M[j][i] = 0 for all constructed matrices.

References

• [Rafsky, 1977]: L.C. Rafsky (1977). Private communication cited in Garey & Johnson.
• [Kemeny, 1959]: J.G. Kemeny (1959). "Mathematics Without Numbers." Daedalus, 88, pp. 577-591.

[isPANN]

Updated to match the optimization framing of #930. Removed bound B from the reduction algorithm and correctness statement. The construction is unchanged; correctness is now: 'minimum disagreement cost = minimum feedback arc set size' instead of the decision version with bound B.