Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT

DOI10.1016/J.TCS.2018.11.009zbMATH Open1421.68088arXiv1809.01998OpenAlexW2891710764WikidataQ128930596 ScholiaQ128930596MaRDI QIDQ2632009FDOQ2632009

Authors: Irena Rusu 

Publication date: 17 May 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

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).

Full work available at URL: https://arxiv.org/abs/1809.01998

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

zbMATH Keywords

NP-completenessfeedback vertex set3-SATflow reducible graphsminimum ones 3-SAT

Mathematics Subject Classification ID

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

Cites Work

• Reducibility among Combinatorial Problems
• Interval digraphs: An analogue of interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The complexity of satisfiability problems
• Title not available (Why is that?)
• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• Title not available (Why is that?)
• Feedback vertex sets and cyclically reducible graphs
• A Linear Time Algorithm for Finding Minimum Cutsets in Reducible Graphs
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• The nature of computation
• Approximating minimum feedback sets and multicuts in directed graphs
• Testing flow graph reducibility
• Characterizations of Reducible Flow Graphs
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Title not available (Why is that?)
• Packing directed circuits fractionally
• Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete
• A contraction algorithm for finding small cycle cutsets
• Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
• Heuristics for deciding collectively rational consumption behavior
• Coloring graphs using two colors while avoiding monochromatic cycles
• Node listings for reducible flow graphs
• Feedback vertex set on cocomparability graphs
• Title not available (Why is that?)
• Robust linear algorithms for cutsets

Cited In (2)

• Hamiltonian problems in directed graphs with simple row patterns
• On the complexity of feedback set problems in signed digraphs

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)