Source-linked AI summary
Orientations without transitive arcs for cubic graphs and phylogenetic networks
Janosch Döcker, Simone Linz
TL;DR
The paper addresses whether non-transitive st-orientations remain hard on cubic graphs and whether the analogous shortcut-free phylogenetic orientation problem is hard. It develops cubic-graph gadgets and reductions, proving NP-completeness for designated and freely chosen source–sink variants and for unrooted binary phylogenetic networks.
Problem
Whether NT-st-Orientation remains NP-complete for cubic graphs, including variants with designated or freely chosen source and sink, and whether the analogous phylogenetic problem is NP-complete.
Method
The paper introduces a cubic-compatible fork gadget and uses reductions from a variant of Not-All-Equal 3-SAT, then applies the graph result to phylogenetic networks.
Results
NT-st-Orientation is NP-complete for cubic graphs, including instances with degree-one s and t and all other vertices degree three; Phylogenetic NT-Orientation is also NP-complete.
Takeaways & Limitations
The results close the degree gap for NT-st-Orientation and establish a complexity connection between undirected graph orientations and unrooted binary phylogenetic networks.
Takeaways & Limitations
The paper leaves open whether analogous gadgets satisfy the topological constraints of other binary phylogenetic network classes and whether further links exist between the two orientation areas.
Abstract
from arXiv · showhide
An $st$-orientation of an undirected graph $G$ is an acyclic digraph with a single source $s$ and a single sink $t$ that can be obtained from $G$ by assigning a direction to each edge. The classical problem of deciding if an undirected graph $G$ has an $st$-orientation can be solved efficiently. On the other hand, deciding if an $st$-orientation of $G$ exists that does not have any transitive arc is NP-complete, even if each vertex of $G$ has degree at most four. Here we show that this last decision problem remains NP-complete if $G$ is cubic, which settles an open question by Binucci et al. (2025). We obtain NP-completeness for two variants of the problem: (i) $s$ and $t$ are fixed and given as part of the input and (ii) $s$ and $t$ can be chosen freely. We then use these results to investigate the computational complexity of a problem that arises in computational evolution. Specifically, we show that the problem of deciding if an unrooted binary phylogenetic network has an orientation as a rooted binary phylogenetic network without any shortcuts (the analog of a transitive arcs in phylogenetics) is NP-complete. Our results connect the two (mostly) distinct research areas of orienting undirected graphs and orienting unrooted phylogenetic networks.
1. Introduction
The paper studies constrained acyclic orientations, focusing on non-transitive st-orientations and their complexity in cubic graphs and phylogenetic networks.
- Orientation problems: An st-orientation is an acyclic orientation with one source s and one sink t, and a transitive arc has an alternate directed path between its endpoints.Such orientations are useful in planarity testing, graph drawing, and phylogenetics.
- Orientation problems: NT-st-Orientation asks whether a graph with designated s and t has a non-transitive st-orientation.Earlier work established NP-completeness for degree-at-most-four graphs and fixed-parameter tractability parameterized by treewidth.
- Phylogenetic application: The phylogenetic application asks whether an unrooted binary network can be oriented as a rooted binary network without transitive arcs, also called shortcuts.The paper proves this decision problem NP-complete.
- Phylogenetic application: Binary phylogenetic networks restrict internal vertices to degree three because higher-degree vertices indicate insufficiencies in reconstruction data.Rooted networks encode ancestor-descendant relationships through directed paths.
- Paper approach: The paper introduces a cubic-graph gadget and uses it in a Karp reduction to establish hardness for NT-st-Orientation.The construction proceeds through a fork gadget and a variant of Not-All-Equal 3-SAT.
2. Preliminaries
The preliminaries define graph orientations and NT-st-Orientation, then record structural observations used in the paper’s hardness arguments.
- Graph notation: A cubic graph has degree three at every vertex, and directed graphs additionally use in-degree, out-degree, sources, and sinks.These definitions support the later restriction to cubic instances.
- Graph transformations: Suppressing a degree-2 vertex replaces its two incident edges with an edge joining its neighbors, while subdivision performs the reverse operation.These operations define when one graph is a subdivision of another.
- Orientations: An orientation replaces every undirected edge with exactly one directed arc, while an st-orientation is acyclic with unique source s and unique sink t.Every other vertex has at least one incoming and one outgoing arc.
- Decision problem: NT-st-Orientation asks whether an undirected graph with designated vertices s and t has a non-transitive st-orientation.The example in Figure 1 is a yes-instance.
- Structural observations: Reversing every arc converts a non-transitive st-orientation into a non-transitive ts-orientation.This symmetry is stated as Observation 2.1.
- Structural observations: In any underlying cycle of a non-transitive st-orientation, at least two arc directions must be reversed to create a directed cycle.A non-transitive st-orientation also forbids induced triangles.
3. Fork gadget
The section introduces a cubic-compatible fork gadget and proves that non-transitive st-orientations constrain its edge directions. These constraints support a split gadget that propagates one edge direction to multiple edges.
- Fork gadget: The fork gadget has only degree-1 and degree-3 vertices, unlike the earlier version involving degree-1, degree-2, and degree-4 vertices.It is defined as a graph isomorphic to the graph depicted in Figure 2.
- Orientation constraints: The fork gadget links the direction of {x, v} to the directions of {a0, x0} and {a1, x1}.If (x, v) is directed, both corresponding edges point from ai to xi; if (v, x) is directed, both reverse.
- Ladder constraints: The ladder graph L3 admits exactly four possible edge-orientation patterns in the stated non-transitive st-orientation setting.These four patterns are listed as (i)–(iv) and illustrated in Figure 3.
- Orientation constraints: If (x, v) is an arc, v has in-degree one and out-degree two, while a0 and a1 have in-degree two and out-degree one.This is the first of the two possible degree configurations established for the fork gadget.
- Orientation constraints: If (v, x) is an arc, v has in-degree two and out-degree one, while a0 and a1 have in-degree one and out-degree two.This is the reverse degree configuration of the fork gadget.
4. Non-transitive st-orientations of cubic graphs
The paper proves NP-completeness of NT-st-Orientation for cubic graphs using a polynomial-time reduction from Positive NAE-3-SAT-E4 and specialized gadgets. The construction also yields variants with constrained terminals and supports later results when the source and sink are not given.
- Reduction framework: The reduction uses a new fork gadget and a restricted Positive NAE-3-SAT-E4 instance, where every clause has three variables and each variable appears exactly four times.The fork gadget is central to avoiding degree-4 vertices in the construction.
- Reduction framework: Clause vertices encode literal truth values by edge directions, and the constructed graph has a non-transitive orientation exactly when the formula is nae-satisfiable.Edges directed toward a clause vertex represent true literals, while edges directed away represent false literals.
- Gadget construction: The source and sink gadgets simulate high-degree terminals while preserving acyclic, non-transitive orientations through degree-three building blocks.The source gadget enforces one source and the sink gadget enforces one sink; their interface vertices have complementary in-degree and out-degree patterns.
- Gadget construction: Variable gadgets consist of two fork gadgets and one split gadget S4, reflecting that each variable appears exactly four times.Their orientations transmit a consistent truth value to the four clause occurrences.
- Main result: NT-st-Orientation is NP-complete for cubic graphs, with the proof obtaining a graph of maximum degree three before suppressing degree-two vertices.The equivalence between formula satisfiability and graph orientation is preserved through the intermediate graph and the final cubic graph.
- Main result: A related corollary establishes NP-completeness when the designated source and sink have degree one and all other vertices have degree three, supporting the variant where terminals are not part of the input.The paper then argues that the unrestricted-terminal version remains NP-complete on cubic graphs.
5. Non-transitive orientations of unrooted phylogenetic networks
The paper defines non-transitive orientations for unrooted binary phylogenetic networks and proves that deciding whether such an orientation exists is NP-complete. The proof reduces from non-transitive st-orientation using a root gadget and establishes polynomial-time verification.
- Definitions: An unrooted binary phylogenetic network is a leaf-labeled simple connected graph whose vertices have degree one or three.A rooted binary network is an acyclic digraph with one root, labeled leaves, and internal vertices of the specified in-degree and out-degree types.
- Definitions: A rooted phylogenetic network orients an unrooted network by subdividing one edge with the root and directing every edge; non-transitivity forbids shortcut arcs.An arc is transitive when another directed path connects its endpoints without using that arc.
- Decision problem: Phylogenetic NT-Orientation asks whether an unrooted phylogenetic network has a rooted phylogenetic network orientation that is non-transitive.For a network with one leaf, this is equivalent to a non-transitive st-orientation with the root as source and the leaf as sink.
- Reduction: The reduction from NT-st-Orientation uses a root gadget whose orientation properties force the root placement and a directed edge toward the original source.The root gadget is depicted in Figure 12, and Lemma 5.1 establishes these structural properties.
- Complexity result: Phylogenetic NT-Orientation is NP-complete.Membership in NP follows because rootedness, acyclicity, and non-transitivity can be verified in polynomial time; NP-hardness follows from the reduction.
6. Conclusion
The paper establishes NP-completeness for non-transitive st-orientation on cubic graphs and extends this hardness to freely chosen source and sink vertices. It also proves NP-completeness for orienting unrooted binary phylogenetic networks as rooted binary networks without shortcuts.
- The paper proves that deciding whether a cubic graph has a non-transitive st-orientation is NP-complete, settling an open question.
- The hardness result closes the degree gap between trivial cases at maximum degree two and previously known NP-completeness at maximum degree four.
- NP-completeness remains when the source and sink are chosen freely rather than designated in the input.
- The paper transfers these results to show NP-completeness for deciding whether an unrooted binary phylogenetic network has a non-transitive rooted-binary orientation.
- The conclusion identifies open questions about higher-degree regular graphs, cycle restrictions, stronger arc-reversal conditions, and other binary phylogenetic-network classes.