×

Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT. (English) Zbl 1421.68088

Summary: In directed graphs, we investigate the problems of finding: 1) a minimum feedback vertex set (also called the Feedback Vertex Set problem, or MFVS), 2) a feedback vertex set inducing an acyclic graph (also called the Vertex 2-Coloring without Monochromatic Cycles problem, or Acyclic FVS) and 3) a minimum feedback vertex set inducing an acyclic graph (Acyclic MFVS). We show that these problems are strongly related to (variants of) Monotone 3-SAT and Monotone NAE 3-SAT, where monotone means that all literals are in positive form. As a consequence, we deduce several NP-completeness results on restricted versions of these problems. In particular, we define the 2-Choice version of an optimization problem to be its restriction where the optimum value is known to be either \(D\) or \(D + 1\) for some integer \(D\), and the problem is reduced to decide which of \(D\) or \(D + 1\) is the optimum value. We show that the 2-Choice versions of MFVS, Acyclic MFVS, Min Ones Monotone 3-SAT and Min Ones Monotone NAE 3-SAT are NP-complete. The two latter problems are the variants of Monotone 3-SAT and respectively Monotone NAE 3-SAT requiring that the truth assignment minimize the number of variables set to true. Finally, we propose two classes of directed graphs for which Acyclic FVS is polynomially solvable, namely flow reducible graphs (for which MFVS is already known to be polynomially solvable) and C1P-digraphs (defined by an adjacency matrix with the Consecutive Ones Property).

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aho, A. V.; Ullman, J. D., Node listings for reducible flow graphs, J. Comput. System Sci., 13, 286-299 (1976) · Zbl 0354.68077
[2] Bafna, V.; Berman, P.; Fujito, T., Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs, (International Symposium on Algorithms and Computation (1995), Springer), 142-151 · Zbl 1512.68189
[3] Bar-Yehuda, R.; Geiger, D.; Naor, J.; Roth, R. M., Approximation algorithms for the feedback vertex set problem with applications to constraint satisfaction and Bayesian inference, SIAM J. Comput., 27, 942-959 (1998) · Zbl 0907.68110
[4] Becker, A.; Geiger, D., Optimization of Pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem, Artificial Intelligence, 83, 167-188 (1996) · Zbl 1506.68118
[5] Booth, K. S.; Lueker, G. S., Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci., 13, 335-379 (1976) · Zbl 0367.68034
[6] Brandstädt, A.; Kratsch, D., On the restriction of some NP-complete graph problems to permutation graphs, (International Conference on Fundamentals of Computation Theory (1985), Springer), 53-62
[7] Coorg, S. R.; Rangan, C. P., Feedback vertex set on cocomparability graphs, Networks, 26, 101-111 (1995) · Zbl 0856.90113
[8] Das, S.; Sen, M.; Roy, A.; West, D. B., Interval digraphs: an analogue of interval graphs, J. Graph Theory, 13, 189-202 (1989) · Zbl 0671.05039
[9] R. Deb, Acyclic partitioning problem is NP-complete for \(k = 2\); R. Deb, Acyclic partitioning problem is NP-complete for \(k = 2\)
[10] Deb, R., An efficient nonparametric test of the collective household model (2008), unpublished, available at
[11] Dom, M., Algorithmic aspects of the consecutive-ones property, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 98, 27-59 (2009) · Zbl 1179.05071
[12] Even, G.; Naor, J. S.; Schieber, B.; Sudan, M., Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica, 20, 151-174 (1998) · Zbl 0897.68078
[13] Festa, P.; Pardalos, P. M.; Resende, M. G., Feedback set problems, (Handbook of Combinatorial Optimization (1999), Springer), 209-258 · Zbl 1253.90193
[14] Garey, M. R.; Johnson, D. S., Computers and Intractability (2002), W.H. Freeman: W.H. Freeman New York
[15] Hecht, M. S.; Ullman, J. D., Flow graph reducibility, (Proceedings of the Fourth Annual ACM Symposium on Theory of Computing STOC ’72 (1972)), 238-250
[16] Hecht, M. S.; Ullman, J. D., Characterizations of reducible flow graphs, J. ACM, 21, 367-375 (1974) · Zbl 0304.68041
[17] Karp, R. M., Reducibility among combinatorial problems, (Miller, R.; Thatcher, J., Complexity of Computer Computations (1972), Plenum Press), 85-103 · Zbl 1467.68065
[18] Karpiński, M., Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete, Theoret. Comput. Sci., 659, 88-94 (2017) · Zbl 1355.68106
[19] Levy, H.; Low, D. W., A contraction algorithm for finding small cycle cutsets, J. Algorithms, 9, 470-493 (1988) · Zbl 0662.68070
[20] Lu, C. L.; Tang, C. Y., A linear-time algorithm for the weighted feedback vertex problem on interval graphs, Inform. Process. Lett., 61, 107-111 (1997) · Zbl 1336.68140
[21] Moore, C.; Mertens, S., The Nature of Computation (2011), OUP: OUP Oxford · Zbl 1237.68004
[22] Nobibon, F. T.; Cherchye, L.; De Rock, B.; Sabbe, J.; Spieksma, F. C., Heuristics for deciding collectively rational consumption behavior, Comput. Econ., 38, 173-204 (2011) · Zbl 1231.91293
[23] Nobibon, F. T.; Hurkens, C. A.J.; Leus, R.; Spieksma, F. C.R., Coloring graphs using two colors while avoiding monochromatic cycles, INFORMS J. Comput., 24, 485-499 (2012) · Zbl 1461.05096
[24] Rosen, B. K., Robust linear algorithms for cutsets, J. Algorithms, 3, 205-217 (1982) · Zbl 0493.68065
[25] Schaefer, T. J., The complexity of satisfiability problems, (Proceedings of the Tenth Annual ACM Symposium on Theory of Computing. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC ’78 (1978), ACM: ACM New York, NY, USA), 216-226 · Zbl 1282.68143
[26] Seymour, P. D., Packing directed circuits fractionally, Combinatorica, 15, 281-288 (1995) · Zbl 0826.05031
[27] Shamir, A., A linear time algorithm for finding minimum cutsets in reducible graphs related databases, SIAM J. Comput., 8, 645-655 (1979) · Zbl 0422.05029
[28] Steurer, D.
[29] Tarjan, R. E., Testing flow graph reducibility, J. Comput. System Sci., 9, 355-365 (1974) · Zbl 0315.68018
[30] Wang, C.-C.; Lloyd, E. L.; Soffa, M. L., Feedback vertex sets and cyclically reducible graphs, J. ACM, 32, 296-313 (1985) · Zbl 0633.68064
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.