CS Paper Radar

The Path Partition Conjecture and 3-(quasi-)Transitive Digraphs

Shamik Ghosh, Jing Huang

cs.DM math.CO ·submitted 2026-10-09 18:30 UTC · v1
theory

Abstract

A digraph $D = (V,E)$ is 3-transitive (respectively, 3-quasi-transitive) if whenever $(u,v,w,z)$ is a directed path of length 3, $(u,z) \in E$ (respectively, $(u,z) \in E$ or $(z,u) \in E$). These digraphs extend the concepts of transitive and quasi-transitive digraphs, respectively. For 3-transitive and 3-quasi-transitive digraphs, only the strong case has been characterized. In this paper, we introduce the notion of semi-acyclic digraphs and use it to describe completely the structure of 3-transitive and 3-quasi-transitive digraphs. As an application of this type of structure description, we prove that the path partition conjecture holds for the class of extended semi-acyclic digraphs, which generalizes two previously known results on the conjecture.

Comment
27 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Decomposing Directed Graphs into Partial Orders is Hard

cs.CC ·2026-10-27 ·Grzegorz Gutowski, Dominik Jilg, Antonio Lauerbach, Mikołaj Rams
theory similarity 0.67
Abstract

Comparability graphs represent partial orders and provide natural building blocks for representing a graph as a union of simpler graphs. The analogous task in the directed setting is to represent a digraph as a union of partial orders. Aboulker et al. [arXiv, 2026] recently introduced the partial order decomposition number as a useful structural parameter in their study of tournaments. Formally, a partial order decomposition of a digraph $D$ is a cover of its arc set by transitive acyclic subdigraphs, each representing a strict partial order on the vertex set of $D$. The partial order decomposition number is the minimum number of such subdigraphs needed. We also consider the partitioning variant, in which every arc belongs to exactly one of the partial orders in the decomposition. We prove that, for every fixed $k\geq 2$, deciding whether a digraph admits a decomposition into at most $k$ partial orders is NP-complete, even for directed acyclic graphs (DAGs). For $k=2$, we reduce from NAE-3-SAT. For $k\geq 3$, we reduce from $k$-Coloring, and the reduction yields DAGs with triangle-free underlying graphs. Both reductions establish hardness for both variants. We further show that the minimum cover size and the minimum partition size can differ even on DAGs.

0.25

Revisiting the directed pathwidth of h-semicomplete digraphs

cs.DS math.CO ·2026-10-30 ·Guilherme C. M. Gomes, Raul Lopes, Matthias Mnich
similarity 0.65
Abstract

A digraph is $h$-semicomplete if every vertex has at most $h$ non-neighbors. In semicomplete digraphs, $k$-triples are obstructions to bounded directed pathwidth with many algorithmic applications: Fradkin and Seymour [JCTB 2013] showed that a large triple contains a subdivision of every small digraph, and triples were used for irrelevant vertex arguments in routing problems by Fomin and Pilipczuk [JCTB 2019] and Gomes, Lopes, and Sau [ICALP 2025]. Fradkin and Seymour also showed that there is a function $f(k)$ such that every semicomplete digraph of directed pathwidth at least $f(k)$ contains a $k$-triple, and their proof gives $f(k)$ triply exponential in $k$. For $h$-semicomplete digraphs, a result of Kitsunai et al. [ESA 2015] also yields a $k$-triple, but only existentially, and finding one in fixed-parameter time remained open. We improve the bound on $f(k)$ to a single exponential and extend the result to $h$-semicomplete digraphs: we show that every $h$-semicomplete digraph of directed pathwidth greater than $(h+1) \cdot k \cdot 2^{27k+9}$ contains a $k$-triple, which we find in polynomial time, and no bound subexponential in $k$ or sublinear in $h$ is possible. We also extend the approximation algorithm for directed pathwidth of Fomin and Pilipczuk to $h$-semicomplete digraphs, so its certificates of large directed pathwidth remain valid. Our proof is much shorter than the analysis of Kitsunai et al., and while their algorithm is exact, ours runs in polynomial time. As an application, we show that Arc-Disjoint Paths on $h$-semicomplete digraphs is fixed-parameter tractable parameterized by the number of paths and $h$, generalizing the semicomplete case. Finally, unlike in semicomplete digraphs, directed pathwidth does not bound directed cliquewidth: for every $k$, some acyclic $1$-semicomplete digraph, so of directed pathwidth zero, has directed cliquewidth at least $k$.

0.25

Acyclic orientations of mixed graphs

cs.DM math.CO ·2026-09-26 ·Jørgen Bang-Jensen, Anders Yeo
theory similarity 0.62
Abstract

A mixed graph $M=(V,E\cup A)$ is acyclic if its directed part $(V,A)$ is an acyclic digraph. In this note we study the so-called orientation completion problem for the class of acyclic mixed graphs. That is, given an acyclic mixed graph $M$ and a property ${\cal P}$; can we orient the edges of $M$ so that the resulting digraph is acyclic and has property ${\cal P}$. We prove that one can decide in polynomial time whether $M$ can be completed to an acyclic digraph with an out-branching from a prescibed vertex $s$, while it is NP-complete to decide whether $M$ has an acyclic orientation which has both an out-branching and an in-branching (a bipolar orientation). We show that it is NP-complete to decide whether $M$ can be oriented so that it contains a directed path between two prescribed vertices. Finally we describe a polynomial algorithm for deciding whether an acyclic digraph $D$ has an out-branching $B^+_s$ such that the digraph $D-A(B^+_s)$ is connected (in the underlying sense). Based on this we pose as an open problem the complexity of deciding whether the edges of an acyclic mixed graph can be oriented so that the result is an acyclic digraph with a non-separating out-branching.

0.09

The Complexity of Hamiltonian Cycles and Paths with Prescribed Walk Lengths

cs.DS ·2026-10-13 ·Hitendra Kumar, Mathieu Mari, R. B. Sandeep
theory similarity 0.61
Abstract · added acknowledgement

Fix a set $S$ of positive integers. An $S$-Hamiltonian cycle is a cyclic ordering of all vertices of a graph such that each consecutive pair is joined by a walk whose length belongs to $S$. We study the complexity of deciding whether an input graph admits such an ordering, together with the corresponding path variants with prescribed or unrestricted endpoints. We complete the complexity classification for undirected graphs. In particular, we prove NP-completeness for every finite nonempty set of odd lengths, resolving an open problem posed by Amarilli, Lombardo, and Monet (WG 2026). For digraphs, all three problems are NP-complete for every fixed finite nonempty $S$ and admit linear-time algorithms when $S$ is cofinite. For other fixed infinite sets $S$, we establish NP-complete and undecidable cases, with undecidability occurring even when $S$ is recursive.

0.23

Counterexamples to the Strong Roberson Conjecture

cs.DM math.COcs.LO ·2026-10-02 ·Arnar Á. Kristjánsson
similarity 0.60
Abstract · 24 pages. v2: expanded introduction, related work and conclusion; improved exposition throughout; smaller explicit counterexamples obtained

We refute the Strong Roberson Conjecture, which asserts that adding any graph outside a graph class closed under minors and disjoint unions strictly increases the distinguishing power of homomorphism counts from that class. More precisely, we construct connected graphs $H$ for which homomorphism counts from graphs excluding $H$ as a minor determine the number of homomorphisms from $H$ to any target graph. We also refute the analogous conjecture with immersions in place of minors. The proof introduces a method for deriving exact homomorphism count dependence from modular equivalences. We obtain these modular equivalences for infinitely many primes using prime-order automorphisms and the corresponding orbit quotients. We complete the refutations by proving that suitable circulant graphs with two jump lengths and related cubic bipartite graphs exclude their corresponding orbit quotients as minors and immersions, respectively.

0.45

Stable Set Reconfiguration in Dense Digraphs

cs.DM cs.CCmath.CO ·2026-10-23 ·Sarah Houdaigoui, Nacim Oijid, Matthieu Petiteau, Alexandre Vigny
similarity 0.59
Abstract

In a directed graph, a stable (or acyclic) set is a set which does not induce a directed cycle. Given a directed graph and two acyclic sets of the same size, the Acyclic-Set-Reconfiguration with Directed Token Sliding (ASR) problem asks whether one can, by iteratively replacing a vertex by an adjacent one, transform the first set into the second one, while maintaining acyclicity during the transformation. In this work, we present a study of the complexity of ASR and provide an FPT algorithm for semi-complete digraphs, when parametrized by the size of the sets being reconfigured, the directed pathwidth (or equivalently, the directed treewidth) of the instance, and a newly introduced parameter called the iteration of the reconfiguration sequence. To the best of our knowledge, the reconfiguration of stable sets has only been studied on undirected graphs, or (more recently) on sparse directed graphs.

0.28

Lettericity Is NP-Complete

cs.CC cs.DM ·2026-09-23 ·Henning Fernau, Samuel German, Kevin Mann, Nils Morawietz
theory similarity 0.59
Abstract · After we first posted this paper on arXiv, Vatter posted a proof that Lettericity is NP-complete which he obtained independently of ours (ar…

The lettericity of a graph $G$ is the smallest size of a set $Σ$ such that there exist $w_1, \ldots, w_{|V(G)|} \in Σ$ and a so-called decoder $D \subseteq Σ^2$ for which $G$ is isomorphic to the letter graph $(\{1, \ldots, |V(G)|\}, \{ij : 1 \le i < j \le |V(G)|, w_iw_j \in D\})$. It took around two decades of the study of lettericity for, in the simpler case of paths, a closed-form expression for its lettericity to be derived; this suggests that the question of whether the lettericity of an arbitrary graph can be computed in polynomial time is nontrivial. Indeed, this question has been raised repeatedly as an open problem in recent literature. We solve this problem by showing that the lettericity problem on arbitrary graphs is NP-complete. We also show that each of the natural ways in which a single part of a structure $(Σ, w_1, \ldots, w_{|V(G)|}, D)$ witnessing the lettericity could be constrained corresponds to an NP-complete problem, which resolves an additional three open problems from the literature; in particular, we show that the coloring extension, word extension, and decoder extension problems are NP-complete. Additionally, we use the reduction in the NP-completeness proof to give a lower bound on algorithms for lettericity under the Exponential Time Hypothesis (ETH): unless the ETH is false, there cannot exist a deterministic algorithm to decide whether the lettericity of an $n$-vertex graph is at most $k$ in time $2^{o(n)}$, even when $n = 6k$. Finally, we complement the known result that Lettericity is fixed-parameter tractable when parameterized by the standard parameter $k$ by providing a fixed-parameter algorithm with respect to the dual parameterization by $n-k$ running in $2^{\mathcal{O}((n-k)^2)} + \mathcal{O}(n)$ time.

0.40

Important Cuts with Logical Constraints: A Meta-Theorem for Eulerian Digraphs

cs.DS ·2026-11-14 ·Václav Blažej, Satyabrata Jana, Jędrzej Olkowski, M. S. Ramanujan, Peter Strulo
top venuetheory similarity 0.58
Abstract · To appear at SODA 2027

Important separators are a standard tool in parameterized cut algorithms. An $S$-$T$ separator is important if it is inclusion-wise minimal and no separator of at most the same size leaves a strict superset of the vertices reachable from $S$ after deletion. Their use relies on a boundedness theorem: for fixed $k$, the number of important $S$-$T$ separators of size at most $k$ is at most a constant ($4^k$ to be precise) independent of the input size, even in directed graphs, and they can be enumerated efficiently. The classical theory, however, controls only the size of the separator, not the structure of the source side cut off by it. Once the source side is required to satisfy a condition such as acyclicity, bipartiteness, or another logical property, the corresponding maximal source sides can be unbounded in general digraphs. This obstruction is fundamentally related to hardness phenomena in directed deletion problems such as Directed Odd Cycle Transversal}. Prior to this work, even in undirected graphs, boundedness of such maximal constrained source sides was known only in more specialized settings, not at the level of generality considered in our work.

0.63