Towards Transitive-free Digraphs

Ankit Abhinav, Satyabrata Jana, Abhishek Sahu · 2025

Read Towards Transitive-free Digraphs by Ankit Abhinav, Satyabrata Jana, Abhishek Sahu (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-2503-10541.txt.

Introduction

Ankit Abhinav, Satyabrata Jana, and Abhishek Sahu present a 2025 paper on trimming directed graphs until almost no redundant arrows remain. An arrow is redundant when another path already links the same two points. The task is to delete few vertices so that the graph left behind has at most a set number of such arrows.

The authors study this relaxed task across many graph families: layered graphs with no cycles, flat ones, contest graphs where each pair meets once, and wider kin of those. Some families admit fast exact methods, they show. For others they give bounds or fixed parameter methods. The paper maps where the task is easy and where it stays hard.

Catalog record

CREATORAnkit Abhinav, Satyabrata Jana, Abhishek Sahu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-10541

Browse the full library · About the Tower of Babel

Full text

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

Towards Transitive-free Digraphs Ankit Abhinav, Satyabrata Jana, Abhishek Sahu Abstract In a digraph D D , an arc e = ( x , y ) e=(x,y) in D D is considered transitive if there is a path from x x to y y in D − e D-e . A digraph is transitive-free if it does not contain any transitive arc. In the Transitive-free Vertex Deletion (TVD) problem, the goal is to find at most k k vertices S S such that D − S D-S has no transitive arcs. In our work, we study a more general version of the TVD problem, denoted by ℓ \ell -Relaxed Transitive-free Vertex Deletion ( ℓ \ell -RTVD ), where we look for at most k k vertices S S such that D − S D-S has no more than ℓ \ell transitive arcs. We explore ℓ \ell -RTVD on various well-known graph classes of digraphs such as directed acyclic graphs (DAGs), planar DAGs, α \alpha -bounded digraphs, tournaments, and their multiple generalizations such as in-tournaments, out-tournaments, local tournaments, acyclic local tournaments, and obtain the following results. Although the problem admits polynomial-time algorithms in tournaments, α \alpha -bounded digraphs, and acyclic local tournaments for fixed values of ℓ \ell , it remains NP -Hard even in planar DAGs with maximum degree 6. In the parameterized realm, for ℓ \ell -RTVD on in-tournaments and out-tournaments, we obtain polynomial kernels parameterized by k + ℓ k+\ell for bounded independence number. But the problem remains fixed-parameter intractable on DAGs when parameterized by k k . 1 Introduction The act of removing vertices from a directed graph in a manner that ensures specific properties in the resulting graph has a rich history in the field of graph theory. Often, this process serves as a preliminary stage for various graph drawing algorithms, including 3D orthogonal graph drawings [ 1 ] , right-angle-crossing drawings [ 2 ] , hierarchical and upward drawings [ 3 ] . For instance, one may consider Eulerian orientations, where each vertex has an equal in-degree and out-degree, acyclic orientations that yield a directed acyclic graph, or singly connected orientations that guarantee at most one path between any pair of vertices [ 4 ] . Our paper focuses on investigating a significant property of directed graphs: transitive-freeness. Specifically, we delve into the problem of removing vertices from a graph so that only a limited number of transitive arcs remain in the resulting structure. In a directed graph D , an arc e=(u,v) is considered transitive if at least one path exists from u to v in the graph D-e [ 5 ] . A digraph is said to be transitive-free if it contains no transitive arcs. In a transitive-free digraph, each arc plays a crucial role in maintaining connectivity that any combination of the remaining arcs cannot achieve. In other words, every arc is essential for preserving connectivity. The optimization version of this problem, referred to as the Transitive-free Vertex Deletion (TVD), aims to find the minimum number of vertices to be deleted from the graph to achieve transitive freeness. We investigate a generalization of this problem known as \ell -Relaxed Transitive-free Vertex Deletion ( \ell -RTVD ), where the digraph can have a maximum of \ell transitive arcs. In many graph layout problems, existing algorithms often rely on an initial orientation computation for the given graph. In such scenarios, reducing the number of transitive arcs in this orientation tends to affect the overall readability of the layout positively. Despite its similarities to the Singly Connected Vertex Deletion [ 4 ] and Feedback Vertex Set [ 6 ] problems, the Transitive-free Vertex Deletion (TVD) problem has received relatively little attention. Only recently, Binucci et al. [ 5 ] investigated a slightly different variant of the problem, which involved orienting edges in an undirected graph to minimize the count of transitive arcs. Their study demonstrated that the problem is NP -hard for general graphs. In contrast, our paper takes a distinct approach by exploring the vertex deletion version of the problem. \ell -Relaxed Transitive-free Vertex Deletion ( \ell -RTVD) Input: A digraph D , a non-negative integer k . Question: Does there exist a set S\subseteq V(D) such that |S|\leq k and D-S has at most \ell transitive arcs? 1.1 Our contribution and methods To begin with, in Section 3 , we show that \ell -RTVD is NP -hard on directed acyclic graphs (DAGs), even when the underlying undirected graph is planar and has maximum degree six. This result is derived through a hardness reduction from Vertex Cover on planar graphs with maximum degree three [ 7 ] . Subsequently, we derive several polynomial-time algorithms (for constant \ell ) for various widely recognized subclasses of directed graphs, including tournaments, \alpha -bounded digraphs, and acyclic local tournaments. For instance, our algorithm for tournaments (Section 4.1 ) is constructed by combining Frankl’s result on a uniform family of set system [ 8 ] with the straightforward observation that any tournament with more than four vertices contains a transitive arc. In the case of \alpha -bounded digraphs, we utilize the Gallai-Milgram theorem [ 9 ] to establish an upper bound of \mathcal{O}(\alpha^{2}) on the size of a transitive-free digraph, thereby enabling the development of a polynomial-time algorithm (Section 4.2 ). Furthermore, employing a dynamic programming approach, we design our third polynomial-time algorithm specifically tailored for acyclic local tournaments (Section 4.3 ). Additionally, we study \ell -RTVD in the parameterized framework focusing on various subclasses of digraphs and obtain the following results. In Section 5 , we show that this problem remains W[1] -hard on directed acyclic graphs (DAGs) when parameterized by the solution size ( k ). To prove this, we utilize a reduction from Vertex Multicut in DAGs, which is already known to be W[1] -hard when parameterized by the solution size [ 10 ] . However, for both in-tournaments and out-tournaments, we design polynomial (in k+\ell+\alpha ) size kernels (Section 6 ), where \alpha is the independence number (equivalently, the graph is \alpha -bounded). In designing these kernels, the concept of the cut preserving set [ 11 ] plays a crucial role. Finally, in Section 7 , we explore the problem for the special case when \ell=0 on in-tournaments (and out-tournaments) and show that the problem reduces to the 3-Hitting Set problem, thus admitting an FPT algorithm and a quadratic vertex kernel. 2 Preliminaries For a positive integer n , [n] denotes the natural number set \{1,2,\ldots,n\} . For a digraph, D , V(D) and A(D) denote the set of vertices and arcs in D , respectively. A directed arc from u to v is denoted by the ordered pair (u,v) . For a set S\subseteq V(G) , D-S denotes the digraph obtained by deleting S from D and D[S] denotes the subgraph of D induced on S . Similarly for a set A^{\prime}\subseteq A(D) , D-A^{\prime} denotes the digraph obtained by deleting the arcs A^{\prime} from D . By N^{+}_{D}(v)=\{u|(v,u)\in A(D)\} we denote the set of out-neighbors of v . Similarly, N^{-}_{D}(v)=\{u|(u,v)\in A(D)\} denotes the set of in-neighbors of v . We may not use D in the notation when the context is clear. A path

Read the complete text