Proof regarding the NP-completeness of the unweighted complex-triangle elimination (CTE) problem for general adjacency graphs
Souvik Roy, Sanghamitra Bandyopadhyay, Ujjwal Maulik · IEE Proceedings - Computers and Digital Techniques · 2001
The elimination of all complex triangles (CT) is an essential step in the rectangular dualisation approach of floor-planning. It is known that the weighted complex triangle elimination problem, i.e. the version of the problem where the input to the problem is a weighted adjacency graph, is NP-complete. Also, for adjacency graphs with 0-level containment the unweighted problem is optimally solvable in polynomial time. However, the complexity of the unweighted CTE problem for general graphs with multiple levels of containment was unknown though it was conjectured that this problem is also NP-complete. The authors present a claim that the unweighted complex triangle elimination problem for general graphs with multiple levels of containment is, indeed, NP-complete, and present a proof supporting the claim.