Copyright © [2016] by The Society for Industrial and Applied Mathematics. All rights reserved
We study the node-deletion problem consisting of finding a maximum weighted induced bipartite subgraph of a planar graph with maximum degree three. We show that this is polynomially solvable. It was shown in [4] that it is NP-complete if the maximum degree is four. We also extend these ideas to the problem of balancing signed graphs.
We also consider maximum weighted induced acyclic subgraphs of planar directed graphs. If the maximum degree is three, it is easily shown that this is polynomially solvable. We show that for planar graphs with maximum degree four it is NP-complete.
By: Mourad Baïou, Francisco Barahona
Published in: SIAM Journal on Discrete Mathematics, volume 30, (no 2), pages 1290-1301; 10.1137/140980053 in 2016
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .