On the feedback vertex set problem for a planar graph (Q678111)

If a directed graph has cycles, we can remove some nodes so that the remaining graph becomes acyclic. Such a set of nodes is called a feedback vertex set. These nodes could form the set of indices involved in the Schur complement problem. The paper presents an algorithm for solving the feedback vertex set problem for planar digraphs. In particular, planar digraphs with a certain additional condition are considered as they arise from solving systems of linear equations obtained from convection-dominated flow problems. The proposed algorithm requires a computational work linear in the size of the digraph. As a side product, the algorithm for determining the feedback vertex set produces a disjoint decomposition of the digraph into subsets (concentric cycles) mainly consisting of one cycle.