SIAM Journal on Discrete Mathematics · 1989 · 66 citations · 9 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationCombinatorial OptimizationGraph AlgorithmsGraph TheoryComputational Complexity Of Graph AlgorithmsGraph OptimizationMinimizationPlanar Graph AlgorithmsPlanar GraphsPolynomial Time ComplexityPolynomial-time AlgorithmsPrinted Circuit Boards
The vertex- (respectively, edge-) deletion graph bipartization problem is the problem of deleting a set of vertices (respectively, edges) from a graph so as to make the remaining graph bipartite. This paper first shows that the vertex-deletion graph bipartization problem has a solution of size k or less if and only if the edge-deletion graph bipartization problem has a solution of size k or less, when the maximum vertex degree is limited to three. This immediately implies that (1) the vertex-deletion graph bipartization problem is NP-complete for cubic graphs, and (2) the minimum vertex-deletion graph bipartization problem is solvable in polynomial time for planar graphs when the maximum vertex degree is limited to three. It is then proved that the vertex-deletion graph bipartization problem is NP-complete for planar graphs when the maximum vertex degree exceeds three. Using this result, it is finally shown that the via minimization problem, which arises in the design of integrated circuits and printed circuit boards, is NP-complete even when the maximum “junction” degree is limited to four.
9
Some simplified NP-complete graph problems
M. R. Garey, David S. Johnson, Larry Stockmeyer · Theoretical Computer Science · 1976 · 2.1K citations
Planar Formulae and Their Uses
David Lichtenstein · SIAM Journal on Computing · 1982 · 754 citations
Node-and edge-deletion NP-complete problems
Mihalis Yannakakis · 1978 · 444 citations · Full text