TODO: a set theory based reduction path

[GiggleLiu]

The hardness:

• unweighted MIS with unit-disk graph is a subset of MIS with simple graph.
• floating point weighted MIS with unit-disk graph is NOT a subset of integer weighted MIS with simple graph.

Is there a good way to decide possible reduction paths?

[GiggleLiu]

I want to reduce from A -> B, have existing rule C -> D. This rule is applicable if and only if:

• A is a subset of C
• D is a subset of B

[GiggleLiu]

Narrow down, at programming level:

• First we decide potential reduction paths, at problem level, without checking whether they satisfy detailed constraints.
• Then we filter out invalid paths by check the above relationship.

[GiggleLiu]

What if we have exponential growing reduction paths?

• Maybe we can use dynamic programming to keep track of shortest paths for problems that can be reduced to. similar to Dijkstra algorithm.

[isPANN]

So this is my understanding of what we need to do in the refactored repo. Is that correct?

1. Parametric Problem Modeling

Instead of static problem types, each NP-Complete problem is implemented with specific type parameters. These parameters define the constraints of the instance, which directly influence whether a specific reduction rule can be validly applied.

2. Extensible Architecture

Anyone should be able to add new problems or reduction rules independently without:

• Modifying the core search algorithm.
• Knowing the global state of the entire reduction graph.
• Causing side effects in existing reduction paths.

3. Optimized Search Strategy

The system must navigate a potentially vast search space efficiently. It achieves this by separating the high-level type-graph search (Problem A to Problem B) from the low-level instance validation (checking parameter compatibility), preventing an exponential explosion of the state space.

[GiggleLiu]

Good summary, this is accurate.