The nonplanar vertex deletion or vertex deletion vd(G) of a graph G is the smallest nonnegative integer k, such that the removal of k vertices from G produces a planar graph G′. In this case G′ is said to be a maximum planar induced subgraph of G. We solve a problem proposed by Yannakakis: find the threshold for the maximum degree of a graph G such that, given a graph G and a nonnegative integer k, to decide whether vd(G)?k is NP-complete. We prove that it is NP-complete to decide whether a maximum degree 3 graph G and a nonnegative integer k satisfy vd(G)?k. We prove that unless P=NP there is no polynomial-time approximation algorithm with fixed ratio to compute the size of a maximum planar induced subgraph for graphs in general. We prove that it is Max SNP-hard to compute vd(G) when restricted to a cubic input G. Finally, we exhibit a polynomial-time -approximation algorithm for finding a maximum planar induced subgraph of a maximum degree 3 graph. 相似文献
The conformational behavior of a single AB block copolymer is studied by Monte Carlo simulation. The A‐A and A‐B interactions have the character of excluded volume interactions while the B units attract each other; the attractive B blocks can move along the chain. The collapse transition of the chain with increasing attraction between the B units is analyzed. Intrachain separation of the A and B units takes place in the course of the chain collapse with the formation of “globule with a tail” conformations. The globule is formed by the attractive moving B blocks while the tail consists of the swollen A segments. The model of AB block copolymer with moving B blocks can describe the behavior of interpolymer complexes between a long macromolecule and shorter polymer chains.
