# Finding forest-orderings of tournaments is NP-complete††thanks: This work is
funded by group Casino/ENS Chair on Algorithmics and Machine Learning, ELIT
(ANR-20-CE48-0008-01), and by project 22-17398S (Flows and cycles in graphs on
surfaces) of Czech Science Foundation.

Pierre Aboulker  DIENS, École normale supérieure, CNRS, PSL University, Paris,
France.  Guillaume Aubian  DIENS, École normale supérieure, CNRS, PSL
University, Paris, France.  Charles University, Prague, Czech Republic.  Raul
Lopes  DIENS, École normale supérieure, CNRS, PSL University, Paris, France.
LIRMM, Université de Montpellier, Montpellier, France.

###### Abstract

Given a class of (undirected) graphs $\mathcal{C}$, we say that a FAS $F$ is a
$\mathcal{C}$-FAS if the graph induced by the edges of $F$ (forgetting their
orientations) belongs to $\mathcal{C}$. We show that deciding if a tournament
has a $\mathcal{C}$-FAS is NP-complete when $\mathcal{C}$ is the class of all
forests. We are motivated by connections between $\mathcal{C}$-FAS and
structural parameters of tournaments, such as the dichromatic number, the
clique number of tournaments, and the strong Erdős-Hajnal property.

##  1 Introduction

Given a tournament $T$, a _Feedback Arc Set_ (_FAS_ for short) is a set of
arcs $F$ of $T$ such that $T\setminus F$ is acyclic. Feedback arc sets in
tournaments are well studied from the combinatorial [15, 16, 21, 22, 29, 33],
statistical [23], and algorithmic [3, 4, 10, 14, 12, 19, 31, 32] points of
view.

Given a class of (undirected) graph $\mathcal{C}$, we say that a FAS is a
$\mathcal{C}$-FAS if the graph induced by the edges of $F$ (forgetting their
orientations) belongs to $\mathcal{C}$, and we call _$\mathcal{C}$ -FAS
Problem_ the associated decision problem, that is deciding if a tournament has
a $\mathcal{C}$-FAS. The goal of this paper is to prove the following:

######  Theorem 1.1.

The $\mathcal{C}$-FAS Problem is NP-complete when $\mathcal{C}$ is the set of
forests.

Motivations and related works
Let us motivate the $\mathcal{C}$-FAS Problem by showing its link with several
studied problems in tournament theory. First, let us abuse notation and refer
to a FAS $F$ of a tournament as the undirected graph induced by the edges of
$F$ (forgetting their orientations).

Given a tournament $T$, and a total order $\prec$ on $V(T)$, we denote by
$T^{\prec}$ the (undirected) graph with vertex set $V(T)$ and edge $uv$ if
$u\prec v$ and $vu\in A(D)$. We call it the _backedge graph_ of $T$ with
respect to $\prec$. Observe that $F$ is a FAS of $T$ if and only if there is
an ordering $\prec$ such that $F=T^{\prec}$.

Given a tournament $T$, we denote by $\operatorname{\overrightarrow{\chi}}(T)$
its dichromatic number, that is the minimum integer $k$ such that the set of
vertices of $T$ can be partitioned into $k$ transitive tournaments. The
dichromatic number of tournaments has recently been a centre of interest [8,
20, 24], in particular because of the bridges it creates between tournament
theory and (undirected) graph theory. For example, a tournament version [5] of
the Erdős-Hajnal Conjecture [18] has been studied quite a lot [9, 27, 34, 35],
as well as a tournament version [28, 25] of the El-Zahar-Erdős Conjecture
[17]. A better understanding of tournaments could thus lead to a better
understanding of graphs.

Let $T$ be a tournament and $\prec$ an ordering of its vertices. It is
straightforward that every independent set of $T^{\prec}$ induces a transitive
subtournament of $T$. As a consequence, we have that
$\operatorname{\overrightarrow{\chi}}(T)\leq\chi(T^{\prec})$. Conversely, by
taking an ordering built from a
$\operatorname{\overrightarrow{\chi}}(T)$-dicolouring, that is taking colour
classes one after the other, and ordering each colour class in a topological
ordering, we get that:

$\operatorname{\overrightarrow{\chi}}(T)=\min\,\big{\\{}\chi(T^{\prec}):\mbox{$\prec$
is a total order of $V(D)$}\big{\\}}$ (1)

Now, it is straightforward that a tournament $T$ is $k$-dicolourable if and
only it contains a $k$-colourable FAS. Hence, deciding if a tournament is
$k$-dicolourable is equivalent with deciding if a tournament has a
$k$-colourable FAS. This problem has been proved to be NP-complete for every
$k\geq 2$ [11]. In particular, the $\mathcal{C}$-FAS problem is NP-complete
when $\mathcal{C}$ is the class of bipartite graphs. Our result can be seen as
a strengthening of this result.

Inspired by (1), the clique number $\operatorname{\overrightarrow{\omega}}(T)$
of a tournament $T$ has recently been defined [1] (see also [26]) as follows:

$\operatorname{\overrightarrow{\omega}}(T)=\min\,\big{\\{}\operatorname{\overrightarrow{\omega}}(T^{\prec}):\mbox{$\prec$
is a total order of $V(T)$}\big{\\}}$

Hence, $\operatorname{\overrightarrow{\omega}}(T)\leq k$ if and only if $T$
has a FAS $F$ inducing a graph with clique number at most $k$. Denoting
$\mathcal{C}_{k}$ the class of graphs with clique number at most $k$, deciding
if a tournament has clique number at most $k$ is equivalent with the
$\mathcal{C}_{k}$-FAS problem. The problem of computing the clique number of a
tournament has been mentioned in [30] and in [1]. It has very recently been
proved [6] to be NP-complete for $k\geq 3$ and is still open for $k=2$.

A tournament $H$ has the _strong Erdős-Hajnal property_ if there exists
$\epsilon_{H}>0$ such that every $H$-free tournament $T$ contains two disjoint
subset of vertices $A$ and $B$, such that $|A|,|B|\geq\epsilon_{H}|V(T)|$ and
all arcs between $A$ and $B$ are oriented from $A$ to $B$. Chudnovsky et al.
[13] conjectured that a tournament $H$ has the strong Erdős-Hajnal property if
and only if $H$ admits a FAS inducing a forest, showing that these tournaments
might play an important role in tournament theory.

Structure of the paper
Definitions and some preliminaries results are given in section 2. The proof
of Theorem 1.1 is a reduction from $3$-SAT. Given an instance $\mathcal{I}$ of
$3$-SAT, we construct a tournament $T_{\mathcal{I}}$ such that
$T_{\mathcal{I}}$ has polynomial size (in the size of $\mathcal{I}$) and has a
forest-ordering if and only if $\mathcal{I}$ is a satisfiable instance. We
explain how to construct $T_{\mathcal{I}}$ in Section 3.1. We prove that if
$T_{\mathcal{I}}$ has a forest-ordering, then $\mathcal{I}$ is a satisfiable
instance in Section 3.2, and finally, we prove that if $\mathcal{I}$ is a
satisfiable instance, then $T_{\mathcal{I}}$ has a forest-ordering in Section
3.3.

##  2 Definitions an preliminaries

We refer the reader to [7] for standard definitions.

A _tournament_ $T$ is an orientation of a complete graph, we denote by $V(T)$
its set of vertices and by $A(T)$ its sets of arcs. The _transitive
tournament_ on $n$ vertices is the unique acyclic tournament on $n$ vertices.

An _ordered tournament_ is a pair $(T,\prec)$ where $T$ is a tournament and
$\prec$ is a total ordering of $V(T)$. If $uv\in A(T)$ with $v\prec u$ we say
that $uv$ is a _back-arc_ of $(T,\prec)$ and a _forward-arc_ otherwise. We
denote by $T^{\prec}$ the (undirected) graph with vertex set $V(T)$ and arc
set $\\{uv\mid\text{ if }v\prec u\text{ and }uv\in A(T)\\}$, and call it the
_backedge graph_ of $T$ with respect to $\prec$.

Let $T$ be a tournament. A _topological-ordering_ of $T$ is an ordering of
$V(T)$ such that every arc is a forward arc. Note that only transitive
tournaments admit a topological ordering. A _(tree) forest-ordering_ of $T$ is
an ordering $\prec$ of $V(T)$ such that $T^{\prec}$ is a (tree) forest.

For an ordered tournament $(T,\prec)$ and $X,Y\subseteq V(T)$, we write
$X\prec Y$ to say that every vertex of $X$ precedes every vertex of $Y$. If
$X=\\{v\\}$ we drop the brackets from the notation and simply write $v\prec Y$
or $Y\prec v$. If $V(T^{\prime})\prec v$ or $v\prec V(T^{\prime})$ for a
subtournament $T^{\prime}$ of $T$, we shorten the notation to $T^{\prime}\prec
v$ and $v\prec T^{\prime}$.

We write $x\rightarrow y$ to say that there is an arc from $x$ to $y$. Given
two disjoint sets of vertices $X,Y$ of a tournament $T$, we write
$X\Rightarrow Y$ to say that for every $x\in X$ and for every $y\in Y$, $xy\in
A(T)$. When $X=\\{x\\}$ we write $x\Rightarrow Y$. We also use the symbol
$\Rightarrow$ to denote a composition operation on tournaments: for two
tournaments $T_{1}$ and $T_{2}$, $T_{1}\Rightarrow T_{2}$ is the digraph
obtained from the disjoint union of $T_{1}$ and $T_{2}$ by adding all arcs
from $V(T_{1})$ to $V(T_{2})$.

For a positive integer $k$, we denote by $[k]$ the set containing every
integer $i$ such that $1\leq i\leq k$.

Preliminaries results
As observed in the introduction, an ordering $\prec$ of a tournament $T$ is a
forest-ordering if and only $T^{\prec}$ if a forest. All along the paper, we
look at $T^{\prec}$ to prove that $\prec$ is a forest ordering or not.

The following simple technical lemma is used several times to prove properties
of forest-orderings.

######  Lemma 2.1.

Let $(T,\prec)$ be an ordered tournament. Let $a,b\in V(T)$, $X\subseteq
V(T)\setminus\\{a,b\\}$ and assume that $a\Rightarrow X\Rightarrow b$. If
$b\prec a$, then each vertex of $X$ is adjacent to $a$ or $b$ in $T^{\prec}$.

###### Proof.

Let $x\in X$. If $x\prec a$, then $ax\in E(T^{\prec})$, and if $a\prec x$,
then $b\prec x$ and $bx\in E(T^{\prec})$. ∎

Now, we describe a tournament that admits a unique forest-ordering which, in
particular, is a tree-ordering. This statement was verified by a program
implementing the code described in section 6.

######  Lemma 2.2.

The tournament depicted in Figure 1 has a unique forest-ordering, which is the
one shown in Figure 1. This ordering is tree-ordering.

$a$$b$$c$$d$$e$$f$$g$$h$ Figure 1: A tournament on eight vertices admitting a
unique forest-ordering (left to right on the figure). Only back-arcs are
drawn.

Let $n\geq 1$ and let $T_{1}$ and $T_{2}$ be transitive tournaments with
topological ordering $(u_{1},\dots,u_{n})$ and $(v_{1},\dots,v_{n})$
respectively. A _back-arc matching from $T_{2}$ to $T_{1}$_ is the following
set of arcs between $T_{1}$ and $T_{2}$: $\\{v_{i}u_{i}\mid
i\in[n]\\}\cup\\{u_{j}v_{i}\mid i,j\in[n]\text{ and }i\neq j\\}$. Hence, if
$u_{1}\prec\ldots\prec u_{n}\prec v_{1}\prec\ldots\prec v_{n}$ in an ordering
$\prec$ of a tournament containing $T_{1}$ and $T_{2}$, the back-arc matching
translates into the matching $\\{u_{i}v_{i}\mid i\in[n]\\}$ in $T^{\prec}$ and
there are no other edges in $T^{\prec}$. See Figure 2.

$T_{1}$$T_{2}$ Figure 2: A back-arc matching from a transitive tournament
$T_{2}$ to a transitive tournament $T_{1}$. Only back-arcs are drawn.

##  3 The reduction

###  3.1 The construction of $T_{\mathcal{I}}$

Let $\mathcal{I}$ be an instance of $3$-SAT with $n$ variable and $k$ clauses.
We consider an arbitrary ordering $x_{1},\ldots,x_{n}$ of the variables and
$C_{1},\ldots,C_{k}$ of the clauses. We also consider that for $i\in[k]$, each
clause $C_{i}$ is formed by an ordered trio of literals. This naturally
implies an ordering $\ell_{1}$, $\ell_{2}$, $\ell_{3}$, $\ldots$,
$\ell_{3k-2}$, $\ell_{3k-1}$, $\ell_{3k}$ of the literals as they occur in the
clauses, i.e. for $j\in[k]$ we have
$C_{j}=(\ell_{3j-2}\vee\ell_{3j-1}\vee\ell_{3j})$.

This subsection is dedicated to the construction of the tournament
$T_{\mathcal{I}}$. We are actually going to construct an ordered tournament
$(T_{\mathcal{I}},\prec^{*})$. The order $\prec^{*}$ is used to simplify the
description of $T_{\mathcal{I}}$, as many arcs of $T_{\mathcal{I}}$ are
forward-arcs with respect to $\prec^{*}$. It is also used in Section 3.3 where
given an assignment of $\mathcal{I}$, we need to deduce from it a forest-
ordering of $T_{\mathcal{I}}$. The forest-ordering will be found by perturbing
$\prec^{*}$ a little bit.

The construction of $(T_{\mathcal{I}},\prec^{*})$ will be done in two steps.
We first describe the construction of the ordered tournament
$(T_{B},\prec^{*})$, called the _base tournament_ , to which gadgets will be
added later to get $(T_{\mathcal{I}},\prec^{*})$.

####  3.1.1 The base tournament $(T_{B},\prec^{*})$

To build $(T_{B},\prec^{*})$, we start with vertices
$v_{1},\overline{v}_{1},\dots,v_{n},\overline{v}_{n},\ell_{1},\dots,\ell_{3k}$
in this order. We set
$\mathcal{V}=\\{v_{1},\overline{v}_{1},\ldots,v_{n},\overline{v}_{n}\\}$ and
$\mathcal{L}=\\{\ell_{1},\dots,\ell_{3k}\\}$. For every
$x\in\mathcal{V}\cup\mathcal{L}$, we add a set of vertices $M_{x}$111$M$ stand
for Magical, which is the name we gave to the tournament that has a unique
forest-ordering right after $x$ in the ordering, such that $T_{B}[M_{x}]$ is
the tournament depicted in Figure 1, and

  * •

$x\Rightarrow M_{x}$,

  * •

$\prec^{*}$ restricted to $M_{x}$ is the unique forest-ordering of $M_{x}$,
and

  * •

all non-defined arcs as forward-arcs.

This terminates the construction of $(T_{B},\prec^{*})$. Each $v_{i}$,
$\overline{v}_{i}$ represents respectively the variable $x_{i}$ and its
negation, and $\ell_{i}$ represent the $i^{th}$ literal.

For every $x\in\mathcal{V}\cup\mathcal{L}$, the smallest (most) vertex of
$T_{B}[M_{x}]$ (vertex $a$ in Figure 1) plays a very important role (as we
explain below), and is called $\ell_{x}$. For every
$x\in\mathcal{V}\cup\mathcal{L}$, we call $B_{x}$ the tournament
$T_{B}[\\{x\cup M_{x}\\}]$ and $\prec_{x}$ the restriction of $\prec^{*}$ to
$B_{x}$. $(B_{x},\prec_{x})$ is called a _block_.

In Section 3.2, we are given a forest-ordering $\prec$ of $T_{\mathcal{I}}$
and we need to deduce from it a truth assignment of the variables that satisfy
$\mathcal{I}$. This will be done using the position of each vertex
$x\in\mathcal{V}\cup\mathcal{L}$ with respect to $\ell_{x}$.

In Section 3.3, we are given an instance $\mathcal{I}$ and we want to
construct a forest-ordering of $T_{\mathcal{I}}$ from it. This forest-ordering
will be obtained from $\prec^{*}$, by placing the vertices $x$ in
$\mathcal{V}\cup\mathcal{L}$ on the left or on the right of $\ell_{x}$
depending on the truth assignment received by the variable it represents.

####  3.1.2 The gadgets

We now add some gadgets to $(T_{B},\prec^{*}$), on top of each block $B_{x}$.

For each variable $x_{i}$, denote by ${\sf occ}(x_{i})$ the number of
occurrences of the literal $x_{i}$ and by ${\sf occ}(\overline{x}_{i})$ the
number of occurrences of the literal $\overline{x}_{i}$.

For every $v\in\mathcal{V}$, we define the gadget $G_{v}$ associated with $v$
to be the transitive tournament on $7+7{\sf occ}(\overline{v})$ vertices. We
first partition the vertices of $G_{v}$ into a set $N_{v}$ containing the
first $2+2{\sf occ}(\overline{v})$ vertices, and a set $Y_{v}$ containing the
remaining $5+5{\sf occ}(\overline{v})$ vertices. We then partition $N_{v}$
(resp. $Y_{v}$) into $1+{\sf occ}(\overline{v})$ parts of size $2$ (resp. of
size $5$) as follows:

$N_{v}=N_{v}^{\overline{v}}\sqcup N_{v}^{1}\sqcup\dots\sqcup N_{v}^{{\sf
occ}(\overline{v})}\quad\text{ and }\quad Y_{v}=Y_{v}^{\overline{v}}\sqcup
Y_{v}^{1}\sqcup\dots\sqcup Y_{v}^{{\sf occ}(\overline{v})}$

Let us now explain how we define the gadget associated with vertices in
$\mathcal{L}$. Let $\ell\in\mathcal{L}$ and assume $\ell$ represents the
variable $v_{i}$ or $\overline{v_{i}}$ and is part of the clause $C$. The
gadget $G_{\ell}$ associated with $\ell$ is a transitive tournament on $9$
vertices. We partition $G_{\ell}$ into a set $N_{\ell}$ containing the first
four vertices of $G_{\ell}$ and a set $Y_{\ell}$ containing the remaining $5$
vertices. Then, we partition $N_{\ell}$ into two sets of size $2$,
$N_{\ell}^{v_{i}}$ and $N_{\ell}^{C}$ if $\ell$ represents $v_{i}$, and
$N_{\ell}^{\overline{v}_{i}}$ and $N_{\ell}^{C}$ if $\ell$ represents
$\overline{v}_{i}$.

####  3.1.3 Ordering and arcs linking the gadgets and the base tournaments

We now describe the orientation of the arcs linking the gadgets with the base
tournament, as well as the way the gadgets are introduced in the ordering
$\prec^{*}$.

First, for every $x\in\mathcal{V}\cup\mathcal{L}$, we set

$x\prec^{*}N_{x}\prec^{*}\ell_{x}\prec^{*}Y_{x}\prec^{*}M_{x}\setminus\\{\ell_{x}\\}$

and $\prec^{*}$ restricted to $G_{x}$ is the topological ordering of $G_{x}$.
This defines the ordering. All arcs linking $G_{x}$ and $B_{x}$ are forward-
arcs with respect to $\prec^{*}$, except the arcs between $Y_{x}$ and $x$ that
are all oriented from $Y_{x}$ to $x$. See Figure 5 for the case when
$x\in\mathcal{V}$ and Figure 6 for the case when $x\in\mathcal{L}$.

####  3.1.4 Arcs linking the gadgets together

We now describe the orientation of the arcs between a gadget and another
gadget. For $v\in\mathcal{V}$ and $\ell\in\mathcal{L}$, we say that $\ell$ is
an _occurrence_ of $v$ ($\overline{v}$) if $v\in\\{v_{i},\overline{v}_{i}\\}$
for some $i\in n$ and $\ell$ is associated with an occurrence of $x_{i}$
$(\overline{x}_{i})$ in the literals.

  1. 1.

For every $v\in\mathcal{V}$ and for each occurrence $\ell\in\mathcal{L}$ of
$\overline{v}$, if $\ell$ is the $i^{th}$ occurrence of $\overline{v}$, then
we put a back-arc matching from $N_{\ell}^{\overline{v}}$ to $N_{v}^{i}$ and
from $Y_{\ell}$ to $Y_{v}^{i}$. See Figure 7.

  2. 2.

For every $v\in\\{v_{1},\dots,v_{n}\\}$, we put a back-arc matching from
$N_{\overline{v}}^{v}$ to $N^{\overline{v}}_{v}$, and from
$Y_{\overline{v}}^{v}$ to $Y^{\overline{v}}_{v}$.

  3. 3.

For each (ordered) clause $(a\vee b\vee c)$, setting $N_{a}=a_{1}\rightarrow
a_{2}$, $N_{b}=b_{1}\rightarrow b_{2}$, $N_{c}=c_{1}\rightarrow c_{2}$, we add
the following arcs: $c_{2}\rightarrow a_{1}$, $b_{1}\rightarrow a_{2}$ and
$c_{1}\rightarrow a_{1}$. See Figure 8.

  4. 4.

All other arcs are forward-arcs.

This ends the construction of the ordered tournament
$(\mathcal{T}_{\mathcal{I}},\prec^{*})$. Figure 3 illustrates the links
between the gadgets associated with vertices in $\mathcal{V}\cup\mathcal{L}$.

For every $v\in\mathcal{V}$ associated with a variable $x$, we ask that
$N_{v}$ and $Y_{v}$ have as many pieces of size two and five, respectively, as
the number of occurrences of $\overline{x}$ as a literal plus one. This choice
is made to ensure that no two gadgets $G_{u},G_{u^{\prime}}$ with
$u,u^{\prime}\in\mathcal{V}\cup\mathcal{L}\setminus\\{v\\}$ have back-arc
matchings with common endpoints in $G_{v}$. For otherwise, it could be the
case that every backedge graph of $T$ would contain a cycle. Here, the
backedge graph induced by the union of all gadgets $G_{v}$ when
$v\in\mathcal{V}\cup\mathcal{L}$ with respect to $\prec^{*}$ is a matching.

Variables:$G_{v_{1}}$$G_{\overline{v}_{1}}$$x_{1}$$G_{v_{2}}$$G_{\overline{v}_{2}}$$x_{2}$$G_{v_{3}}$$G_{\overline{v}_{3}}$$x_{3}$Clauses:$N^{\overline{v}_{1}}_{\ell_{1}}$$\ell_{1}=x_{1}$$N^{v_{2}}_{\ell_{2}}$$\ell_{2}=\overline{x}_{2}$$N^{\overline{v}_{3}}_{\ell_{3}}$$\ell_{3}=x_{3}$$N^{v_{1}}_{\ell_{4}}$$\ell_{4}=\overline{x}_{1}$$N^{v_{2}}_{\ell_{5}}$$\ell_{5}=\overline{x}_{2}$$N^{\overline{v}_{3}}_{\ell_{6}}$$\ell_{6}=x_{3}$$N^{1}_{\overline{v}_{1}}$$N^{1}_{v_{2}}$$N^{1}_{\overline{v}_{3}}$$N^{1}_{v_{1}}$$N^{2}_{v_{2}}$$N^{2}_{\overline{v}_{3}}$$C_{1}$$C_{2}$
Figure 3:  Informal description of the back-arc matchings linking the gadgets
of the literals of two clauses, together with the gadgets of the variables
these literals represent. The edge labelled $N^{1}_{\overline{v}_{1}}$
represents the back-arc matching from $N^{\overline{v}_{1}}_{\ell_{1}}$ to
$G_{\overline{v}_{1}}$, where $\ell_{1}$ is the first occurrence of $x_{1}$.

###  3.2 Building a satisfying assignment from a forest-ordering

Let $\mathcal{I}$ be an instance of $3$-SAT (as described at the beginning of
Section 3.1) and $(T_{\mathcal{I}},\prec^{*})$ the tournament described in
Section 3.1. The goal of this subsection is to prove that if $T_{\mathcal{I}}$
has a forest-ordering, then $\mathcal{I}$ is a satisfiable instance.

Given forest-ordering $\prec$ of $T_{\mathcal{I}}$, we need to deduce from
$\prec$ a truth assignment of the variables of $\mathcal{I}$ that satisfies
$\mathcal{I}$. This will be done using the position of each vertex
$x\in\mathcal{V}\cup\mathcal{L}$ with respect to $\ell_{x}$ as we explain now.

We say that $\prec$ satisfies ${\sf L}_{\prec}(v_{i})$ if
$v_{i}\prec\ell_{v_{i}}$, and $\prec$ satisfies ${\sf R}_{\prec}(v_{i})$ if
$\ell_{v_{i}}\prec v_{i}$. ${\sf L}_{\prec}(v_{i})$ is used to assign value
True to the variable $x_{i}$, and ${\sf R}_{\prec}(v_{i})$ to assign value
False.

In order to get a coherent assignment for $\mathcal{I}$ and to be sure that
each clause is satisfied, we need to prove the following for every forest-
ordering $\prec$ of $T_{\mathcal{I}}$:

  * •

For every $i\in[n]$, $\prec$ satisfies either ${\sf L}(v_{i})$ and ${\sf
R}(\overline{v_{i}})$ or ${\sf R}(v_{i})$ and ${\sf L}(\overline{v}_{i})$.

  * •

For every $i\in[n]$, $\prec$ satisfies ${\sf L}(v_{i})$ if and only if $\prec$
satisfies ${\sf L}(\ell)$ for any literal $\ell$ that is an occurrence of
$x_{i}$.

  * •

For every $i\in[n]$, $\prec$ satisfies ${\sf L}(\overline{v}_{i})$ if and only
if $\prec$ satisfies ${\sf L}(\ell)$ for any literal $\ell$ that is an
occurrence of $\overline{x}_{i}$.

  * •

Each clause is satisfied. With our notation, this is equivalent with proving
that for each (ordered) clause $(x\vee y\vee z)$, the forest-ordering $\prec$
assigns ${\sf L}_{\prec}(x)$ or ${\sf L}_{\prec}(y)$ or ${\sf L}_{\prec}(z)$.

The three first items are proved in Lemma 3.3, and the last one in Lemma 3.4.

The next lemma is used to ensure that all the back-arcs of the back-arc
matchings linking pairs of gadgets appear in the backedge graph of every
forest-ordering.

######  Lemma 3.1.

In every forest-ordering $\prec$ of $T_{\mathcal{I}}$, for every
$x,z\in\mathcal{V}\cup\mathcal{L}$, such that $x\prec z$, we have $N_{x}\prec
N_{z}$ and $Y_{x}\prec Y_{z}$

###### Proof.

Let $\prec$ be a forest-ordering of $T_{\mathcal{I}}$ and let
$x,z\in\mathcal{V}\cup\mathcal{L}$ such that $x\prec z$.

Let $a\in N_{x}$ and $b\in N_{z}$, and assume for contradiction that $b\prec
a$. By construction of $T_{\mathcal{I}}]$ we have $a\Rightarrow
M_{x}\Rightarrow b$, and thus, by Lemma 2.1, each vertex of $M_{x}$ is
adjacent to $a$ or $b$ in $T^{\prec}_{\mathcal{I}}$. This implies that, in
$T^{\prec}$, $a$ or $b$ has at least two neighbours in $M_{x}$, and since
$T^{\prec}_{\mathcal{I}}[M_{x}]$ is a tree, we get that
$T^{\prec}_{\mathcal{I}}[M_{x}\cup\\{a,b\\}]$ has a cycle, contradiction.

Now, let $a\in Y_{x}$ and $b\in Y_{z}$, and assume for contradiction that
$b\prec a$. We have $a\Rightarrow M_{x}\setminus\\{\ell_{x}\\}\Rightarrow b$
and since $b\prec a$, by Lemma 2.1, each vertex of
$M_{x}\setminus\\{\ell_{x}\\}$ is adjacent to $a$ or $b$ in
$T^{\prec}_{\mathcal{I}}$. Hence, in $T^{\prec}_{\mathcal{I}}$, one of $a$ or
$b$ has two neighbours in $M_{x}$, and since $T^{\prec}_{\mathcal{I}}[M_{x}]$
is a tree, $T^{\prec}_{\mathcal{I}}[M_{x}\cup\\{a,b\\}]$ has a cycle, a
contradiction. ∎

Recall that for every $v\in\mathcal{V}\cup\mathcal{L}$, $B_{v}=\\{v\\}\cup
M_{v}$

######  Lemma 3.2.

Let $\prec$ be a forest-ordering of $T_{\mathcal{I}}$. For every
$v\in\mathcal{V}\cup\mathcal{L}$, if $\prec$ satisfies $R_{\prec}(v)$, then
$T_{\mathcal{I}}^{\prec}[B_{v}\cup N_{v}]$ is a tree.

###### Proof.

Let $v\in\mathcal{V}\cup\mathcal{L}$ and assume $\prec$ satisfies
$R_{\prec}(v)$, i.e. $\ell_{v}\prec v$. Since $v\rightarrow\ell_{v}$, we have
that $v\ell_{v}\in E(T_{\mathcal{I}}^{\prec})$. Moreover,
$T^{\prec}_{\mathcal{I}}[M_{v}]$ is a tree by Lemma 2.2. Hence
$T^{\prec}_{\mathcal{I}}[\\{v\\}\cup M_{v}]$ is a tree. Let $r\in V(N_{v})$.
By construction of $T_{\mathcal{I}}$, $v\Rightarrow N_{v}\Rightarrow\ell_{v}$,
so in particular $v\rightarrow r\rightarrow\ell_{v}$. If $r\prec v$, then
$vr\in E(T^{\prec}_{\mathcal{I}})$. If $v\prec r$, then $\ell_{v}\prec r$ and
thus $\ell_{v}r\in E(T^{\prec}_{\mathcal{I}})$. This implies the lemma. ∎

As announced, next lemma implies that the truth assignment of $\mathcal{I}$
deduced from a forest-ordering $\prec$ is coherent.

######  Lemma 3.3.

Let $\prec$ be a forest-ordering of $T_{\mathcal{I}}$, let $v\in\mathcal{V}$
and let $x\in\mathcal{V}\cup\mathcal{L}\setminus\\{v\\}$. If $x=\overline{v}$,
or $x\in\mathcal{L}$ is an occurrence of $\overline{v}$, then, one of the
following is satisfied:

  * •

$L_{\prec}(v)$ and $R_{\prec}(x)$, or

  * •

$R_{\prec}(v)$ and $L_{\prec}(x)$.

###### Proof.

Assume $x$ is either $\overline{v}$ or is the $i^{th}$ occurrence of
$\overline{v}$ for some $i\in[3k]$.

Assume for contradiction that $R_{\prec}(v)$ and $R_{\prec}(x)$. Assume first
that $x=\overline{v}$. By Lemma 3.2, both $T^{\prec}_{\mathcal{I}}[B_{v}\cup
N_{v}]$ and $T^{\prec}_{\mathcal{I}}[B_{\overline{v}}\cup N_{\overline{v}}]$
are trees, and by Lemma 3.1, there is a perfect matching between
$N_{v}^{\overline{v}}$ and $N_{\overline{v}}^{v}$ in
$T^{\prec}_{\mathcal{I}}$, i.e. two edges are linking
$T^{\prec}_{\mathcal{I}}[B_{v}\cup N_{v}]$ and
$T^{\prec}_{\mathcal{I}}[B_{\overline{v}}\cup N_{\overline{v}}]$ in
$T^{\prec}_{\mathcal{I}}$, and thus $T^{\prec}_{\mathcal{I}}$ has a cycle, a
contradiction. If $x=\ell$ is the $i^{th}$ occurrence of $\overline{v}$, then
the same reasoning holds by considering $N_{v}^{i}$ instead of
$N_{\overline{v}}^{v}$ and $N_{\ell}^{v}$ instead of $N_{\overline{v}}^{v}$.

Assume now that $L_{\prec}(v)$ and $L_{\prec}(x)$. Assume first that
$x=\overline{v}$, so we have both $v\prec\ell_{v}$ and
$\overline{v}\prec\ell_{\overline{v}}$.

######  Claim 3.3.1.

Let $z\in\\{v,\overline{v}\\}$. For every $a\in Y_{z}$, either $av\in
E(T^{\prec})$, or $a\ell_{v}\in E(T^{\prec})$

Proof. Recall that, by construction of $T_{\mathcal{I}}$, we have
$Y_{z}\Rightarrow z\rightarrow\ell_{z}\Rightarrow Y_{z}$ (see Figure 5). Let
$a\in Y_{z}$. Since $z\prec\ell_{z}$ and $a\rightarrow
z\rightarrow\ell_{z}\rightarrow a$, if $z\prec a$, then $za\in E(T^{\prec})$,
and if $a\prec z$, then $a\prec\ell_{z}$ and $a\ell_{z}\in E(T^{\prec})$.
$\lozenge$

Recall that $Y_{v}^{\overline{v}}$ and $Y_{\overline{v}}^{v}$ both have $5$
vertices. Now consider $H$ the subgraph of $T^{\prec}$ induced by
$\\{v,\ell_{v},\overline{v},\ell_{\overline{v}}\\}\cup
Y_{v}^{\overline{v}}\cup Y_{\overline{v}}^{v}$. By Lemma 3.1, there is a
perfect matching between $Y_{v}^{\overline{v}}$ and $Y_{\overline{v}}^{v}$ in
$T^{\prec}$ and thus in $H$. Now, together with the claim, we get that $H$ has
at least $10+5=15$ edges, while it has only $14$ vertices. Hence $H$ has a
cycle, a contradiction. This proved the case where $x=\overline{v}$, in the
case where $x=\ell$ is the $i^{th}$ occurrence of $\overline{v}$, the same
reasoning holds by considering $Y_{v}^{i}$ instead of $Y_{\overline{v}}^{v}$
and $Y_{\ell}^{v}$ instead of $Y_{\overline{v}}^{v}$. ∎

The last Lemma implies that all clauses are satified by the truth assignment
of $\mathcal{I}$ deduced from a forest-ordering of $T_{\mathcal{I}}$.

######  Lemma 3.4.

Let $\prec$ be a forest-ordering of $T_{\mathcal{I}}$ and let
$v\in\mathcal{V}$ and let $(a\vee b\vee c)$ be an (ordered) clause. Then at
least one of $L(x),L(y),L(z)$ holds.

###### Proof.

Set $N_{a}=a_{1}\rightarrow a_{2}$, $N_{b}=b_{1}\rightarrow b_{2}$,
$N_{c}=c_{1}\rightarrow c_{2}$. Recall that we have: $b_{1}\rightarrow a_{2}$,
$c_{1}\rightarrow b_{2}$ and $c_{2}\rightarrow a_{1}$ (See Figure 8). By Lemma
3.1, edges $b_{1}a_{2},c_{1}b_{2}$ and $c_{2}a_{1}$ are in
$E(T^{\prec}_{\mathcal{I}})$. Moreover, by Lemma 3.2,
$T^{\prec}_{\mathcal{I}}[B_{a}\cup N_{a}]$, $T^{\prec}_{\mathcal{I}}[B_{b}\cup
N_{b}]$ and $T^{\prec}_{\mathcal{I}}[B_{c}\cup N_{c}]$ are trees. This,
together with edges $b_{1}a_{2},c_{1}b_{2}$ and $c_{2}a_{1}$, implies that
$T^{\prec}$ has a cycle, contradiction. ∎

###  3.3 Building a forest-ordering from a satisfying assignment

For an integer $k\geq 1$, we say that an undirected graph $G$ is _$k$
-degenerate_ if every subgraph of $G$ has a vertex of degree at most $k$.
Observe that a graph is a forest if and only if it is $1$-degenerate graph is
a forest.

This section is dedicated to the proof that, given a satisfiable instance
$\mathcal{I}$ of $3$-SAT, $T_{\mathcal{I}}$ admits a forest-ordering. Let
$\nu$ be a variable assignment satisfying $\mathcal{I}$. The ordered
tournament $(T_{\mathcal{I}},\prec^{*})$ starts with every
$x\in\mathcal{V}\cup\mathcal{L}$ assigned ${\sf L}(x)$, and we show how to use
$\nu$ to decide which $x\in\mathcal{V}\cup\mathcal{L}$ should be assigned
${\sf R}(x)$ to build a forest-ordering $\prec$ for $T_{\mathcal{I}}$ starting
from $\prec^{*}$, as indicated in Section 3.1.

We set

$\mathcal{V}_{True}=\\{v_{i}\in\mathcal{V}\mid\nu(x_{i})=True\\}\cup\\{\overline{v}_{i}\in\mathcal{V}\mid\nu(x_{i})=False\\}$

and $\mathcal{V}_{False}=\mathcal{V}\setminus\mathcal{V}_{True}$. We define
$\mathcal{L}_{True}$ and $\mathcal{L}_{False}$ similarly.

Then we define the order $\prec$ of $T$ from $\prec^{*}$ by moving each vertex
$x\in\mathcal{V}_{False}\cup\mathcal{L}_{False}$ right after $Y_{x}$. Figure 9
describes the ordering $\prec$ restricted to $\\{x\\}\sqcup G_{x}\sqcup
M_{x}\\}$ when $x\in\mathcal{V}_{False}\cup\mathcal{L}_{False}$. When
$x\in\mathcal{V}_{True}\cup\mathcal{L}_{True}$, the ordering of
$\\{\\{x\\}\sqcup G_{x}\sqcup M_{x}\\}$ is the same as $\prec^{*}$ and is
shown in Figure 5.

Hence, if $x\in\mathcal{V}_{True}\cup\mathcal{L}_{True}$, then the only edges
of $T^{\prec}_{\mathcal{I}}[\\{x\\}\sqcup G_{x}\sqcup M_{x}]$ are the edges
linking each vertex of $Y_{x}$ with $x$ (that is back-arcs in Figure 5) and if
$x\in\mathcal{V}_{False}\cup\mathcal{L}_{False}$, then the only edges of
$T^{\prec}[\\{x\\}\sqcup G_{x}\sqcup M_{x}]$ are the edges linking each vertex
of $N_{x}$ with $x$ (that is back-arcs in Figure 9).

We are going to prove that $\prec$ is a forest-ordering of $T_{\mathcal{I}}$
i.e., that $T_{\mathcal{I}}^{\prec}$ is a forest. More precisely, we are going
to prove that $T^{\prec}_{\mathcal{I}}$ is $1$-degenerate by iteratively
peeling off vertices of degree at most $1$ in $T^{\prec}_{\mathcal{I}}$.

For every $x\in\mathcal{V}\cup\mathcal{L}$, $T^{\prec}_{\mathcal{I}}[M_{x}]$
is a tree and vertices in $M_{x}\setminus\\{\ell_{x}\\}$ have no neighbour in
$T^{\prec}$ outside $M_{x}$. We can thus peel off every vertex of
$M_{x}\setminus\\{\ell_{x}\\}$.

Let $x\in\mathcal{V}\cup\mathcal{L}$ and consider $\ell_{x}$. If
$x\in\mathcal{V}_{True}\cup\mathcal{L}_{True}$, then $\ell_{x}$ has degree $0$
(see Figure 5), and if $x\in\mathcal{V}_{False}\cup\mathcal{L}_{False}$, then
the only remaining neighbour of $\ell_{x}$ in $T^{\prec}$ is $x$ (see Figure
9). We can thus also peel off $\ell_{x}$.

Let $T_{1}$ be the tournament obtained from $T$ after removing the union of
all $M_{x}$ for $x\in\mathcal{V}\cup\mathcal{L}$. In $T^{\prec}_{1}$ the
vertices in the following sets have degree one:

  * •

$N_{x}$ when $x\in\mathcal{V}_{True}\cup\mathcal{L}_{True}$

  * •

$Y_{x}$ when $x\in\mathcal{V}_{False}\cup\mathcal{L}_{False}$

Indeed, when $x\in\mathcal{V}_{True}\cup\mathcal{L}_{True}$, vertices in
$N_{x}$ have degree $0$ in $T^{\prec}[B_{x}\cup M_{x}]$ (see Figures 5 and 6),
and thus their only neighbours are through the back-arc matching linking the
gadgets. Similarly, when $x\in\mathcal{V}_{False}\cup\mathcal{L}_{False}$,
vertices in $Y_{x}$ have degree $0$ in $T^{\prec}[B_{x}\cup M_{x}]$ (see
Figures 9 and 10), and thus their only neighbours are through the back-arc
matching linking the gadgets.

For $v\in\mathcal{V}\cup\mathcal{L}$, the _$Y$ -gadget_ of $v$ is the set
$Y_{v}$. Let $T_{2}$ be the tournament obtained after removing the above sets
of vertices. In $T^{\prec}_{2}$ the vertices in the following sets have degree
one:

  * •

$Y_{x}$ when $x\in\mathcal{V}_{True}\cup\mathcal{L}_{True}$ (their only
neighbours is $x$)

  * •

$N_{v}$ for $v\in\mathcal{V}_{False}$.

  * •

$N_{\ell}^{var(\ell)}$ for $\ell\in\mathcal{L}_{False}$, where $var(\ell)$ is
the variable corresponding to $\ell$.

The first item holds because the neighbours of vertices in $Y_{x}$ are $x$ and
the end-vertices of the back-arc matchings linking them with the $Y$-gadgets
associated with (some of the) vertices in
$\mathcal{V}_{False}\cup\mathcal{L}_{False}$, which already have been removed.
The two other items hold for the similar reasons.

After deleting all these sets, the vertices in
$\mathcal{V}\cup\mathcal{L}_{True}$ have degree $1$, we can thus remove them.
We call $T_{3}$ the tournament induced by the remaining vertices.

$T_{3}$ has the following vertices: $\mathcal{L}_{False}$ and for each
$\ell\in\mathcal{L}_{False}$, $N_{\ell}^{C_{\ell}}$ where $C_{\ell}$ is the
clause containing $\ell$. Let $C=(x,y,z)$ be a clause. At least one of $x,y,z$
is in $\mathcal{L}_{True}$, say $z$. If both $x$ and $y$ are False, we have
$T^{\prec}_{3}[\\{x,y\\}\cup N_{x}^{C}\cup N_{y}^{C}]$ is a path (see Figure
4) and a connected component of $T^{\prec}_{3}$ and thus we are done. If $x$
or $y$ are True, the same reasoning holds.

$x_{1}$$x_{2}$$N^{C}_{x}$$x$$y_{1}$$y_{2}$$N^{C}_{y}$$y$$z$$z_{1}$$z_{2}$$N^{C}_{z}$
Figure 4: Back-arcs associated with ordering $\prec$ defined in Section 3.3
with an ordered clause $C=(x,y,z)$ in $T_{3}$, where
$x,y\in\mathcal{L}_{False}$ and $z\in\mathcal{L}_{True}$.

##  4 Conclusion

We think the $\mathcal{C}$-FAS Problem is interesting, and quite natural, in
particular because of its links with the dichromatic number and the clique
number of tournaments. It is also a way to define classes of tournament (given
an undirected class of graphs $\mathcal{C}$, a $\mathcal{C}$-tournaments is a
tournament $T$ that admits $\mathcal{C}$-FAS) that has been often used
recently (see for example Section 4 in [26] where many such classes are looked
at).

As explained in the introduction, when $\mathcal{C}_{k}$ is the class of
graphs with clique number at most $k$, the $\mathcal{C}_{k}$-FAS problem has
been recently proved to be $NP$-complete when $k\geq 4$, is easily seen to be
polynomial when $k\leq 2$, but its complexity is open when $k=3$.

######  Problem 4.1 ([6]).

Given a tournament $T$, what is the complexity of deciding if $T$ has a
triangle-free FAS?

On the same flavour, Aboulker et al.[2] proved that an approximation version
of the above problem is polynomial. More precisely, they prove that there is a
constant $c$ such that one can decide in poly-time if, given a tournament $T$,
$\operatorname{\overrightarrow{\omega}}(T)\geq 3$, or
$\operatorname{\overrightarrow{\omega}}(T)\leq c$. It is thus natural to
conjecture the following.

######  Conjecture 4.2.

There a function $f$ such that for every integer $k$, there is a polynomial-
time algorithm that, given a tournament $T$ decide if
$\operatorname{\overrightarrow{\omega}}(T)\geq k$, or
$\operatorname{\overrightarrow{\omega}}(T)\leq f(k)$

In [1], it is proved that a tournament has a forest-ordering if and only if it
has a tree-ordering. (For the curious reader, the proof is easy: simply start
from a forest-ordering, runs through vertices from left to right, and when two
consecutive vertices $x\prec y$ are in distinct connected component, just
switch the ordering of $x$ and $y$). Together with Theorem 1.1, it implies the
following:

######  Theorem 4.3.

The $\mathcal{C}$-FAS problem is NP-complete when $\mathcal{C}$ is the set of
all trees.

It is natural to ask for which class of graphs $\mathcal{C}$, the
$\mathcal{C}$-FAS Problem is in $P$. Two natural candidates of such
$\mathcal{C}$ are paths and matching. More formally:

######  Problem 4.4.

What is the complexity of the $\mathcal{C}$-FAS Problem when $\mathcal{C}$ is
the set of all paths? when $\mathcal{C}$ is the set of graphs with maximum
degree $1$?

##  5 Figures

$v$$N_{v}$$N^{\overline{x}}_{v}$$N^{1}_{v}$$\cdots$$N^{{\sf
occ}(\overline{v})}_{v}$$\ell_{v}$$Y_{v}$$Y^{\overline{v}}_{v}$$Y^{1}_{v}$$\cdots$$Y^{{\sf
occ}(\overline{v})}_{v}$$M_{v}\setminus\ell_{v}$ Figure 5: The figure
represent a vertex $v\in\mathcal{V}$, $M_{v}$ and $G_{v}=N_{v}\sqcup Y_{v}$
ordered as in $\prec^{*}$. Forward-arcs are note drawn. The tournament induced
by $M_{x}$ is the same as the one depicted in Figure 1, and thus the back-arcs
in $T[M_{v}]$ induce a tree. A thick arc represent all arcs in that
orientation.
$z$$N_{z}$$N^{\overline{v}_{i}}_{z}$$N^{C}_{z}$$\ell_{z}$$Y_{z}$$M_{z}\setminus\ell_{z}$
Figure 6: The figure represent a vertex $z\in\mathcal{L}$, $M_{z}$ and
$G_{z}=N_{z}\sqcup Y_{z}$ ordered as in $\prec^{*}$. Forward-arcs are not
drawn. The tournament induced by $M_{z}$ is the same as the one depicted in
Figure 1, and thus the back-arcs in $T[M_{z}]$ induce a tree. A thick arc
represent all arcs in that orientation.
$v$$N^{\overline{v}}_{v}$$\cdots$$\cdots$$\overline{v}$$N^{v}_{\overline{v}}$$\cdots$$\cdots$$N^{j}_{\overline{v}}$$\cdots$$\cdots$$\ell$$N^{\overline{v}}_{\ell}$$N^{C}_{\ell}$$\cdots$
Figure 7: Back-arc matchings from $N^{v}_{\overline{v}}$ to
$N^{\overline{v}}_{v}$, where $v,\overline{v}\in\mathcal{V}$, and from
$N^{\overline{v}}_{\ell}$ and $N^{j}_{\overline{v}}$, where $\ell$ is the
$j^{th}$ occurrence of $\overline{x}$ and $x$ is the variable associated with
the pair $v,\overline{v}$. Vertices are ordered as in $\prec^{*}$. Non-drawn
arcs are all forward-arcs.
$a$$a_{1}$$a_{2}$$N^{C}_{a}$$b$$b_{1}$$b_{2}$$N^{C}_{b}$$c$$c_{1}$$c_{2}$$N^{C}_{c}$
Figure 8: Back-arc matchings associated with an ordered clause $C=(a\vee b\vee
c)$. Non-drawn arcs are all forward-arcs.
$N_{x}$$N^{\overline{x}}_{x}$$N^{1}_{x}$$\cdots$$N^{{\sf
occ}(\overline{x})}_{x}$$\ell_{x}$$Y_{x}$$Y^{\overline{x}}_{x}$$Y^{1}_{x}$$\cdots$$Y^{{\sf
occ}(\overline{x})}_{x}$$x$$M_{x}\setminus\ell_{x}$ Figure 9: The figure
represents a vertex $v\in\mathcal{V}$, $M_{v}$ and $G_{v}=N_{v}\sqcup Y_{v}$
ordered as the ordering $\prec$ defined in Section 3.3. Forward-arcs are not
drawn. A thick arc represent all arcs in that orientation.
$N_{z}$$N^{\overline{v}_{i}}_{z}$$N^{C}_{z}$$\ell_{z}$$Y_{z}$$z$$M_{z}\setminus\ell_{z}$
Figure 10: The figure represents a vertex $z\in\mathcal{V}$, $M_{z}$ and
$G_{z}=N_{z}\sqcup Y_{z}$ ordered as the ordering $\prec$ defined in Section
3.3. Forward-arcs are not drawn. A thick arc represent all arcs in that
orientation.

##  6 Code for Lemma 2.2

The following code is used to verify that the tournament shown in Figure 1
admits an unique tree-ordering.

from itertools import permutations

# is_forest(T,P) # Input: # - a tournament, given as a 8x8 matrix ‘T‘ such
that # T[u][v] iff there is an arc u -> v # - an ordering of V(T), given as a
permutation ‘P‘ # of [0,7] such that u < v iff P[u] < P[v] # Output: # - a
boolean: is ‘T^<‘ a forest? def is_forest(T, P): visited = set()

# Recursive depth-first search looking for a cycle # in T^< starting from rot
‘u‘, and assuming we # just visited vertex ‘parent‘ (initially, u itself). def
dfs(u, parent): if u in visited: return True visited.add(u) return any(T[u][v]
== (P[v] <= P[u]) and dfs(v, u) for v in range(8) if v != parent)

return all(x in visited or not dfs(x, x) for x in range(8))

# The tournament in Figure 1. T = [ [ 0, 1, 1, 0, 0, 0, 1, 0], [ 0, 0, 1, 1,
1, 1, 0, 0], [ 0, 0, 0, 1, 1, 0, 1, 1], [ 1, 0, 0, 0, 1, 1, 1, 1], [ 1, 0, 0,
0, 0, 1, 1, 1], [ 1, 0, 1, 0, 0, 0, 1, 1], [ 0, 1, 0, 0, 0, 0, 0, 1], [ 1, 1,
0, 0, 0, 0, 0, 0] ]

# We iterate over all permutations of [0,7], and check # that the only
permutation such that is_forest(T, P) # returns True is the identity. for P in
permutations(range(8)): assert is_forest(T, P) == (P == (0,1,2,3,4,5,6,7))

## References

  * [1] Pierre Aboulker, Guillaume Aubian, Pierre Charbit, and Raul Lopes.  Clique number of tournaments, 2023.
  * [2] Pierre Aboulker, Guillaume Aubian, Pierre Charbit, and Stéphan Thomassé.  Personnal communication.
  * [3] Faisal N. Abu-Khzam.  A kernelization algorithm for d-hitting set.  Journal of Computer and System Sciences, 76(7):524–531, 2010.
  * [4] Nir Ailon, Moses Charikar, and Alantha Newman.  Aggregating inconsistent information: Ranking and clustering.  J. ACM, 55(5), nov 2008.
  * [5] Noga Alon, János Pach, and József Solymosi.  Ramsey-type theorems with forbidden subgraphs.  Combinatorica, 21(2):155–170, Apr 2001.
  * [6] Guillaume Aubian.  Computing the clique number of tournaments, 2024.
  * [7] Jørgen Bang-Jensen and Gregory Gutin.  Digraphs: Theory, Algorithms and Applications.  Springer, London, 2007.
  * [8] Eli Berger, Krzysztof Choromanski, Maria Chudnovsky, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour, and Stéphan Thomassé.  Tournaments and colouring.  Journal of Combinatorial Theory, Series B, 103:1–20, 01 2013.
  * [9] Eli Berger, Krzysztof Choromanski, Maria Chudnovsky, and Shira Zerbib.  Tournaments and the strong erdős–hajnal property.  European Journal of Combinatorics, 100:103440, 2022.
  * [10] Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, and Stéphan Thomassé.  Kernels for feedback arc set in tournaments.  Journal of Computer and System Sciences, 77(6):1071–1078, 2011\.
  * [11] Drago Bokal, Gašper Fijavz, Martin Juvan, P. Kayll, and Bojan Mohar.  The circular chromatic number of a digraph.  Journal of Graph Theory, 46:227 – 240, 07 2004.
  * [12] Pierre Charbit, Stéphan Thomassé, and Anders Yeo.  The minimum feedback arc set problem is np-hard for tournaments.  Comb. Probab. Comput., 16(1):1–4, 2007.
  * [13] Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl.  Pure pairs. x. tournaments and the strong erdős-hajnal property.  European Journal of Combinatorics, 115:103786, 2024.
  * [14] William W Cohen, Robert E Schapire, and Yoram Singer.  Learning to order things.  In M. Jordan, M. Kearns, and S. Solla, editors, Proc. of the 10th Advances in Neural Information Processing Systems (NIPS), volume 10. MIT Press, 1997.
  * [15] Michael Dom, Daniel Lokshtanov, and Saket Saurabh.  Incompressibility through colors and ids.  In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris Nikoletseas, and Wolfgang Thomas, editors, Proc. of the 36th International Colloquium on Automata, Languages and Programming (ICALP), pages 378–389, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.
  * [16] Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar.  Rank aggregation revisited.  2002\.  Technical report.
  * [17] M. El-Zahar and P. ErdÅ‘s.  On the existence of two non-neighboring subgraphs in a graph.  Combinatorica, 5(4):295–300, Dec 1985.
  * [18] Paul Erdős and András Hajnal.  On spanned subgraphs of graphs.  Beitrage zur Graphentheorie und deren Anwendungen, Kolloq. Oberhof (DDR), 01 1977.
  * [19] Fedor Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh.  Fast local search algorithm for weighted feedback arc set in tournaments.  Proceedings of the AAAI Conference on Artificial Intelligence, 24(1):65–70, Jul. 2010.
  * [20] Ararat Harutyunyan, Tien-Nam Le, Stéphan Thomassé, and Hehui Wu.  Coloring tournaments: From local to global.  J. Comb. Theory, Ser. B, 138:166–171, 2019.
  * [21] J. Kemeny.  Mathematics without numbers.  Daedalus, 88:571–590, 1959.
  * [22] J. Kemeny and J. Snell.  Mathematical Models in the Social Sciences.  Blaisdell, 1962.
  * [23] C. Kenyon-Mathieu and W. Schudy.  How to rank with few errors.  In ACM Symposium on Theory of Computing (STOC), pages 95–103, 2007\.
  * [24] Felix Klingelhoefer and Alantha Newman.  Coloring tournaments with few colors: Algorithms and complexity.  ArXiv, abs/2305.02922, 2023.
  * [25] Felix Klingelhöfer and Alantha Newman.  Bounding the chromatic number of dense digraphs by arc neighborhoods.  CoRR, abs/2307.04446, 2023.
  * [26] Tung Nguyen, Alex Scott, and Paul Seymour.  Some results and problems on tournament structure, 2023.
  * [27] Tung Nguyen, Alex Scott, and Paul Seymour.  Induced subgraph density. vi. bounded vc-dimension, 2024.
  * [28] Tung Nguyen, Alex Scott, and Paul Seymour.  On a problem of el-zahar and erdős.  Journal of Combinatorial Theory, Series B, 165:211–222, 2024.
  * [29] V. Raman and S. Saurabh.  Parameterized algorithms for feedback set problems and their duals in tournaments.  Theoretical Computer Science, 351(3):446–458, 2006.
  * [30] Alex Scott and Paul Seymour.  A survey of $\chi$-boundedness.  Journal of Graph Theory, 95, 08 2020.
  * [31] S. Seshu and M. B. Reed.  Linear Graphs and Electrical Networks.  Addison-Wesley, 1961.
  * [32] P. Slater.  Inconsistencies in a schedule of paired comparisons.  Biometrika, 48:303–312, 1961.
  * [33] E. Speckenmeyer.  On feedback problems in digraphs.  In Proc. of the 5th Workshop on Graph-Theoretic Concepts in Computer Science (WG), volume 411 of Lecture Notes in Computer Science, pages 218–231. Springer, 1989.
  * [34] Soukaina Zayat.  Forests and the strong erdős-hajnal property.  Discrete Mathematics, 347(5):113920, 2024.
  * [35] Soukaina Zayat and Salman Ghazal.  Tournaments and the erdös-hajnal conjecture, 2022.


# Driven translocation of a flexible polymer through an interacting conical
pore

Rajneesh Kumar<EMAIL_ADDRESS>Present address: Theoretical Science
Unit, Jawaharlal Nehru Center for Advanced Scientific Research, Jakkur,
Banglore –560064 India. Abhishek Chaudhuri<EMAIL_ADDRESS>Rajeev
Kapri<EMAIL_ADDRESS>Indian Institute of Science Education and
Research Mohali, Knowledge City, Sector 81, S. A. S. Nagar – 140 306, Punjab
India.

###### Abstract

We study the driven translocation of a flexible polymer through an interacting
conical pore using Langevin dynamics simulations. We find that, for a fixed
value of externally applied force and pore polymer interaction strength, the
mean residence time of monomers inside the pore shows non-monotonic variations
with pore apex angle $\alpha$. We explain this behavior using a free energy
argument by explicitly accounting for pore-polymer interactions and external
drive. Our theoretical observations are corroborated by the simulation results
of the mean translocation times as the pore-polymer interactions and external
driving force are varied.

###### pacs:

87.15.ap, 82.35.Lr, 82.35.Pq

Polymer translocation is a complex ubiquitous phenomena found in many
biological processes like the passage of mRNA through nuclear pore complexes,
protein translocation across biological membranes through a narrow channel,
injection of DNA from a virus head into a host cell and gene swapping between
bacteria Muthukumar (2016); Palyulin  _et al._ (2014). The translocation of a
polymer through a narrow pore has attracted considerable attention both
experimentally Branton  _et al._ (2010); Wanunu (2012); Howorka and Siwy
(2009); Deamer  _et al._ (2016); Merchant  _et al._ (2010); Keyser (2011); Gu
_et al._ (2012); Venkatesan and Bashir (2011); Meller (2003); Movileanu (2008,
2009); Majd  _et al._ (2010) and theoretically Aksimentiev (2010); Milchev
(2011); Panja  _et al._ (2013); Sung and Park (1996); Lubensky and Nelson
(1999); Muthukumar (1999); Muthukumar and Kong (2006); Muthukumar (2010); Wong
and Muthukumar (2010); Muthukumar (2001); Kong and Muthukumar (2004); Sakaue
(2007); Panja  _et al._ (2007); Dubbeldam  _et al._ (2007); Gauthier and
Slater (2008a, b); Saito and Sakaue (2011, 2012); Sakaue (2016); Ledesma-
Aguilar  _et al._ (2012); Liu  _et al._ (2013); Rowghanian and Grosberg
(2011); Ikonen  _et al._ (2012a, b, 2013); Sarabadani  _et al._ (2014, 2017);
Sarabadani and Ala-Nissila (2018); Ghosh  _et al._ (2020); Buyukdagli  _et
al._ (2019); Cohen  _et al._ (2011, 2012a, 2012b); Luo  _et al._ (2007, 2008);
Kumar  _et al._ (2018) in the last two decades due to its potential in
designing inexpensive, fast and direct sequencing devices for biomolecules
like DNA. Biomolecules such as DNA, moving through a narrow pore blocks the
flow of ionic current through the pore. The resultant ionic current trace is
expected to give information of the DNA sequence that is passing through the
pore. This has led to the extensive use of both biological and synthetic
nanopores as biosensors, for example in sequence detection.

Biological nanopores such as $\alpha$-haemolysin Kasianowicz  _et al._ (1996),
MspA Derrington  _et al._ (2010); Butler  _et al._ (2008); Manrao  _et al._
(2012), phi29 Wendell  _et al._ (2009) and recently wild-type aerolysin
nanopore Cao  _et al._ (2016) have been used to investigate both single
stranded DNA (ssDNA) and double stranded DNA (dsDNA) sequencing. However,
biological nanopores are known to be unstable with changes in pH, temperature
and mechanical oscillations Howorka and Siwy (2009). Further, the role of pore
geometry in the translocation process and the ability to tune the pore
geometry to provide the best sequencing platform, is difficult to address in
the context of biological nanopores.

Solid state nanopores Dekker (2007); Wanunu and Meller (2007); Gershow and
Golovchenko (2007); Haque  _et al._ (2013); Luan  _et al._ (2012); Keyser  _et
al._ (2006), on the other hand, have been shown to be stable with respect to
reasonable changes in pH and temperature and can be fabricated to a wide range
of shapes and sizes. One of the challenges of nanopore based sequencing
technologies is that translocation of ssDNA through nanopores is extremely
fast, the ionic current signatures of single DNA nucleotides masked by
fluctuations. Therefore sequencing techniques have focused at slowing down the
transport of ssDNA before readout. In this regard, asymmetrical conical
nanopores with tapering angles have great potential for sensing applications,
the constricting geometry slowing down translocation of biomolecules and the
tip of the cone acting like a sensing zone Howorka and Siwy (2009); Keyser
(2011). This has led to several experimental studies of translocation of
biomolecules through fabricated solid state conical nanopores Zhou  _et al._
(2017). Conical nanocapillaries have been used to study detection of DNA and
other proteins, the conical shape of the pore resulting in ionic current
rectification at low salt concentrations Harrell  _et al._ (2006); Lan  _et
al._ (2011); Zhou  _et al._ (2017). An alternative technique using glass
nanocapillaries, as opposed to solid state nanopores, was capable of
simultaneous ionic current and fluorescent detection of DNA translocation
Thacker  _et al._ (2012). Even for biological nanopores such as the
$\alpha$-hemolysin, pore asymmetry is known to affect the capture rate and
current signature of DNA depending on its direction of transport Mathé  _et
al._ (2005).

On the theoretical front, there have been only a few studies on polymer
translocation through conical nanpores Nikoofard  _et al._ (2013); Nikoofard
and Fazli (2015); Sun  _et al._ (2018); Tu  _et al._ (2018). These studies
have shown that the shape of the asymmetric conical channel gives rise to an
effective entropic force that drives translocation and that the translocation
time is a non-monotonic function of the apex angle of the pore. However, in
all experimental scenarios, the translocation process is driven and the
interactions of the polymer with the pore is extremely important in
determining the efficiency of the translocation process. It is therefore
imperative to understand the extent to which the non-monotonicity in the
translocation times persists in presence of external drive and varying pore-
polymer interactions. In Refs. Sun  _et al._ (2018); Nikolaev and Gracheva
(2011), ionic conductivity and polymer translocation in the presence of
external driving in three different conical shaped nanopore geometries were
studied. Polymer translocation was shown to be heavily dependent on the
structures of the pore for different pore-polymer interactions and external
voltage. However, a systematic understanding of the non-linear effects of
translocation times on the pore-polymer interactions and external voltage as
the angle of the conical pore is varied, is missing.

In this paper, we study the driven translocation of a flexible polymer through
an interacting conical pore with a small entry and a large exit, using
Langevin dynamics simulations. We look at the mean residence time distribution
$\langle r(s)\rangle$ of a monomer $s$ inside the conical pore. The mean
residence time distribution shows non-monotonic features with the tapering
angle $\alpha$ of the pore which are distinctly different from that through a
rectangular channel of same length. We show how $\langle r(s)\rangle$ can be
tuned with $\alpha$ and the external driving force. We explain the
observations using free energy arguments which includes both the entropic
contributions due to confinement and the synergetics of the pore-polymer
interactions. Finally we show that the non-monotonic behavior of the mean
translocation time with changing apex angle, is strongly affected by both the
pore-polymer interactions and the external driving force.

Figure 1:  Schematic diagram of a polymer translocating through a conical pore
with an half apex angle $\alpha$. The width (at the apex) and the length of
the pore is $W_{0}=2.25\sigma$ and $L=16\sigma$, respectively.

We model the polymer by beads and springs in two dimensions. A schematic
diagram of a flexible polymer translocating from the cis to the trans side of
a conical pore is shown in Fig. 1. The beads of the polymer experience an
excluded volume interaction modeled by the Weeks-Chandler-Andersen (WCA)
potential of the form

$U_{\textrm{bead}}(r)=\begin{cases}4\varepsilon\left[\left(\frac{\sigma}{r}\right)^{12}-\left(\frac{\sigma}{r}\right)^{6}\right]+\varepsilon&\text{for}\
r\leq r_{min}\cr 0&\text{for}\ r>r_{min}\end{cases}$ (1)

where, $\varepsilon$ is the strength of the potential. The cutoff distance,
$r_{min}=2^{1/6}\sigma$, is set at the minimum of the potential. The
consecutive monomers in the chain interact via harmonic potential of the form

$U_{\textrm{bond}}(r)=K\left(r-r_{0}\right)^{2},$ (2)

where $K$ is the spring constant and $r_{0}$ is the equilibrium separation
between consecutive monomers of the chain.

Figure 2:  Potential energy landscape for various pore apex angles $\alpha=0$,
0.25, 1.5 and 4.5 used in our simulations. Potential depth increases from red
to purple. Figure 3: The mean residence time $\langle r(s)\rangle$, for a
flexible polymer of length $N=64$ as a function of $s/N$ for various pore
half-apex angles $\alpha$ for external driving forces (a) $f=0.1$, (b)
$f=0.15$, and (c) $f=0.2$. The strength of pore-monomer interaction is
$\varepsilon_{p}=0.9$. The inset shows the mean residence time for half-apex
angle $\alpha=0$ for various values of driving forces.

The pore and walls are made from stationary monomers separated by a distance
of $\sigma$ from each other. The conical pore is made up of two rows of
monomers symmetric about the $x$-axis with an apex angle $\theta=2\alpha$. The
length of the pore is taken to be $L=16\sigma$ with a width $W_{0}=2.25\sigma$
at the apex. This pore width allows only single-file entrance of the polymer
and avoid the formation of hairpin configurations at the apex opening Cohen
_et al._ (2011, 2012a, 2012b). The interaction of the pore with the polymer is
chosen to be the standard LJ form:

$U_{\textrm{pore}}(r)=\begin{cases}4\varepsilon_{p}\left[\left(\frac{\sigma}{r}\right)^{12}-\left(\frac{\sigma}{r}\right)^{6}\right]&\text{for}\
r\leq r_{c}\cr 0&\text{for}\ r>r_{c},\end{cases}$ (3)

where $\varepsilon_{p}$ denotes the potential depth and $r_{c}=2.5\sigma$ is
the cutoff distance. The interaction of polymer with walls,
$U_{\textrm{wall}}$, is modeled by WCA potential given by Eq. (1). The
potential energy landscape inside the pore for various pore angles are shown
in Fig. 2. For small apex angles, there is a strong attraction near the cis
side of the pore and a strong barrier near the trans side. As the apex angle
increases, the barrier near the trans side shifts toward the cis side of the
pore.

The polymer experiences a driving force,
${\boldsymbol{f}}_{\textrm{ext}}=f\hat{\boldsymbol{x}}$ directed along the
pore axis with magnitude $f$, which mimics the electrophoretic driving of
biopolymers through nanopores. To initiate the translocation process, we start
with a chain configuration with the first bead placed at the entrance of the
pore. This bead is fixed and the remaining beads are allowed to fluctuate so
that the chain can relax to its equilibrium configuration. The first bead is
then released and the translocation of the polymer across the pore is
monitored. The translocation time $\tau$ is defined as time elapsed between
the entrance of the first bead of the polymer and the exit of all the beads
from the channel. We discard all failed translocation events.

To integrate the equation of motion for the monomers of the chain we use
Langevin dynamics algorithm with velocity Verlet update. The equation of
motion for a monomer is given by

$m\ddot{\boldsymbol{r}}_{i}=-{\boldsymbol{\nabla}}U_{i}+{\boldsymbol{f}}_{ext}-\zeta{\boldsymbol{v}}_{i}+{\boldsymbol{\eta}}_{i},$
(4)

where $m$ is the monomer mass,
$U_{i}=U_{\textrm{bond}}+U_{\textrm{bead}}+U_{\textrm{wall}}+U_{\textrm{pore}}$
is the total potential experienced by $i$th monomer, $\zeta$ is the friction
coefficient, ${\boldsymbol{v}}_{i}$ is the monomer’s velocity, and
${\boldsymbol{\eta}}_{i}$ is the random force satisfying the fluctuation-
dissipation theorem $\langle{\eta}_{i}(t){\eta}_{j}(t^{\prime})\rangle=2\zeta
k_{B}T\delta_{ij}\delta(t-t^{\prime})$. The unit of energy, length and mass
are set by $\varepsilon$, $\sigma$, and $m$, respectively, which sets the unit
of time as $\sqrt{m\sigma^{2}/\varepsilon}$. In these units, we choose
$\zeta=1.0$, $K=10^{3}k_{B}T/\sigma$, $r_{0}=1.12\sigma$ and $k_{B}T=1.0$, and
the number of polymer beads $N=64$ in our simulations. A time step of $\Delta
t=0.005$ is used in all simulation runs.

We first look at the mean residence time, $\langle r(s)\rangle$, of a monomer
$s$ inside the pore. It is defined as the total time spent by the monomer $s$
inside the pore between its entrance at the pore apex and its first exit from
the base of the conical pore. In Fig. 3, $\langle r(s)\rangle$ is plotted as
as a function of monomer index $s$ for a polymer of length $N=64$ for
different values of pore half-apex angles $\alpha$, and various external
driving forces $f$ for a fixed pore-polymer interaction strength,
$\epsilon_{p}$.

We first look at $\alpha=0$, i.e a flat pore. As seen in Fig. 3(c, inset), for
small driving forces, $\langle r(s)\rangle$ increases with $s$ for the initial
monomers, then saturates and finally shows a non-monotonic variation for the
end monomers of the chain. This behavior can be explained using the tension
propagation theory Sakaue (2007, 2016); Rowghanian and Grosberg (2011); Saito
and Sakaue (2011, 2012); Ikonen  _et al._ (2012b, a, 2013); Sarabadani  _et
al._ (2014, 2017); Sarabadani and Ala-Nissila (2018) with pore-polymer
interactions. The part of the polymer on the cis-side is divided into two
distinct domains. The external driving force and the attractive interactions
of the pore with the polymer, pulls on the monomers nearer to the pore and
sets them in motion. The remaining monomers that are farther away from the
pore, do not experience the pull and on average remain at rest. As the polymer
gets sucked inside, more and more monomers on the cis side start responding to
the force, with a tension front separating the two domains propagating along
the length of the polymer. The time dependent drag experienced by a monomer
$\zeta(t)$ increases as the tension front propagates and more number of
monomers on the cis side get involved. This increase in the effective friction
is manifested in the residence times which show an initial increase with $s$,
implying that subsequent monomers spends more time inside the pore. This
continues until $\zeta(t)$ becomes maximum when the tension front reaches the
last monomer, maximum number of monomers at the cis-side participating in the
translocation process. Beyond this, the system enters the tail retraction
stage where the monomers on the cis side starts decreasing and therefore
$\zeta(t)$ decreases and so does the waiting time $\langle r(s)\rangle$. For
the end monomers exiting the extended pore, the effect of the attractive
interactions of the pore become more dominant compared to entropic effects
which increases their residence time inside the pore. As the external driving
force increases, this increase in $\langle r(s)\rangle$ for the end monomers
is minimal.

As $\alpha$ increases, we observed several interesting effects which can be
attributed to the conical nature of the pore. For non-zero $\alpha$, $\langle
r(s)\rangle$ shows a hump for the initial monomers. The initial increase
follows from the argument of tension propagation theory as stated above. The
decrease in $\langle r(s)\rangle$ observed before the saturation region is a
result of the entropic gain as the initial monomers move into a larger region
than that of a flat pore. The effective drag reduces leading to a lowering of
$\langle r(s)\rangle$. The saturation regime follows as the tension propagates
to the end monomers. The dominant effect of the pore-polymer interactions on
the end monomers which results in an increase in $\langle r(s)\rangle$,
reduces as $\alpha$ increases. Further note that $\langle r(s)\rangle$ is
lowest for all $s$ (except for the end monomers) for $\alpha=1.5$, increases
for $\alpha=2.5$ and decreases for $\alpha=4.5$. This indicates a non-
monotonic dependence of the total translocation time with $\alpha$ consistent
with earlier observations. For increasing driving forces, the subtle
competition between entropy and pore synergetics decreases and the features in
$\langle r(s)\rangle$ are less pronounced.

Figure 4:  (a) Two consecutive blobs inside the conical pore. The diameter
$\xi(x_{i})$ of a blob depends on the position $x_{i}$ along the pore axis.
This figure also shows the relation satisfied by two consecutive blobs. (b)
The location of the first blob is tangent to the beginning of the conical
pore. (c) The location of the $n$th blob is at a distance $y$ from the
entrance of the conical pore.  Figure 5: (Color online) (a) Sum of free energy
contributions due to confinement and external force $(F_{c}+F_{f})/k_{B}T$,
(b) Free energy due to pore interaction $F_{p}/k_{B}T$, (c) Total free energy
$F_{tot}/k_{B}T$, as a function of distance $y$ from the pore apex along the
pore axis for different half-apex angle $\alpha$ for a polymer of length
$N=64$ with an external force $f=0.1$. The inset shows the data near the peak
region.

We now provide a theoretical description of the translocation process using a
free energy argument. We need to estimate the free-energy change due to the
confinement, $F_{c}$, of the polymer inside the conical channel. Let us
consider a partly confined chain in the channel in the presence of an external
driving force ${\boldsymbol{f}}_{ext}$. The confinement of the polymer inside
the pore costs entropy. We assume that the part of the polymer chain that is
inside the pore breaks up into blobs of size
$\xi(x)=W_{0}\cos\alpha+2x\sin\alpha$ that are tangent to the pore walls as
shown in Fig 3. Then, the entropic penalty due to the confinement of chain in
the conical channel is of the order of $k_{B}T$ per blob. If $N_{b}(y)$
represents the number of blobs that penetrate a distance $y$ into the channel,
we have $F_{c}(y)\sim k_{B}TN_{b}(y)$.

To count $N_{b}(y)$, we consider two consecutive blobs inside the conical pore
at positions $x_{j}$ and $x_{j+1}$ with diameters $\xi(x_{j})$ and
$\xi(x_{j+1})$, respectively as shown in Fig. 4. They satisfy the relation

$x_{j+1}=x_{j}+\frac{1}{2}\left[\xi(x_{j})+\xi(x_{j+1})\right].$ (5)

Using this recursion relation, one can easily obtain an expression between the
position of the blob $x_{j}$ and its number $j$ along the pore Nikoofard  _et
al._ (2013) as

$x_{j}=\mathcal{Q}^{j-1}\left(x_{1}+\frac{W_{0}}{2\tan\alpha}\right)-\frac{W_{0}}{2\tan\alpha},$
(6)

where $\mathcal{Q}=(1+\sin\alpha)/(1-\sin\alpha)$. The first blob is tangent
to the beginning of the pore and its location along the axis is given by
$x_{1}=\xi(x_{1})/2$. The last (say $n$th) blob is tangent to the pore at a
distance $y$ from the pore entrance, hence its location $x_{n}$ along the axis
is given by $x_{n}=y-\xi(x_{n})/2$. The blob number $n$, and hence $N_{b}(y)$,
can be obtained by Using Eq. (6) along with $x_{1}$ and $x_{n}$, and hence the
free-energy cost due to the confinement as a function of distance $y$ along
the pore axis is given by

$\frac{F_{c}(y)}{k_{B}T}\sim
N_{b}(y)\sim\frac{\log\mathcal{P}}{\log\mathcal{Q}},$ (7)

where $\mathcal{P}=1+2y\tan\alpha/W_{0}$.

The second contribution to the free-energy is due to the constant external
force, $f$, experienced by the segment of the polymer which is inside the
pore, denoted by $F_{f}$. The value of $F_{f}$ changes with the number of
monomers which are present inside the pore. The free energy change corresponds
to the work done to displace the chain by a distance $y$ inside the pore and
is given by

$\displaystyle\frac{F_{f}(y)}{k_{B}T}$ $\displaystyle\sim$
$\displaystyle-\int_{0}^{y}fN_{b}(x)dx$ (8) $\displaystyle\sim$
$\displaystyle-\frac{f}{2\log\mathcal{Q}}\left[2y-\left(2y+\frac{W_{0}}{\tan\alpha}\right)\log\mathcal{P}\right],$
(9)

where $f$ is the magnitude of the external force ${\boldsymbol{f}}_{ext}$
acting inside the pore towards the trans direction.

The final contribution to the free-energy is due to the attractive
interactions with the walls of the channel. We need to determine the number of
monomers in the blobs that are in contact with two walls of the conical
channel. In 2D, the number of monomers in $j$th blob is given by
$m(x_{j})=\left(\xi(x_{j})/\sigma\right)^{4/3}$. The total number of monomers
$N_{n}$ in $n$ blobs up to the distance $y$ inside the channel can then be
obtained from the constraint $N_{n}(y)=\sum_{j=1}^{n}m(x_{j})$. Substituting
$x_{j}$ from the recursion relation Eq. (6), and number of blobs $N_{b}(y)$,
we get

$N_{n}(y)=\sigma^{-\frac{4}{3}}\frac{\left(2y\sin\alpha+W_{0}\cos\alpha\right)^{\frac{4}{3}}-\left(W_{0}\cos\alpha\right)^{\frac{4}{3}}}{(1+\sin\alpha)^{\frac{4}{3}}-(1-\sin\alpha)^{\frac{4}{3}}}.$
(10)

The fraction of monomers that are in contact with a wall of the channel is
then given by $N_{n}(y)(\sigma/\xi(y))$. If $V(y)$ denotes the interaction
energy, which is due to the pore-polymer interaction and given by the LJ
potential (Eq. (3)), the free energy contribution due to the attractive
interaction for a polymer that has entered the pore up to a distance $y$ is
given by

$\frac{F_{p}(y)}{k_{B}T}\sim V(y)N_{n}(y)\left(\frac{\sigma}{\xi(y)}\right).$
(11)

The total free energy is then given by

$\frac{F_{tot}(y)}{k_{B}T}=\frac{1}{k_{B}T}\left(F_{f}(y)+AF_{p}(y)+CF_{c}(y)\right),$
(12)

where $A$ and $C$ are undetermined factors.

In Fig. 5, we have plotted the total free energy $F_{tot}/k_{B}T$, given by
Eq. (12), for parameter values $A=0.035$ and $C=1$, as a function of distance
$y$ along the pore axis for different half-apex angle $\alpha$ ranging from
$\alpha=0.5^{\circ}$ to $\alpha=5^{\circ}$ for a polymer of length $N=64$ with
an external force $f=0.1$ and pore polymer interaction energy strength
$\varepsilon_{p}=1$. The free energy exhibits a barrier that needs to be
overcome by the polymer to translocate towards the trans side successfully. As
$\alpha$ increases, the barrier height also increases indicating that it is
relatively more difficult for the polymer to translocate towards the trans
end. The free energy barrier attains a maximum height at $\alpha=2^{\circ}$
and on increasing $\alpha$ further, the barrier starts decreasing showing that
polymer can easily translocate from the conical pore for larger apex angle.
This explains the non-monotonic dependence of residence times and average
translocation times on the pore angle.

In the above analysis, we have taken the interaction energy, which comes due
to pore-polymer interactions, to be one one-dimensional. However, the actual
interaction energy is two dimensional. The potential energy landscape
presented in Fig. 2, clearly indicate that for very small values of $\alpha$,
the position of the potential barrier is nearer to the trans side of pore,
which corroborates the free energy picture. So for small apex angles, the
translocation process is an interplay between confinement effects and
interactions of the polymer with the pore. But as the $\alpha$ increases,
position of the potential barrier start moving towards the apex of the pore as
can be seen from the red region moving close to the pore entry. As the driving
force is increased, the translocation is faster. The polymer will take less
time to overcome the barrier as compared to the smaller values of driving
forces. At sufficiently strong driving force, effect of pore-polymer
interaction becomes negligible and translocation time is expected to decrease
monotonically with the apex angle of the pore (Fig. 2).

Figure 6:  (a) Average translocation time $\langle\tau\rangle$ as a function
of pore apex angle $\alpha$: (a) For various strength of pore-polymer
interaction $\varepsilon_{p}$ at pulling force $f=0.1$. (b) For various
pulling forces $f$ by keeping $\varepsilon_{p}=0.9$. The length of the polymer
is $N=64$.

In Fig. 6(a), we plot the variation of mean translocation time
$\langle\tau\rangle$ as a function of $\alpha$ for different strengths of
pore-polymer interaction, $\varepsilon_{p}$, at a fixed value of the external
force $f=0.1$. As is evident from the free energy argument, $F_{p}$ dominates
the translocation process as $\varepsilon_{p}$ increases. With increasing
$\varepsilon_{p}$, the free energy barrier near the exit of the pore is high
and the polymer spends longer time inside the pore and therefore,
$\langle\tau\rangle$ increases with $\varepsilon_{p}$ for all values of
$\alpha$. With increasing $\alpha$ since the barrier falls drastically, the
translocation times are significantly less. However, the non-monotonic feature
persists even for driven translocation with the hump observed near
$\alpha\approx 2^{\circ}$. In Fig. 6(b), we observe that with increasing
external drive $f$ at a fixed $\varepsilon_{p}$, the mean translocation time
$\langle\tau\rangle$ decreases for all $\alpha$. The non-monotonic feature
starts disappearing at higher $f$.

We have studied the driven translocation of a flexible polymer through an
interacting cone shaped pore. Conical nanopores have several advantages in
bio-sensing applications and the influence on translocation behavior of the
interactions with the surface of the pore and the external drive are of
significant interest. Using free energy arguments, we have shown that non-
monotonic features in translocation times observed in conical pores persist
even in the presence of the experimentally relevant scenarios of driven
translocation with pore-polymer interactions. Extensive Langevin dynamics
simulations confirm these observations. The mean residence times also show
behaviors characteristic of translocation through conical pores. Their
behavior with changing external drive is consistent with tension propagation
along the polymer backbone. The mean translocation time $\langle\tau\rangle$
is found to be strongly dependent on the strength of pore-polymer interaction
and the external driving force.

## References

  * Muthukumar (2016) M. Muthukumar,  _Polymer translocation_ (CRC press, 2016).
  * Palyulin  _et al._ (2014) V. V. Palyulin, T. Ala-Nissila, and R. Metzler, Soft matter 10, 9016 (2014).
  * Branton  _et al._ (2010) D. Branton, D. W. , A. Marziali, H. Bayley, S. A. Benner, T. Butler, M. Di Ventra, S. Garaj, A. Hibbs, X. Huang, _et al._ , in  _Nanoscience and technology: A collection of reviews from Nature Journals_ (World Scientific, 2010) pp. 261–268.
  * Wanunu (2012) M. Wanunu, Physics of life reviews 9, 125 (2012).
  * Howorka and Siwy (2009) S. Howorka and Z. Siwy, Chemical Society Reviews 38, 2360 (2009).
  * Deamer  _et al._ (2016) D. Deamer, M. Akeson, and D. Branton, Nature biotechnology 34, 518 (2016).
  * Merchant  _et al._ (2010) C. A. Merchant, K. Healy, M. Wanunu, V. Ray, N. Peterman, J. Bartel, M. D. Fischbein, K. Venta, Z. Luo, A. C. Johnson, _et al._ , Nano letters 10, 2915 (2010).
  * Keyser (2011) U. F. Keyser, Journal of The Royal Society Interface 8, 1369 (2011).
  * Gu  _et al._ (2012) L.-Q. Gu, M. Wanunu, M. X. Wang, L. McReynolds, and Y. Wang, Expert review of molecular diagnostics 12, 573 (2012).
  * Venkatesan and Bashir (2011) B. M. Venkatesan and R. Bashir, Nature nanotechnology 6, 615 (2011).
  * Meller (2003) A. Meller, Journal of physics: condensed matter 15, R581 (2003).
  * Movileanu (2008) L. Movileanu, Soft Matter 4, 925 (2008).
  * Movileanu (2009) L. Movileanu, Trends in Biotechnology 27, 333 (2009).
  * Majd  _et al._ (2010) S. Majd, E. C. Yusko, Y. N. Billeh, M. X. Macrae, J. Yang, and M. Mayer, Current Opinion in Biotechnology 21, 439 (2010).
  * Aksimentiev (2010) A. Aksimentiev, Nanoscale 2, 468 (2010).
  * Milchev (2011) A. Milchev, Journal of Physics: Condensed Matter 23, 103101 (2011).
  * Panja  _et al._ (2013) D. Panja, G. T. Barkema, and A. B. Kolomeisky, Journal of Physics: Condensed Matter 25, 413101 (2013).
  * Sung and Park (1996) W. Sung and P. Park, Physical review letters 77, 783 (1996).
  * Lubensky and Nelson (1999) D. K. Lubensky and D. R. Nelson, Biophysical journal 77, 1824 (1999).
  * Muthukumar (1999) M. Muthukumar, The Journal of Chemical Physics 111, 10371 (1999).
  * Muthukumar and Kong (2006) M. Muthukumar and C. Kong, Proceedings of the National Academy of Sciences 103, 5273 (2006).
  * Muthukumar (2010) M. Muthukumar, The Journal of chemical physics 132, 05B605 (2010).
  * Wong and Muthukumar (2010) C. T. A. Wong and M. Muthukumar, The Journal of chemical physics 133, 07B607 (2010).
  * Muthukumar (2001) M. Muthukumar, Physical Review Letters 86, 3188 (2001).
  * Kong and Muthukumar (2004) C. Kong and M. Muthukumar, The Journal of chemical physics 120, 3460 (2004).
  * Sakaue (2007) T. Sakaue, Physical Review E 76, 021803 (2007).
  * Panja  _et al._ (2007) D. Panja, G. T. Barkema, and R. C. Ball, Journal of Physics: Condensed Matter 19, 432202 (2007).
  * Dubbeldam  _et al._ (2007) J. Dubbeldam, A. Milchev, V. Rostiashvili, and T. A. Vilgis, EPL (Europhysics Letters) 79, 18002 (2007).
  * Gauthier and Slater (2008a) M. G. Gauthier and G. W. Slater, The Journal of chemical physics 128, 02B612 (2008a).
  * Gauthier and Slater (2008b) M. G. Gauthier and G. W. Slater, The Journal of Chemical Physics 128, 05B619 (2008b).
  * Saito and Sakaue (2011) T. Saito and T. Sakaue, The European Physical Journal E 34, 135 (2011).
  * Saito and Sakaue (2012) T. Saito and T. Sakaue, Physical Review E 85, 061803 (2012).
  * Sakaue (2016) T. Sakaue, Polymers 8, 424 (2016).
  * Ledesma-Aguilar  _et al._ (2012) R. Ledesma-Aguilar, T. Sakaue, and J. M. Yeomans, Soft Matter 8, 1884 (2012).
  * Liu  _et al._ (2013) L. Liu, C. Yang, K. Zhao, J. Li, and H.-C. Wu, Nature communications 4, 1 (2013).
  * Rowghanian and Grosberg (2011) P. Rowghanian and A. Y. Grosberg, The Journal of Physical Chemistry B 115, 14127 (2011).
  * Ikonen  _et al._ (2012a) T. Ikonen, A. Bhattacharya, T. Ala-Nissila, and W. Sung, Physical Review E 85, 051803 (2012a).
  * Ikonen  _et al._ (2012b) T. Ikonen, A. Bhattacharya, T. Ala-Nissila, and W. Sung, The Journal of chemical physics 137, 085101 (2012b).
  * Ikonen  _et al._ (2013) T. Ikonen, A. Bhattacharya, T. Ala-Nissila, and W. Sung, EPL (Europhysics Letters) 103, 38001 (2013).
  * Sarabadani  _et al._ (2014) J. Sarabadani, T. Ikonen, and T. Ala-Nissila, The Journal of Chemical Physics 141, 214907 (2014).
  * Sarabadani  _et al._ (2017) J. Sarabadani, T. Ikonen, H. Mökkönen, T. Ala-Nissila, S. Carson, and M. Wanunu, Scientific reports 7, 1 (2017).
  * Sarabadani and Ala-Nissila (2018) J. Sarabadani and T. Ala-Nissila, Journal of Physics: Condensed Matter 30, 274002 (2018).
  * Ghosh  _et al._ (2020) B. Ghosh, J. Sarabadani, S. Chaudhury, and T. Ala-Nissila, Journal of Physics: Condensed Matter 33, 015101 (2020).
  * Buyukdagli  _et al._ (2019) S. Buyukdagli, J. Sarabadani, and T. Ala-Nissila, Polymers 11, 118 (2019).
  * Cohen  _et al._ (2011) J. A. Cohen, A. Chaudhuri, and R. Golestanian, Physical review letters 107, 238102 (2011).
  * Cohen  _et al._ (2012a) J. A. Cohen, A. Chaudhuri, and R. Golestanian, Physical Review X 2, 021002 (2012a).
  * Cohen  _et al._ (2012b) J. A. Cohen, A. Chaudhuri, and R. Golestanian, The Journal of chemical physics 137, 204911 (2012b).
  * Luo  _et al._ (2007) K. Luo, T. Ala-Nissila, S.-C. Ying, and A. Bhattacharya, Physical Review Letters 99, 148102 (2007).
  * Luo  _et al._ (2008) K. Luo, T. Ala-Nissila, S.-C. Ying, and A. Bhattacharya, Physical Review Letters 100, 058101 (2008).
  * Kumar  _et al._ (2018) R. Kumar, A. Chaudhuri, and R. Kapri, The Journal of chemical physics 148, 164901 (2018).
  * Kasianowicz  _et al._ (1996) J. J. Kasianowicz, E. Brandin, D. Branton, and D. W. Deamer, Proceedings of the National Academy of Sciences 93, 13770 (1996).
  * Derrington  _et al._ (2010) I. M. Derrington, T. Z. Butler, M. D. Collins, E. Manrao, M. Pavlenok, M. Niederweis, and J. H. Gundlach, Proceedings of the National Academy of Sciences 107, 16060 (2010).
  * Butler  _et al._ (2008) T. Z. Butler, M. Pavlenok, I. M. Derrington, M. Niederweis, and J. H. Gundlach, Proceedings of the National Academy of Sciences 105, 20647 (2008).
  * Manrao  _et al._ (2012) E. A. Manrao, I. M. Derrington, A. H. Laszlo, K. W. Langford, M. K. Hopper, N. Gillgren, M. Pavlenok, M. Niederweis, and J. H. Gundlach, Nature biotechnology 30, 349 (2012).
  * Wendell  _et al._ (2009) D. Wendell, P. Jing, J. Geng, V. Subramaniam, T. J. Lee, C. Montemagno, and P. Guo, Nature nanotechnology 4, 765 (2009).
  * Cao  _et al._ (2016) C. Cao, Y.-L. Ying, Z.-L. Hu, D.-F. Liao, H. Tian, and Y.-T. Long, Nature Nanotechnology 11, 713 (2016).
  * Dekker (2007) C. Dekker, Nature nanotechnology 2, 209 (2007).
  * Wanunu and Meller (2007) M. Wanunu and A. Meller, Nano letters 7, 1580 (2007).
  * Gershow and Golovchenko (2007) M. Gershow and J. A. Golovchenko, Nature nanotechnology 2, 775 (2007).
  * Haque  _et al._ (2013) F. Haque, J. Li, H.-C. Wu, X.-J. Liang, and P. Guo, Nano today 8, 56 (2013).
  * Luan  _et al._ (2012) B. Luan, G. Stolovitzky, and G. Martyna, Nanoscale 4, 1068 (2012).
  * Keyser  _et al._ (2006) U. F. Keyser, B. N. Koeleman, S. Van Dorp, D. Krapf, R. M. Smeets, S. G. Lemay, N. H. Dekker, and C. Dekker, Nature Physics 2, 473 (2006).
  * Zhou  _et al._ (2017) J. Zhou, Y. Wang, L. D. Menard, S. Panyukov, M. Rubinstein, and J. M. Ramsey, Nature communications 8, 1 (2017).
  * Harrell  _et al._ (2006) C. C. Harrell, Y. Choi, L. P. Horne, L. A. Baker, Z. S. Siwy, and C. R. Martin, Langmuir 22, 10837 (2006).
  * Lan  _et al._ (2011) W.-J. Lan, D. A. Holden, and H. S. White, Journal of the American Chemical Society 133, 13300 (2011).
  * Thacker  _et al._ (2012) V. V. Thacker, S. Ghosal, S. Hernández-Ainsa, N. A. Bell, and U. F. Keyser, Applied physics letters 101, 223704 (2012).
  * Mathé  _et al._ (2005) J. Mathé, A. Aksimentiev, D. R. Nelson, K. Schulten, and A. Meller, Proceedings of the National Academy of Sciences 102, 12377 (2005).
  * Nikoofard  _et al._ (2013) N. Nikoofard, H. Khalilian, and H. Fazli, The Journal of Chemical Physics 139, 074901 (2013).
  * Nikoofard and Fazli (2015) N. Nikoofard and H. Fazli, Soft Matter 11, 4879 (2015).
  * Sun  _et al._ (2018) L.-Z. Sun, H. Li, X. Xu, and M.-B. Luo, Journal of Physics: Condensed Matter 30, 495101 (2018).
  * Tu  _et al._ (2018) B. Tu, S. Bai, B. Lu, and Q. Fang, Scientific reports 8, 1 (2018).
  * Nikolaev and Gracheva (2011) A. Nikolaev and M. E. Gracheva, Nanotechnology 22, 165202 (2011).