Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs. (English) Zbl 1338.05052
Summary: We study the maximum node-weighted induced bipartite subgraph problem in planar graphs with maximum degree three. We show that this is polynomially solvable. It was shown in [H.-A. Choi et al., ibid. 2, No. 1, 38–47 (1989; Zbl 0677.68036)] that it is NP-complete if the maximum degree is four. We 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 the same problem is NP-complete.
MSC:
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 05C22 | Signed and weighted graphs |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 90C27 | Combinatorial optimization |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Keywords:
maximum induced bipartite subgraph; balancing signed graphs; maximum induced acyclic subgraph; polynomial algorithm; NP-completenessCitations:
Zbl 0677.68036References:
| [1] | M. Ba\iou and F. Barahona, {\it Maximum weighted induced bipartite subgraphs and acyclic subgraphs of planar cubic graphs}, in Integer Programming and Combinatorial Optimization: 17th International Conference, IPCO 2014, Bonn, Germany, 2014, Lecture Notes in Comput. Sci. 8494, Springer, New York, 2014, pp. 88-101. · Zbl 1418.90212 |
| [2] | F. Barahona, {\it Planar multicommodity flows, max cut and the Chinese postman problem}, in Polyhedral Combinatorics, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 1, AMS, Providence, RI, 1990, pp. 189-202. · Zbl 0747.05067 |
| [3] | F. Barahona, {\it On cuts and matchings in planar graphs}, Math. Program., 60 (1993), pp. 53-68. · Zbl 0795.90017 |
| [4] | F. Barahona and A. Mahjoub, {\it Facets of the balanced (acyclic) induced subgraph polytope}, Math. Program., 45 (1989), pp. 21-33. · Zbl 0675.90071 |
| [5] | F. Barahona and A. Mahjoub, {\it Compositions of graphs and polyhedra} I{\it : Balanced induced subgraphs and acyclic subgraphs}, SIAM J. Discrete Math., 7 (1994), pp. 344-358. · Zbl 0802.05067 |
| [6] | F. Barahona, R. Maynard, R. Rammal, and J. Uhry, {\it Morphology of ground states of two-dimensional frustration model}, J. Phys. A, 15 (1982), p. 673. |
| [7] | R.-W. Chen, Y. Kajitani, and S.-P. Chan, {\it A graph-theoretic via minimization algorithm for two-layer printed circuit boards}, IEEE Trans. Circuits Systems, 30 (1983), pp. 284-299. · Zbl 0505.94031 |
| [8] | H.-A. Choi, K. Nakajima, and C. S. Rim, {\it Graph bipartization and via minimization}, SIAM J. Discrete Math., 2 (1989), pp. 38-47. · Zbl 0677.68036 |
| [9] | J. Edmonds and E. L. Johnson, {\it Matching, Euler tours and the Chinese postman}, Math. Program., 5 (1973), pp. 88-124. · Zbl 0281.90073 |
| [10] | G. Even, J. S. Naor, B. Schieber, and M. Sudan, {\it Approximating minimum feedback sets and multicuts in directed graphs}, Algorithmica, 20 (1998), pp. 151-174. · Zbl 0897.68078 |
| [11] | P. Festa, P. M. Pardalos, and M. G. Resende, {\it Feedback set problems}, in Handbook of Combinatorial Optimization, Springer, New York, 1999, pp. 209-258. · Zbl 1253.90193 |
| [12] | P. Fouilhoux and A. Mahjoub, {\it Solving VLSI design and DNA sequencing problems using bipartization of graphs}, Comput. Optim. Appl., 51 (2012), pp. 749-781. · Zbl 1245.90100 |
| [13] | A. Frank, {\it How to make a digraph strongly connected}, Combinatorica, 1 (1981), pp. 145-153. · Zbl 0487.05033 |
| [14] | M. Funke and G. Reinelt, {\it A polyhedral approach to the feedback vertex set problem}, in Integer Programming and Combinatorial Optimization, Springer, New York, 1996, pp. 445-459. · Zbl 1415.90063 |
| [15] | H. N. Gabow, {\it An efficient implementation of edmonds’ algorithm for maximum matching on graphs}, J. ACM, 23 (1976), pp. 221-234. · Zbl 0327.05121 |
| [16] | H. N. Gabow, {\it Centroids, representations, and submodular flows}, J. Algorithms, 18 (1995), pp. 586-628. · Zbl 0826.68095 |
| [17] | G. Gardarin and S. Spaccapietra, {\it Integrity of data bases: A general lockout algorithm with deadlock avoidance}, in Proceeding of IFIP Working Conference on Modelling in Data Base Management Systems, 1976, pp. 395-412. |
| [18] | M. R. Garey and D. S. Johnson, {\it Computers and Intractability: A Guide to the Theory of NP-Completeness}, W. H. Freeman, New York, 1979. · Zbl 0411.68039 |
| [19] | N. Garg, V. V. Vazirani, and M. Yannakakis, {\it Approximate max-flow min-(multi) cut theorems and their applications}, SIAM J. Comput., 25 (1996), pp. 235-251. · Zbl 0844.68061 |
| [20] | M. X. Goemans and D. P. Williamson, {\it Primal-dual approximation algorithms for feedback problems in planar graphs}, Combinatorica, 18 (1998), pp. 37-59. · Zbl 0928.90094 |
| [21] | F. Hadlock, {\it Finding a maximum cut of a planar graph in polynomial time}, SIAM J. Comput., 4 (1975), pp. 221-225. · Zbl 0321.05120 |
| [22] | R. Karp, {\it Reducibility among combinatorial problems}, in Complexity of Computer Computations, R. Miller, J. Thatcher, and J. Bohlinger, eds., IBM Research Symposia Series, Springer, New York, 1972, pp. 85-103. · Zbl 1467.68065 |
| [23] | C. E. Leiserson and J. B. Saxe, {\it Retiming synchronous circuitry}, Algorithmica, 6 (1991), pp. 5-35. · Zbl 0708.94025 |
| [24] | D. Lichtenstein, {\it Planar formulae and their uses}, SIAM J. Comput., 11 (1982), pp. 329-343. · Zbl 0478.68043 |
| [25] | R. J. Lipton and R. E. Tarjan, {\it A separator theorem for planar graphs}, SIAM J. Appl. Math., 36 (1979), pp. 177-189. · Zbl 0432.05022 |
| [26] | C. Lucchesi and D. Younger, {\it A minimax theorem for directed graphs}, J. Lond. Math. Soc. (2), 17 (1978), pp. 369-374. · Zbl 0392.05029 |
| [27] | R. Y. Pinter, {\it Optimal layer assignment for interconnect}, J. VLSI Computer Systems, 1 (1984), pp. 123-137. · Zbl 0552.94028 |
| [28] | C. Potts, {\it An algorithm for the single machine sequencing problem with precedence constraints}, in Combinatorial Optimization II, Springer, New York, 1980, pp. 78-87. · Zbl 0441.90038 |
| [29] | P. D. Seymour, {\it On odd cuts and plane multicommodity flows}, Proc. Lond. Math. Soc., 3 (1981), pp. 178-192. · Zbl 0447.90026 |
| [30] | A. Silberschatz, J. L. Peterson, and P. B. Galvin, {\it Operating System Concepts}, Addison-Wesley Longman, Boston, 1991. · Zbl 0883.68037 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
