Pushing the frontiers of subexponential FPT time for Feedback Vertex Set

Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, Jean-Florent Raymond · 2025

Read Pushing the frontiers of subexponential FPT time for Feedback Vertex Set by Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, Jean-Florent Raymond (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-17708.txt.

Introduction

Gaétan Berthe and co-authors work on an algorithm problem in graph theory. The problem is how to break all cycles in a graph by removing few points. The task is called Feedback Vertex Set. Fast methods for it are barred in the general case by a known belief.

For special graph families, faster methods do exist, one family at a time. The authors give broad terms on a family that ensure such a method exists. Their terms unite past methods for many families, from flat graphs to disk graphs. They also open the door to new families, like graphs made of thin string shapes.

Catalog record

CREATORGaétan Berthe, Marin Bougeret, Daniel Gonçalves, Jean-Florent Raymond
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE113 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-17708

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Pushing the frontiers of subexponential FPT time for Feedback Vertex Set Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, Jean-Florent Raymond Abstract . The paper deals with the Feedback Vertex Set problem parameterized by the solution size. Given a graph G G and a parameter k k , one has to decide if there is a set S S of at most k k vertices such that G − S G-S is acyclic. Assuming the Exponential Time Hypothesis, it is known that FVS cannot be solved in time 2 o ⁡ ( k ) ​ n 𝒪 ⁡ ( 1 ) 2^{o(k)}n^{\mathcal{O}(1)} in general graphs. To overcome this, many recent results considered FVS restricted to particular intersection graph classes and provided such 2 o ⁡ ( k ) ​ n 𝒪 ⁡ ( 1 ) 2^{o(k)}n^{\mathcal{O}(1)} algorithms. In this paper we provide generic conditions on a graph class for the existence of an algorithm solving FVS in subexponential FPT time, i.e. time 2 k ε ​ poly ( n ) 2^{k^{\varepsilon}}\mathop{\rm poly}(n) , for some ε < 1 \varepsilon<1 , where n n denotes the number of vertices of the instance and k k the parameter. On the one hand this result unifies algorithms that have been proposed over the years for several graph classes such as planar graphs, map graphs, unit-disk graphs, pseudo-disk graphs, and string graphs of bounded degree. On the other hand, it extends the tractability horizon of FVS to new classes that are not amenable to previously used techniques, in particular intersection graphs of “thin” objects like segment graphs or more generally s s -string graphs. 1. Introduction 1.1. Context Given an n -vertex graph G and a parameter k\in\mathbb{N} , the Feedback Vertex Set problem ( FVS for short) asks whether there exists a set S of at most k vertices such that G-S has no cycle. This is a fundamental decision problem in graph theory and one of Karp’s 21 NP-complete problems. Because of its hardness in a classical setting, the problem has been widely studied within the realm of parameterized complexity. This line of research aims to investigate the existence of FPT algorithms , i.e., algorithms that run in time f(k)\cdot n^{\mathcal{O}(1)} , for some computable function f . Such algorithms provide a fine-grained understanding on the time complexity of a problem and describe regions of the input space where the problem can be solved in polynomial time. Note that it is crucial here to obtain good bounds on the function f since the (potentially) super-polynomial part of the running time is confined in the f(k) term. In this direction it was proved that under the Exponential Time Hypothesis of Impagliazzo, Paturi and Zane, FVS does not admit an algorithm with running time 2^{o(k)}n^{\mathcal{O}(1)} (see [ 12 ] ). Nevertheless certain classes of graphs (typically planar graphs) have been shown to admit algorithms with running times of the form 2^{\mathcal{O}(k^{\varepsilon})}n^{\mathcal{O}(1)} (for some \varepsilon<1 ), i.e., where the contribution of the parameter k is subexponential. Such algorithms are called subexponential parameterized algorithms and they are the topic of this paper. Among the numerous existing results on this theme, there are two main directions of research: to improve the running times in the classes where an algorithm is already known, or to extend the tractability horizon of FVS by providing more general settings where subexponential FPT algorithms exist. We are here interested by the second direction, which can be summarized by the following question. Question 1.1 . What are the most general graph classes where FVS admits a subexponential parameterized algorithm ? Historically, a primary source of graph classes studied to make progress on the above question was geometric intersection graphs. In an intersection graph , each vertex corresponds to a subset of some ambient space, and two vertices are adjacent if and only if the subsets intersect. Taking the Euclidean plane as the ambient space, many graph classes can be defined by setting restrictions on the subsets used to represent the vertices. One can for instance consider intersection graphs of disks in the plane, or segments, or Jordan arcs. 1 1 1 In the following, those are called strings. With such subsets, one defines the class of disk graphs , segment graphs , and string graphs respectively. It is also often the case that there are conditions dealing with all the n subsets representing the vertices of a given graph. For example, if we consider disks (resp. segments) one can ask those to have the same diameter (resp. to use at most d different slopes), and this defines the class of unit disk graphs (resp. d -DIR graphs ). When considering strings, one possible property is that any string has at most d points shared with the other considered strings. This defines string graphs with edge-degree at most d . It was recently proved that for a string graph, having bounded edge-degree is in fact equivalent to having bounded degree [ 18 ] . A weaker condition is to ask every pair of the considered strings to intersect on at most s points, this defines s -string graphs . This class generalizes several natural classes such as planar graphs, map graphs, unit-disk graphs, segment graphs, string graphs of bounded degree, and intersection graphs of \alpha -convex bodies that exclude a fixed subgraph (see [ 28 , 23 , 4 ] ). For all these graph classes, FVS is NP-complete, and actually under ETH none of them admits a 2^{o(\sqrt{n})} -time algorithm. Indeed, this lower bound was given in [ 13 ] for induced grid graphs, which form a subclass of unit disk graphs and 2-DIR graphs. On the other hand, for each of the aforementioned classes there is an algorithm solving FVS in subexponential time. More precisely, this algorithm applies to any string graph and runs in time 2^{\TO(n^{2/3})} [ 10 ] . 2 2 2 The notation \TO ignores polylogarithmic factors, i.e. we write g(x)=\TO(f(x)) if for some c we have g(x)=\mathcal{O}(f(x)\cdot\log^{c}x) . Regarding subexponential parameterized algorithms, the case of unit disk graphs was settled with an algorithm whose running time matches the ETH lower bound [ 2 ] . This result uses the fact that these graphs admit vertex partitions into cliques such that each of these cliques is adjacent to only a constant number of the other cliques. Such a property does not hold for the other graph classes mentioned above. However, other techniques have been developed to deal with the other aforementioned classes such as the classes of bounded edge-degree string graphs [ 4 ] , contact-segment and square graphs [ 7 ] , disk graphs [ 25 , 1 ] , or the pseudo-disk graphs [ 8 ] . Note that when dealing with classes of intersection graphs, the representation of the input (if known) could be used by the algorithm. Some of these algorithms are robust , meaning that the input graph G is provided using one of the classical graph data structures, where there is no indication of the intersection model of G . Because the recognition problem is difficult for most of the classes discussed above, robustness is a substantial advantage. 1.2. Our contribution Toward answering 1.1 ,

Read the complete text