Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT
From MaRDI portal
Publication:2632009
Abstract: 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).
Recommendations
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- Enumerating minimal subset feedback vertex sets
- Enumerating minimal subset feedback vertex sets
- On locating minimum feedback vertex sets
- scientific article; zbMATH DE number 1029225
- scientific article; zbMATH DE number 1342121
- scientific article; zbMATH DE number 1443271
- Approximating minimum feedback vertex sets in hypergraphs
- A Min-Max Theorem on Feedback Vertex Sets
- Minimum \(t P_3\)-saturation graphs
Cites work
- scientific article; zbMATH DE number 6118220 (Why is no real title available?)
- scientific article; zbMATH DE number 5606342 (Why is no real title available?)
- scientific article; zbMATH DE number 3919840 (Why is no real title available?)
- scientific article; zbMATH DE number 3551857 (Why is no real title available?)
- A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
- A contraction algorithm for finding small cycle cutsets
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- Approximating minimum feedback sets and multicuts in directed graphs
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Characterizations of Reducible Flow Graphs
- Coloring graphs using two colors while avoiding monochromatic cycles
- Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
- Feedback vertex set on cocomparability graphs
- Feedback vertex sets and cyclically reducible graphs
- Heuristics for deciding collectively rational consumption behavior
- Interval digraphs: An analogue of interval graphs
- Node listings for reducible flow graphs
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Packing directed circuits fractionally
- Reducibility among combinatorial problems
- Robust linear algorithms for cutsets
- Testing flow graph reducibility
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The complexity of satisfiability problems
- The nature of computation
- Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete
Cited in
(2)
This page was built for publication: Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2632009)
