Urgent Reduction Rules to be implemented

[c-allergic]

• MIS to VertexCover
• QUBO(Spin Glass) to MaxCut
• Set Packing to IndependentSet
• Low Dimensional QUBO and IndependentSet
• Circuit SAT to k-SAT
• Vertex matching to MIS
• Vertex Matching to Set Packing
• SetCovering to VertexCovering (reverse one have been finished)

[GiggleLiu]

Vertex matching to MIS, instead of CircuitSAT to vertex matching. Maximum vertex matching is easy, the counting is hard though.

[GiggleLiu]

MIS to VertexCover is much easier.

[GiggleLiu]

General QUBO to QUBO on grid is trick. The rest are easy.

[GiggleLiu]

Find an interesting paper, sudoku to QUBO: https://arxiv.org/abs/2403.04816v1

[c-allergic]

MIS to VertexCover is much easier.

https://opendsa-server.cs.vt.edu/OpenDSA/Books/Everything/html/independentSet_to_vertexCover.html, this website has a simple proof. I'm a little bit confused that in that case, if we could directly input the graph and weight of IS to the vertex cover and finish the reduction, and when extract the solution, we just have the complement set of the solution?