# Hardness of the Generalized Coloring Numbers

Michael Breen-McKay  North Carolina State UniversityDepartment of
Mathematics2108 SAS HallRaleigh, NC<EMAIL_ADDRESS>Brian
Lavallee  University of UtahSchool of Computing50 Central Campus DriveSalt
Lake City, UT<EMAIL_ADDRESS><EMAIL_ADDRESS>Blair D.
Sullivan  University of UtahSchool of Computing50 Central Campus DriveSalt
Lake City, UT<EMAIL_ADDRESS><EMAIL_ADDRESS>
(15 September 2022)

###### Abstract

The generalized coloring numbers of Kierstead and Yang (Order 2003) offer an
algorithmically-useful characterization of graph classes with bounded
expansion. In this work, we consider the hardness and approximability of these
parameters. First, we complete the work of Grohe et al. (WG 2015) by showing
that computing the weak 2-coloring number is NP-hard. Our approach further
establishes that determining if a graph has weak $r$-coloring number at most
$k$ is para-NP-hard when parameterized by $k$ for all $r\geq 2$. We adapt this
to determining if a graph has $r$-coloring number at most $k$ as well, proving
para-NP-hardness for all $r\geq 2$. Para-NP-hardness implies that no XP
algorithm (runtime $O(n^{f(k)})$) exists for testing if a generalized coloring
number is at most $k$. Moreover, there exists a constant $c$ such that it is
NP-hard to approximate the generalized coloring numbers within a factor of
$c$. To complement these results, we give an approximation algorithm for the
generalized coloring numbers, improving both the runtime and approximation
factor of the existing approach of Dvořák (EuJC 2013). We prove that greedily
ordering vertices with small estimated backconnectivity achieves a
$(k-1)^{r-1}$-approximation for the $r$-coloring number and an
$O(k^{r-1})$-approximation for the weak $r$-coloring number.

11footnotetext: This work was supported in part by the Gordon & Betty Moore
Foundation under award GBMF4560 to Blair D. Sullivan.

##  1 Introduction

In 2008, Nešetřil and Ossona de Mendez introduced _bounded expansion_ as a
notion of sparsity in graph classes [14]. Bounded expansion generalizes
_proper minor-closed_ classes which contain (among other things) the heavily-
studied classes of _bounded treewidth_ and _planar_ graphs. Nešetřil and
Ossona de Mendez characterized classes with bounded expansion by the existence
of low-treedepth colorings [14], enabling the first of many algorithmic
approaches to tackle problems on these broad classes. While part of the appeal
of bounded expansion is its numerous characterizations, low-treedepth
colorings alone allowed Dvořák et al. to prove that FO-Model Checking is
_fixed-parameter tractable_ (FPT) in graphs from a class of bounded expansion
[4]. Beyond the many problems expressible in first order logic,
characterizations of bounded expansion have been used to give FPT algorithms
for Subgraph Counting [12], Steiner Tree [10], and numerous others [1, 2, 6].

In this work, we focus on the _generalized coloring numbers_ , introduced by
Kierstead and Yang in 2003 [9], which also characterize classes of bounded
expansion [18]. The generalized coloring numbers (consisting of the _$r$
-coloring numbers_ and the _weak $r$-coloring numbers_) extend the notion of
_degeneracy_ to neighborhoods of radius $r$. The generalized coloring numbers
are also deeply connected to other important graph properties. In fact, the
$n$-coloring number and the weak $n$-coloring number are equivalent to the
_treewidth_ and _treedepth_ of a graph with $n$ vertices, respectively. Prior
to the introduction of bounded expansion, the generalized coloring numbers
were studied primarily in the context of the _game chromatic number_ [9].

Zhu’s connection of these parameters to bounded expansion in 2009 [18] renewed
interest in analyzing and utilizing them. Reidl et al. used the weak coloring
numbers to prove that _neighborhood complexity_ characterizes bounded
expansion [16], while Nadara et al. initiated an empirical study of
algorithmic techniques used to compute the generalized coloring numbers in
practice [11]. The generalized coloring numbers also led to new algorithms for
bounded expansion; Dvořák gave an approximation for Dominating Set [3], and
Reidl and Sullivan gave an exact FPT algorithm for Subgraph Counting [15].
Both of these algorithms rely on computing a linear order of the vertices
which witnesses a small weak $r$-coloring number for some fixed radius $r$.
Grohe et al. showed that determining the weak $r$-coloring number is NP-hard
when $r\geq 3$ [5], and so both algorithms use an approximation to find a
suitable order. Dvořák gave a parameterized approximation for the weak
$r$-coloring number in $O(rn^{3})$ time through an approximation for _$r$
-admissibility_ [3].

In this paper, we prove that both of the generalized coloring numbers are
para-NP-hard to compute when $r\geq 2$. For the weak coloring numbers, this
improves upon the result of Grohe et al. [5] who showed that the weak
$r$-coloring number is NP-hard to compute when $r\geq 3$. For the coloring
numbers, no hardness results were previously known. Our approach uses 2-Clause
3-SAT in contrast to Balanced Complete Bipartite Subgraph as in [5]. Para-NP-
hardness implies that there does not exist an XP algorithm (i.e. an algorithm
with runtime $O(n^{f(k)})$) to check if a generalized coloring number is at
most $k$. Additionally, it implies that there exists a constant $c$ such that
it is NP-hard to approximate the generalized coloring numbers within a factor
of $c$.

Finally, we show that there is a $(k-1)^{r-1}$-approximation algorithm for the
$r$-coloring number, improving both the runtime and approximation guarantees
given by Dvořák [3]. The algorithm applies a greedy strategy directly to the
coloring number rather than using admissibility as an intermediary. We further
prove that the order produced by this algorithm gives an
$O(k^{r-1})$-approximation for the weak $r$-coloring number.

##  2 Preliminaries

We examine properties of _total orders_ defined on the vertices of simple,
undirected graphs. For a graph $G=(V,E)$, we will frequently use $n=|V|$ and
$m=|E|$ to denote the number of vertices and edges respectively. For
flexibility in our analysis, we define the properties of interest using
_prefix orders_.

######  Definition 2.1.

A prefix order is a _strict partial order_ which is also _downward total_.
That is, a prefix order $\sigma$ of a set $V$ satisfies the following
conditions for all $a,b,c\in V$:

  * •

irreflexivity: $a\not<_{\sigma}a$

  * •

asymmetry: if $a<_{\sigma}b$, then $b\not<_{\sigma}a$

  * •

transitivity: if $a<_{\sigma}b$ and $b<_{\sigma}c$, then $a<_{\sigma}c$

  * •

downward totality: if $a<_{\sigma}c$ and $b<_{\sigma}c$, then either
$a<_{\sigma}b$ or $b<_{\sigma}a$

We say an element $a$ is ordered if there exists an element $b$ such that
$a<_{\sigma}b$. All other elements are unordered.

Intuitively, a prefix order is an “incomplete” total order where the position
of only the first $i$ elements has been decided and the remaining unordered
elements will be added to the end of the order. Given a prefix order $\sigma$
of the vertices of $G$, we use $G_{\sigma}$ to refer to the ordered graph
defined by the combination of $G$ and $\sigma$. A prefix order naturally
partitions the neighborhood of a vertex $u$ into its forward and backward
neighbors. The same method of partitioning can also be applied to the
$r$-neighborhood of $u$ (i.e. the set of vertices of distance at most $r$ from
$u$ in $G$), but more restrictive notions of forward neighbors have better
theoretical and algorithmic applications. Specifically, we use $r$-reachable
and weak $r$-reachable as criteria to determine if a vertex $v$ is a forward
neighbor of $u$.

######  Definition 2.2.

Given a graph $G=(V,E)$ and a prefix order $\sigma$, let $P\subseteq G$ be a
$u$-$v$ path of length at most $r$. If $v\not<_{\sigma}u$ and $p<_{\sigma}u$
for all $p\in P\setminus\\{u,v\\}$, then we say that $P$ is an $r$-qualifying
path and $v$ is $r$-reachable from $u$. Similarly, if $v\not<_{\sigma}u$ and
$p<_{\sigma}v$ for all $p\in P\setminus\\{u,v\\}$, then we say $P$ is a weak
$r$-qualifying path and $v$ is weakly $r$-reachable from $u$. Note that all
$r$-qualifying paths are also weak $r$-qualifying paths.

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$$v_{9}$$v_{10}$

$\begin{array}[]{c|c|c|c}r&\operatorname{R}_{r}(v_{4},G\sigma)&\operatorname{W}_{r}(v_{4},G_{\sigma})\\\
\hline\cr 1&\\{v_{5},v_{8}\\}&\\{v_{5},v_{8}\\}\\\
2&\\{v_{5},v_{7},v_{8},v_{9}\\}&\\{v_{5},v_{6},v_{7},v_{8},v_{9}\\}\\\
3&\\{v_{5},v_{6},v_{7},v_{8},v_{9}\\}&\\{v_{5},v_{6},v_{7},v_{8},v_{9},v_{10}\\}\end{array}$

Figure 1:  We give a total order on the vertices of a graph $G$. The chart
gives the various vertices reachable from $v_{4}$ under each definition.

We note that there are minor inconsistencies in the definitions of these terms
in prior work. In particular, we do not consider a vertex to be reachable from
itself (resulting in a value that is off-by-one from the definition in e.g.
[5]). More significantly, we also reverse the direction of the order used in
[5] to adhere to a left-to-right convention. Thus, a vertex reaches to the
right using vertices to the left, rather than reaching to the left using
vertices to the right. Both definitions are equivalent, and this can be seen
by simply reversing $\sigma$.

We use $\operatorname{R}_{r}(u,G_{\sigma})$ to denote the set of vertices in
$G$ which are $r$-reachable from $u$ with respect to $\sigma$ and
$\operatorname{W}_{r}(u,G_{\sigma})$ to denote the set of vertices which are
weakly $r$-reachable. The $r$-reach and the weak $r$-reach refer to the sizes
of these sets respectively. Figure 1 shows the differences between
$\operatorname{R}_{r}(u,G_{\sigma})$ and $\operatorname{W}_{r}(u,G_{\sigma})$
on a small example graph. Using the notions of $r$-reach and weak $r$-reach as
analogues of forward degree leads to two natural generalizations of
degeneracy.

######  Definition 2.3.

Given a graph $G=(V,E)$, let $\Pi$ be the set of all total orders of $V$. The
$r$-coloring number and the weak $r$-coloring number of a graph $G$ are
defined as

$\operatorname{col}_{r}(G):=\min\limits_{\sigma\in\Pi}\max\limits_{u\in
V}|\operatorname{R}_{r}(u,G_{\sigma})|\hskip
28.45274pt\operatorname{wcol}_{r}(G):=\min\limits_{\sigma\in\Pi}\max\limits_{u\in
V}|\operatorname{W}_{r}(u,G_{\sigma})|.$

We will also use $\operatorname{col}_{r}(G_{\sigma})$ and
$\operatorname{wcol}_{r}(G_{\sigma})$ to refer to the maximum $r$-reach and
maximum weak $r$-reach over all vertices with respect to an order $\sigma$.
Under the given definitions, both of the generalized coloring numbers are
closely linked with other important graph measures. Specifically,
$\operatorname{col}_{n}(G)$ is equal to the treewidth [5] and
$\operatorname{wcol}_{n}(G)$ is one less than the treedepth [13]. Since
$\operatorname{col}_{1}(G)=\operatorname{wcol}_{1}(G)=\operatorname{degen}(G)$,
these parameters offer an interpolation between degeneracy and treewidth or
treedepth. In this paper, we consider the problem of computing the generalized
coloring numbers.

Input: a graph $G=(V,E)$ and an integer $k\in\mathbb{N}$. Problem: is
$\operatorname{col}_{r}(G)\leq k$? $r$-Orderable

Input: a graph $G=(V,E)$ and an integer $k\in\mathbb{N}$. Problem: is
$\operatorname{wcol}_{r}(G)\leq k$? Weak $r$-Orderable

We use Minimum $r$-Orderability and Minimum Weak $r$-Orderability to refer to
the corresponding optimization problems. Due to the equivalence of the
1-coloring number and weak 1-coloring number with degeneracy, we note that
both 1-Orderable and Weak 1-Orderable can be solved in linear time using a
greedy algorithm. Finally, our results make use of Exact $r$-SAT and 2-Clause
3-SAT, defined below.

Input: a CNF-formula $\phi$ with clauses $c_{1},\dots,c_{m}$ consisting of
variables $x_{1},\dots,x_{n}$ such that each clause contains _exactly_ $r$
different variables. Problem: is there an assignment of $x_{1},\dots,x_{n}$
that satisfies $\phi$? Exact $r$-SAT

Input: a CNF-formula $\phi$ with clauses $c_{1},\dots,c_{m}$ consisting of
variables $x_{1},\dots,x_{n}$ such that each clause contains _at most_ 3
variables and each literal ($x_{j}$ or $\overline{x}_{j}$) appears in
_exactly_ 2 clauses. Problem: is there an assignment of $x_{1},\dots,x_{n}$
that satisfies $\phi$? 2-Clause 3-SAT

Karp proved that 3-SAT is NP-complete in [8], implying that Exact $r$-SAT is
NP-hard for $r\geq 3$. To see that 2-Clause 3-SAT is also NP-hard, we use
Theorem 2.1 of [17] which states that SAT remains NP-complete when restricted
to instances with 2 or 3 variables per clause and at most 3 occurrences per
variable. These instances of SAT can be converted to 2-Clause 3-SAT in the
following manner. First, we may assume that each literal appears at most twice
(and at least once), since a variable which appears only positively or only
negatively can be preprocessed without consequence. If a literal $x$ appears
only once, then we add the following clauses using the new variables
$y_{1},\dots,y_{5}$ so that it appears twice.

$(x\lor y_{1}\lor\overline{y}_{2})\land(y_{1}\lor
y_{3}\lor\overline{y}_{4})\land(\overline{y}_{1}\lor
y_{3}\lor\overline{y}_{4})\land(\overline{y}_{1}\lor
y_{4}\lor\overline{y}_{5})\land(y_{2}\lor
y_{4}\lor\overline{y}_{5})\land(y_{2}\lor\overline{y}_{3}\lor
y_{5})\land(\overline{y}_{2}\lor\overline{y}_{3}\lor y_{5})$

The additional variables $y_{1},\dots,y_{5}$ all have exactly two appearances
per literal, and the additional clauses can be satisfied by setting
$y_{1},\dots,y_{5}$ to true. By repeatedly adding 5 new variables and 7 new
clauses in this pattern for every literal which only appears once, we can
ensure that we end up with an instance of 2-Clause 3-SAT.

For the remainder of this paper, we will also assume that no variable appears
twice in a single clause in instances of 2-Clause 3-SAT and Exact $r$-SAT. If
a literal and its negation both appear, then the clause can be removed since
it will be satisfied by any assignment. If the same literal appears twice,
then one appearance can be removed without changing the instance. To adhere to
the limitations of Exact $r$-SAT, we replace the removed variable with a new
variable $y$ by duplicating the clause, adding $y$ to one copy, and adding
$\overline{y}$ to the other. We also assume that any clauses with only a
single literal have been preprocessed.

##  3 Computational Complexity

In [5], the authors showed that Weak $r$-Orderable is NP-hard for $r\geq 3$.
Below, we prove the stronger result that determining if
$\operatorname{wcol}_{r}(G)\leq k$ is para-NP-hard parameterized by $k$, even
when $r=2$. Moreover, we show that determining if
$\operatorname{col}_{r}(G)\leq k$ is also para-NP-hard for $r\geq 2$.

###  3.1 Weak 2-Orderable is Para-NP-hard

In this section, we prove that Weak 2-Orderable parameterized by the natural
parameter $k$ is para-NP-hard. This also closes an open question regarding the
NP-hardness of Weak 2-Orderable from [5]. Our proof reduces from 2-Clause
3-SAT and shows that determining if $\operatorname{wcol}_{2}(G)\leq 5$ is NP-
hard. First, we describe the reduction.

######  Definition 3.1.

Given an instance $\varphi$ of 2-Clause 3-SAT, let $G(\varphi)$ be the
following graph. For each clause $c_{i}\in\varphi$, we create 6 vertices
$u_{i}^{1},\dots,u_{i}^{6}$ in $G(\varphi)$. If $c_{i}$ only contains 2
literals, we add 2 more vertices $f_{i}$ and $f^{\prime}_{i}$, each connected
to $u_{i}^{1},\dots,u_{i}^{6}$. Then for each variable $x_{j}$, we create 2
vertices $v_{j}$ and $v^{\prime}_{j}$ (corresponding to the literals $x_{j}$
and $\overline{x}_{j}$ respectively) connected by an edge. For each variable
$x_{j}$, add an edge from $v_{j}$ to each of $u_{i}^{1},\dots,u_{i}^{6}$ for
each clause $c_{i}$ which contains $x_{j}$ as a literal. Likewise, add an edge
from $v^{\prime}_{j}$ to each of $u_{i}^{1},\dots,u_{i}^{6}$ for each clause
$c_{i}$ which contains $\overline{x}_{j}$ as a literal.

$u_{1}^{1}$$\dots$$u_{1}^{6}$$u_{2}^{1}$$\dots$$u_{2}^{6}$$v_{2}$$v^{\prime}_{2}$$v_{1}$$v^{\prime}_{1}$$v_{3}$$v^{\prime}_{3}$$v_{4}$$v^{\prime}_{4}$$f_{2}$$f^{\prime}_{2}$
Figure 2:  The subgraph of $G(\varphi)$ corresponding to the clauses
$c_{1}=(x_{1}\lor x_{2}\lor x_{3})$ and $c_{2}=(\overline{x}_{3}\lor x_{4})$.

See Figure 2 for an example of $G(\varphi)$. In the conversion between orders
and assignments, the relative position of $v_{j}$ and $v^{\prime}_{j}$
corresponds to the assignment of $x_{j}$. If $v_{j}$ appears first, then
$x_{j}$ is set to false, and if instead $v^{\prime}_{j}$ appears first, then
$x_{j}$ is set to true. Thus, a clause vertex $u_{i}^{\ell}$ (which must
appear at the beginning of the order) has 2-reach equal to 6 only if $c_{i}$
contains 3 false literals in the converted assignment. We prove that $\varphi$
is satisfiable if and only if $\operatorname{wcol}_{2}(G(\varphi))\leq 5$. The
forward direction uses a satisfying assignment of $\varphi$ to construct an
order on $G(\varphi)$ with weak 2-reach at most 5.

######  Lemma 3.2.

Let $\varphi$ be an instance of 2-Clause 3-SAT and let $G(\varphi)$ be the
graph produced by Definition 3.1. If $\varphi$ is satisfiable, then
$\operatorname{wcol}_{2}(G(\varphi))\leq 5$.

###### Proof.

Let $G=G(\varphi)$, and let $A$ be an assignment of $x_{1},\dots,x_{n}$
witnessing that $\varphi$ is satisfiable. Construct the total order $\sigma$
in the following manner. First, for each clause $c_{i}$, add
$u_{i}^{1},\dots,u_{i}^{6}$ to $\sigma$ in that order. If $c_{i}$ only
contains 2 literals, place $f_{i}$ and $f^{\prime}_{i}$ immediately after
$u_{i}^{6}$. Then, for each variable $x_{j}$, add $v^{\prime}_{j}$ and then
$v_{j}$ if $x_{j}$ is true in $A$. Otherwise, add $v_{j}$ and then
$v^{\prime}_{j}$.

Consider $\operatorname{W}_{2}(u_{i}^{\ell},G_{\sigma})$, and suppose that
$c_{i}$ contains 3 literals. Since $u_{i}^{\ell}$ only has edges to literal
vertices (of the form $v_{j}$ or $v^{\prime}_{j}$) and
$v_{j},v^{\prime}_{j}>_{\sigma}u_{p}^{q}$ for any $j$, it cannot reach any
other $u_{p}^{q}$ (even if $p=i$). Thus,
$|\operatorname{W}_{2}(u_{i}^{\ell},G_{\sigma})|\leq 6$ since there are only 6
vertices (corresponding to the 3 literals in the clause and their negations)
remaining in its 2-neighborhood. This still holds if $c_{i}$ only contains 2
literals, since $f_{i},f^{\prime}_{i}>_{\sigma}u_{i}^{6}$ and neither $f_{i}$
nor $f^{\prime}_{i}$ have edges outside of the clause. Since $A$ is a
satisfying assignment, at least one literal in $c_{i}$ must be set to true.
Without loss of generality, assume $x_{j}\in c_{i}$ and $x_{j}$ is true. Thus,
$v_{j}$ appears after $v^{\prime}_{j}$ by the definition of $\sigma$. Then
$v^{\prime}_{j}\not\in\operatorname{W}_{2}(u_{i}^{\ell},G_{\sigma})$, and so
$|\operatorname{W}_{2}(u_{i}^{\ell},G_{\sigma})|\leq 5$.

Next, consider $\operatorname{W}_{2}(f_{i},G_{\sigma})$. Since
$u_{i}^{\ell}<_{\sigma}f_{i}$, $f_{i}$ can only reach $f^{\prime}_{i}$ and
vertices corresponding to literals in $c_{i}$. Thus,
$|\operatorname{W}_{2}(f_{i},G_{\sigma})|=3$ and similarly
$|\operatorname{W}_{2}(f^{\prime}_{i},G_{\sigma})|=2$.

Finally, consider $\operatorname{W}_{2}(v_{j},G_{\sigma})$. Since
$u_{i}^{\ell}<_{\sigma}v_{j}$ and $f_{i}<_{\sigma}v_{j}$, $v_{j}$ can only
reach other vertices corresponding to literals. If $x_{j}$ is false in $A$,
then $v^{\prime}_{j}$ is weakly 2-reachable from $v_{j}$. The only other
vertices in the 2-neighborhood of $v_{j}$ are the other literals in the
clauses which contain $x_{j}$. Since $\varphi$ is an instance of 2-Clause
3-SAT, there are only 4 of these. Thus,
$|\operatorname{W}_{2}(v_{j},G_{\sigma})|\leq 5$. The argument is symmetric
for $v^{\prime}_{j}$. Since the weak 2-reach of every vertex is at most $5$,
$\operatorname{wcol}_{2}(G_{\sigma})\leq 5$. ∎

To complete the proof, the reverse direction argues that the assignment
implied by an order $\sigma$ either satisfies $\varphi$, or there exists a
subset of vertices (corresponding to an unsatisfied clause) which cannot have
weak 2-reach at most 5 in $\sigma$.

######  Lemma 3.3.

Let $\varphi$ be an instance of 2-Clause 3-SAT and let $G(\varphi)$ be the
graph produced by Definition 3.1. If $\operatorname{wcol}_{2}(G(\varphi))\leq
5$, then $\varphi$ has a satisfying assignment.

###### Proof.

Let $G=G(\varphi)$, and let $\sigma$ be a total order of $G$ witnessing that
$\operatorname{wcol}_{2}(G_{\sigma})\leq 5$. Let $A$ be the following
assignment of $x_{1},\dots,x_{n}$: if $v_{j}<_{\sigma}v^{\prime}_{j}$, set
$x_{j}$ to false in $A$; otherwise, set $x_{j}$ to true. Assume that $A$ does
not satisfy $\varphi$ to produce a contradiction.

Let $c_{i}$ be a clause in $\varphi$ which is not satisfied by $A$. First,
suppose that $c_{i}$ contains 3 literals. Without loss of generality, let
$c_{i}=(x_{1}\lor x_{2}\lor x_{3})$. Since $c_{i}$ is not satisfied by $A$,
$v_{1}<_{\sigma}v^{\prime}_{1}$, $v_{2}<_{\sigma}v^{\prime}_{2}$, and
$v_{3}<_{\sigma}v^{\prime}_{3}$ by construction. Let $u_{i}^{\ell}$ be the
vertex from $u_{i}^{1},\dots,u_{i}^{6}$ which appears first in $\sigma$. If
$u_{i}^{\ell}<_{\sigma}v_{1},v_{2},v_{3}$, then
$|\operatorname{W}_{2}(u_{i}^{\ell},G_{\sigma})|\geq 6$ since it can reach
$v_{1}$, $v_{2}$, $v_{3}$, $v^{\prime}_{1}$, $v^{\prime}_{2}$, and
$v^{\prime}_{3}$. This contradicts that
$\operatorname{wcol}_{2}(G_{\sigma})\leq 5$, and so we may assume that at
least one of $v_{1}$, $v_{2}$, or $v_{3}$ appears before $u_{i}^{\ell}$ in
$\sigma$. Without loss of generality, assume $v_{1}<_{\sigma}u_{i}^{\ell}$. By
our choice of $u_{i}^{\ell}$ though, $v_{1}$ can reach all of
$u_{i}^{1},\dots,u_{i}^{6}$. Thus,
$|\operatorname{W}_{2}(v_{1},G_{\sigma})|\geq 6$. This again contradicts that
$\operatorname{wcol}_{2}(G_{\sigma})\leq 5$.

If instead $c_{i}$ only contains 2 literals, then $u_{i}^{\ell}$ reaches
$f_{i}$ and $f^{\prime}_{i}$ rather than $v_{3}$ and $v^{\prime}_{3}$. Like
$v_{1}$ and $v_{2}$, $f_{i}$ and $f^{\prime}_{i}$ cannot come before
$u_{i}^{\ell}$ without reaching all of $u_{i}^{1},\dots,u_{i}^{6}$,
contradicting that $\operatorname{wcol}_{2}(G_{\sigma})\leq 5$. Therefore, $A$
must be a satisfying assignment for $\varphi$. ∎

Together, Lemmas 3.2 and 3.3 show that determining if
$\operatorname{wcol}_{2}(G)\leq 5$ is NP-hard. Since 5 is a constant, this
proves the main result.

######  Theorem 3.4.

Weak 2-Orderable parameterized by the natural parameter $k$ is para-NP-hard.

###### Proof.

Lemmas 3.2 and 3.3 imply that determining if $\operatorname{wcol}_{2}(G)\leq
k$ is NP-hard even when $k=5$. ∎

######  Corollary 3.5.

It is NP-hard to approximate Minimum Weak 2-Orderability within a factor of
$\frac{6}{5}$.

######  Corollary 3.6.

There does not exist an algorithm which can decide a given instance $(G,k)$ of
Weak 2-Orderable in $O(n^{f(k)})$ time unless P $=$ NP. Thus, Weak 2-Orderable
is not in XP.

###  3.2 Weak $r$-Orderable is Para-NP-hard

Having established the para-NP-hardness of the weak 2-coloring number, we now
turn our attention to the weak $r$-coloring number for $r\geq 3$. The
construction is similar to the weak 2-coloring number, but includes subdivided
edges to increase the distance between vertices. An $\ell$-subdivided edge
(alternatively: an edge subdivided $\ell$ times) is an induced path with
$\ell$ internal vertices connecting the endpoints of the edge. The vertices
along the subdivided edge do not have additional neighbors outside of the
path. Note that a 0-subdivided edge is simply a normal edge. We refer
collectively to the vertices along the subdivided edges as _subdivision
vertices_. Additional modifications handle the non-constant reach of vertices
along subdivided edges. One key adaptation is that we now reduce from Exact
$r$-SAT.

######  Definition 3.7.

Given an instance $\varphi$ of Exact $r$-SAT, let $G(\varphi)$ be the
following graph. For each clause $c_{i}\in\varphi$, we create $2r$ vertices
$u_{i}^{1},\dots,u_{i}^{2r}$ in $G(\varphi)$. Then for each variable $x_{j}$,
we create 2 vertices $v_{j}$ and $v^{\prime}_{j}$ (corresponding to the
literals $x_{j}$ and $\overline{x}_{j}$ respectively) connected by an edge.
For each variable $x_{j}$, add two $(r-2)$-subdivided edges from $v_{j}$ to
each of $u_{i}^{1},\dots,u_{i}^{2r}$ for each clause $c_{i}$ which contains
$x_{j}$ as a literal. Likewise, add two $(r-2)$-subdivided edges from
$v^{\prime}_{j}$ to each of $u_{i}^{1},\dots,u_{i}^{2r}$ for each clause
$c_{i}$ which contains $\overline{x}_{j}$ as a literal.

$\dots$$u_{1}^{1}$$u_{1}^{2r}$$\dots$$u_{2}^{1}$$u_{2}^{2r}$$v_{2}$$v^{\prime}_{2}$$v_{1}$$v^{\prime}_{1}$$v_{3}$$v^{\prime}_{3}$$v_{4}$$v^{\prime}_{4}$$v_{5}$$v^{\prime}_{5}$
Figure 3:  The subgraph of $G(\varphi)$ corresponding to the 3-SAT clauses
$c_{1}=(x_{1}\lor x_{2}\lor x_{3})$ and $c_{2}=(\overline{x}_{3}\lor
x_{4}\lor\overline{x}_{5})$. The dashed edges represent $(r-2)$-subdivided
edges between $u_{i}^{\ell}$ and $v_{j}$ (or $v^{\prime}_{j}$).

See Figure 3 for an example of $G(\varphi)$. Like the weak 2-coloring number
reduction, the conversion between orders and assignments conflates the
relative position of $v_{j}$ and $v^{\prime}_{j}$ with the assignment of
$x_{j}$. If $v_{j}$ appears first, then $x_{j}$ is set to false, and if
instead $v^{\prime}_{j}$ appears first, then $x_{j}$ is set to true. Thus, a
clause vertex $u_{i}^{\ell}$ (which still must appear at the beginning of the
order) has $r$-reach equal to $2r$ only if $c_{i}$ contains $r$ false literals
in the converted assignment. We prove that $\varphi$ is satisfiable if and
only if $\operatorname{wcol}_{r}(G(\varphi))\leq 2r-1$. The forward direction
uses a satisfying assignment of $\varphi$ to construct an order on
$G(\varphi)$ with weak $r$-reach at most $2r-1$.

######  Lemma 3.8.

Let $\varphi$ be an instance of Exact $r$-SAT and let $G(\varphi)$ be the
graph produced by Definition 3.7. If $\varphi$ is satisfiable, then
$\operatorname{wcol}_{r}(G(\varphi))\leq 2r-1$.

###### Proof.

Let $G=G(\varphi)$, and let $A$ be an assignment of $x_{1},\dots,x_{n}$
witnessing that $\varphi$ is satisfiable. Construct the total order $\sigma$
in the following manner. First, place the subdivision vertices in any order.
For each clause $c_{i}$, add $u_{i}^{1},\dots,u_{i}^{2r}$ to $\sigma$ in that
order. Then, for each variable $x_{j}$, add $v^{\prime}_{j}$ and then $v_{j}$
if $x_{j}$ is true in $A$. Otherwise, add $v_{j}$ and then $v^{\prime}_{j}$.

Consider a subdivision vertex $s$ along a subdivided edge between
$u_{i}^{\ell}$ and $v_{j}$. Depending on the order, $s$ may be able to reach
the other $r-3$ vertices along its subdivided edge. However, it cannot reach a
subdivision vertex on a different subdivided edge since that would require
going through $u_{i}^{\ell}$ or $v_{j}$, both of which appear after all
subdivision vertices. The $r$-reach of $s$ contains only $u_{i}^{\ell}$ and no
other clause vertices since it cannot use $v_{j}$ which appears after all
clause vertices in $\sigma$. Finally, $s$ can reach $v_{j}$ and
$v^{\prime}_{j}$. If $s$ is adjacent to $u_{i}^{\ell}$, it can reach the $r-1$
vertices corresponding to the other literals in $c_{i}$. In total then,
$|\operatorname{W}_{r}(s,G_{\sigma})|\leq 2r-1$.

Next, consider $\operatorname{W}_{r}(u_{i}^{\ell},G_{\sigma})$. Since edges
between clause vertices and literal vertices are subdivided $r-2$ times and
$r\geq 3$, the distance between $u_{i}^{\ell}$ and $u_{p}^{q}$ is greater than
$r$ (even if $p=i$). Thus,
$|\operatorname{W}_{r}(u_{i}^{\ell},G_{\sigma})|\leq 2r$ since there are only
$2r$ vertices (corresponding to the $r$ literals in the clause and their
negations) remaining in its $r$-neighborhood. Since $A$ is a satisfying
assignment, at least one literal in $c_{i}$ must be set to true. Without loss
of generality, assume $x_{j}\in c_{i}$ and $x_{j}$ is true. Thus, $v_{j}$
appears after $v^{\prime}_{j}$ by the definition of $\sigma$. Then
$v^{\prime}_{j}\not\in\operatorname{W}_{r}(u_{i}^{\ell},G_{\sigma})$, and so
$|\operatorname{W}_{r}(u_{i}^{\ell},G_{\sigma})|\leq 2r-1$.

Finally, $|\operatorname{W}_{r}(v_{j},G_{\sigma})|\leq 1$. Although $v_{j}$
can reach $v^{\prime}_{j}$ (or vice versa), every other vertex corresponding
to a literal is at least distance $r+1$ away. Since the weak $r$-reach of
every vertex is at most $2r-1$, $\operatorname{wcol}_{r}(G_{\sigma})\leq
2r-1$. ∎

To complete the proof, the reverse direction argues that the assignment
implied by an order $\sigma$ either satisfies $\varphi$, or there exists a
subset of vertices (corresponding to an unsatisfied clause) which cannot have
weak $r$-reach at most $2r-1$ in $\sigma$.

######  Lemma 3.9.

Let $\varphi$ be an instance of Exact $r$-SAT and let $G(\varphi)$ be the
graph produced by Definition 3.7. If $\operatorname{wcol}_{r}(G(\varphi))\leq
2r-1$, then $\varphi$ has a satisfying assignment.

###### Proof.

Let $G=G(\varphi)$, and let $\sigma$ be a total order of $G$ witnessing that
$\operatorname{wcol}_{r}(G_{\sigma})\leq 2r-1$. Let $A$ be the following
assignment of $x_{1},\dots,x_{n}$: if $v_{j}<_{\sigma}v^{\prime}_{j}$, set
$x_{j}$ to false in $A$; otherwise, set $x_{j}$ to true. Assume that $A$ does
not satisfy $\varphi$ to produce a contradiction.

Let $c_{i}$ be a clause in $\varphi$ which is not satisfied by $A$. Without
loss of generality, let $c_{i}=(x_{1}\lor\dots\lor x_{r})$. Since $c_{i}$ is
not satisfied by $A$, $v_{j}<_{\sigma}v^{\prime}_{j}$ for $1\leq j\leq r$. Let
$u_{i}^{\ell}$ be the vertex from $u_{i}^{1},\dots,u_{i}^{2r}$ which appears
first in $\sigma$. If $u_{i}^{\ell}<_{\sigma}v_{1},\dots,v_{r}$, then
$|\operatorname{W}_{r}(u_{i}^{\ell},G_{\sigma})|\geq 2r$ since it can reach
$v_{1},\dots v_{r}$ and $v^{\prime}_{1},\dots,v^{\prime}_{r}$. Reaching
$v_{j}$ and $v^{\prime}_{j}$ can only be avoided by placing a subdivision
vertex $s$ from the subdivided edge between $u_{i}^{\ell}$ and $v_{j}$ after
$v^{\prime}_{j}$ in $\sigma$. However, since there are 2 subdivided edges
between $u_{i}^{\ell}$ and $v_{j}$, this results in the same total reach. This
contradicts that $\operatorname{wcol}_{r}(G_{\sigma})\leq 2r-1$, and so we may
assume that at least one of $v_{1},\dots,v_{r}$ appears before $u_{i}^{\ell}$
in $\sigma$. Without loss of generality, assume $v_{1}<_{\sigma}u_{i}^{\ell}$.
By our choice of $u_{i}^{\ell}$, $v_{1}$ can reach all of
$u_{i}^{1},\dots,u_{i}^{2r}$. Again, this can be avoided by placing 2
subdivision vertices after $u_{i}^{\ell}$ in $\sigma$, but this yields an even
larger reach. Thus, $|\operatorname{W}_{r}(v_{1},G_{\sigma})|\geq 2r$. This
again contradicts that $\operatorname{wcol}_{r}(G_{\sigma})\leq 2r-1$.
Therefore, $A$ must be a satisfying assignment for $\varphi$. ∎

Together, Lemmas 3.8 and 3.9 show that determining
$\operatorname{wcol}_{r}(G)\leq 2r-1$ is NP-hard. Since $2r-1$ is assumed to
be a constant, this proves the main result.

######  Theorem 3.10.

Weak $r$-Orderable parameterized by the natural parameter $k$ is para-NP-hard.

###### Proof.

Lemmas 3.8 and 3.9 imply that determining if $\operatorname{wcol}_{r}(G)\leq
k$ is NP-hard even when $k=2r-1$. ∎

######  Corollary 3.11.

It is NP-hard to approximate Minimum Weak $r$-Orderability within a factor of
$\frac{2r}{2r-1}$.

######  Corollary 3.12.

For any fixed $r$, there does not exist an algorithm which can decide a given
instance $(G,k)$ of Weak $r$-Orderable in $O(n^{f(k)})$ time unless P = NP.
Thus, Weak $r$-Orderable is not in XP.

###  3.3 $r$-Orderable is Para-NP-Hard

Finally, we prove that $r$-Orderable parameterized by the natural parameter
$k$ is para-NP-hard. Our proof reduces from 2-Clause 3-SAT and shows that
determining if $\operatorname{col}_{r}(G)\leq 6$ is NP-hard. First, we
describe the reduction from the 2-Clause 3-SAT instance $\varphi$ to the graph
$G(\varphi)$.

######  Definition 3.13.

Given an instance $\varphi$ of 2-Clause 3-SAT, let $G(\varphi)$ be the
following graph. For each clause $c_{i}\in\varphi$, create a _clause vertex_
$u_{i}$ in $G(\varphi)$. For each variable $x_{j}$, create 2 _literal
vertices_ $v_{j}$ and $v^{\prime}_{j}$ (corresponding to the literals $x_{j}$
and $\overline{x}_{j}$ respectively) and connect them by an edge.
Additionally, for each clause $c_{i}$ which contains the literal $x_{j}$ (or
$\overline{x}_{j}$), connect $u_{i}$ and $v_{j}$ (or $v^{\prime}_{j}$) with an
$(r-1)$-subdivided edge. To complete $G(\varphi)$, create a 7-clique
consisting of the _clique vertices_ $w_{1},\dots,w_{7}$, and connect it to the
remainder of the graph in the following manner. For every clause $c_{i}$, add
edges from $u_{i}$ to $w_{1},\dots,w_{4}$. If $c_{i}$ only contains 2
literals, add an additional edge from $u_{i}$ to $w_{5}$. For every variable
$x_{j}$, add edges from $v_{j}$ to $w_{2},\dots,w_{4}$ and from
$v^{\prime}_{j}$ to $w_{5},\dots,w_{7}$.

Figure 4 gives an example of $G(\varphi)$ for a small 2-Clause 3-SAT instance.
In the conversion between orders and assignments, the relative position of
$v_{j}$ and $v^{\prime}_{j}$ corresponds to the assignment of $x_{j}$. If
$v_{j}$ appears first, then $x_{j}$ is set to true, and if instead
$v^{\prime}_{j}$ appears first, then $x_{j}$ is set to false. Informally, the
reduction works by forcing the clause vertices to appear between the true and
false literal vertices in optimal orders. As a result, a clause vertex has
reach 7 unless it is satisfied (3 false literal vertices plus 4 clique
vertices). Formally, we prove that $\varphi$ is satisfiable if and only if
$\operatorname{col}_{r}(G(\varphi))\leq 6$. The forward direction uses a
satisfying assignment of $\varphi$ to construct an order on $G(\varphi)$ with
$r$-reach at most 6.

$u_{1}$$w_{1},\dots,w_{7}$$v^{\prime}_{1},v^{\prime}_{2},v^{\prime}_{3}$$v_{1},v_{2},v_{3}$
Figure 4:  The subgraph of $G(\varphi)$ corresponding to the clause
$c_{1}=(x_{1}\lor x_{2}\lor x_{3})$. The dashed edges represent
$(r-1)$-subdivided edges between clause vertices and literal vertices. The
bold edges indicate that every possible edge is present between the two sets.

######  Lemma 3.14.

Let $\varphi$ be an instance of 2-Clause 3-SAT, and let $G(\varphi)$ be the
graph defined by Definition 3.13. If $\varphi$ is satisfiable, then
$\operatorname{col}_{r}(G(\varphi))\leq 6$.

###### Proof.

Let $G=G(\varphi)$, and let $A$ be an assignment of $x_{1},\dots,x_{n}$
satisfying $\varphi$. Construct the total order $\sigma$ in the following
manner. First, place the subdivision vertices at the beginning of $\sigma$.
Then for each literal $x_{j}$ (or $\overline{x}_{j}$) which is true in $A$,
add $v_{j}$ (or $v^{\prime}_{j}$) to $\sigma$. Next, add $u_{i}$ to $\sigma$
for each clause $c_{i}$. Finally, add the remaining vertices corresponding to
false literals in $A$ and then $w_{1},\dots,w_{7}$ to the end of $\sigma$.

First, we note that the subdivision vertices all have reach 2 since they only
reach a single vertex in either direction along the subdivided edge. Consider
$\operatorname{R}_{r}(v_{j},G_{\sigma})$ where $v_{j}$ corresponds to a true
literal $x_{j}$ in $A$. In this case, $v_{j}$ reaches $v^{\prime}_{j}$, both
vertices corresponding to the clauses containing $x_{j}$, and 3 clique
vertices for a total of 6. Since every path leaving $v_{j}$ goes through one
of these vertices before any others (not counting subdivision vertices),
$v_{j}$ cannot reach anything else. Thus,
$|\operatorname{R}_{r}(v_{j},G_{\sigma})|\leq 6$ when $x_{j}$ is true in $A$.
The argument is symmetric for $v^{\prime}_{j}$ when $\overline{x}_{j}$ is true
in $A$.

Next, consider $\operatorname{R}_{r}(u_{i},G_{\sigma})$. Since $u_{i}$ is
connected to literal vertices using $(r-1)$-subdivided edges, $u_{i}$ does not
have any qualifying paths which go through a true literal vertex. As a result,
$u_{i}$ reaches $w_{1},\dots,w_{4}$ and at most 2 false literal vertices since
$A$ satisfies $\varphi$. If $c_{i}$ only contains 2 literals, then $u_{i}$
also reaches $w_{5}$, but it can only reach a single false literal vertex.
Thus, $|\operatorname{R}_{r}(u_{i},G_{\sigma})|\leq 6$.

Finally, consider $\operatorname{R}_{r}(v_{j},G_{\sigma})$, but now suppose
$x_{j}$ is false in $A$. Every path from $v_{j}$ to another false literal
vertex which does not go through a clique vertex has length greater than $r$.
Thus, $v_{j}$ can only reach $w_{2},\dots,w_{7}$ (either directly or through
$v^{\prime}_{j}$), and $|\operatorname{R}_{r}(v_{j},G_{\sigma})|\leq 6$ when
$x_{j}$ is false in $A$. The argument is symmetric for $v^{\prime}_{j}$ when
$\overline{x}_{j}$ is false in $A$. The 7 clique vertices trivially have reach
at most 6 since no other vertices appear after them in $\sigma$. Because every
vertex has bounded reach with respect to $\sigma$,
$\operatorname{col}_{r}(G_{\sigma})\leq 6$. ∎

To complete the proof, the reverse direction argues that the assignment
implied by an order $\sigma$ either satisfies $\varphi$, or there exists a
subset of vertices (corresponding to an unsatisfied clause) which cannot be
ordered with $r$-reach at most 6.

######  Lemma 3.15.

Let $\varphi$ be an instance of 2-Clause 3-SAT, and let $G(\varphi)$ be the
graph defined by Definition 3.13. If $\operatorname{col}_{r}(G(\varphi))\leq
6$, then $\varphi$ has a satisfying assignment.

###### Proof.

Let $G=G(\varphi)$, and let $\sigma$ be a total order of $G$ such that
$\operatorname{col}_{r}(G_{\sigma})\leq 6$. Let $A$ be the following
assignment of $x_{1},\dots,x_{n}$: if $v_{j}<_{\sigma}v^{\prime}_{j}$, set
$x_{j}$ to true in $A$; otherwise, set $x_{j}$ to false. Assume that $A$ does
not satisfy $\varphi$ to produce a contradiction.

Let $c_{i}$ be a clause in $\varphi$ which is not satisfied by $A$. Without
loss of generality, let $v_{j}$ be the first vertex in $\sigma$ such that
$x_{j}\in c_{i}$. Since $c_{i}$ is not satisfied by $A$,
$v^{\prime}_{j}<_{\sigma}v_{j}$. Let $w_{\ell}$ be the vertex from
$w_{1},\dots,w_{7}$ which appears first in $\sigma$. We argue that the first
vertex among $u_{i}$, $v_{j}$, and $w_{\ell}$ to appear in $\sigma$ must have
$r$-reach at least 7.

First, suppose $w_{\ell}<_{\sigma}u_{i},v_{j}$. By our choice of $w_{\ell}$,
$w_{\ell}$ reaches the other 6 clique vertices. If $\ell\leq 4$, then
$w_{\ell}$ also reaches $u_{i}$, so we may assume $\ell>4$. However, in this
case, $w_{\ell}$ reaches $v^{\prime}_{j}$ if
$w_{\ell}<_{\sigma}v^{\prime}_{j}$, or it reaches $v_{j}$ if
$w_{\ell}>_{\sigma}v^{\prime}_{j}$. Thus,
$|\operatorname{R}_{r}(w_{\ell},G_{\sigma})|>6$. Suppose instead that
$u_{i}<_{\sigma}v_{j},w_{\ell}$. By our choice of $w_{\ell}$, $u_{i}$ must
reach $w_{1},\dots,w_{4}$. Moreover, by our choice of $v_{j}$, $u_{i}$ must
reach each vertex corresponding to one of the 3 literals in $c_{i}$ (or a
vertex along the subdivided edge) for a total of 7. This is not improved if
$c_{i}$ only contains 2 literals since then $u_{i}$ also reaches $w_{5}$.
Thus, $|\operatorname{R}_{r}(u_{i},G_{\sigma})|>6$. Finally, suppose that
$v_{j}<_{\sigma}u_{i},w_{\ell}$. In this case, $v_{j}$ reaches $u_{i}$ as well
as $w_{2},\dots,w_{7}$ since $v^{\prime}_{j}<_{\sigma}v_{j}$. Thus,
$|\operatorname{R}_{r}(v_{j},G_{\sigma})|>6$. Since one of these vertices must
appear before the others, $\operatorname{col}_{r}(G_{\sigma})$ cannot be at
most 6. ∎

Together, Lemmas 3.14 and 3.15 show that determining
$\operatorname{col}_{r}(G)\leq 6$ is NP-hard. Since 6 is a constant, this
proves the main result.

######  Theorem 3.16.

When parameterized by the natural parameter $k$, $r$-Orderable is para-NP-
hard.

###### Proof.

Lemmas 3.14 and 3.15 imply that determining if $\operatorname{col}_{r}(G)\leq
k$ is NP-hard even when $k=6$. ∎

######  Corollary 3.17.

It is NP-hard to approximate Minimum $r$-Orderability within a factor of
$\frac{7}{6}$.

######  Corollary 3.18.

There does not exist an algorithm which can decide a given instance $(G,k)$ of
$r$-Orderable in $O(n^{f(k)})$ time unless P = NP. Thus, $r$-Orderable is not
in XP.

##  4 Approximating the Generalized Coloring Numbers

In this section, we prove that a straightforward greedy algorithm for Minimum
$r$-Orderability gives a $(k-1)^{r-1}$-approximation in graphs with
$r$-admissibility at most $k$. We establish that the same algorithm also gives
an $O(k^{r-1})$-approximation for Minimum Weak $r$-Orderability. Our analysis
relies on properties of $r$-admissibility and its relationships with the
$r$-coloring number and the weak $r$-coloring number.

######  Definition 4.1.

Given a graph $G=(V,E)$ and a prefix order $\sigma$, the $r$-backconnectivity
$\operatorname{B}_{r}(u,G_{\sigma})$ of a vertex $u\in V$ is the maximum
number of vertex-disjoint (aside from $u$) $r$-qualifying paths beginning at
$u$. The $r$-admissibility of $G$ is defined as

$\operatorname{adm}_{r}(G):=\min_{\sigma\in\Pi}\max_{u\in V}\
\operatorname{B}_{r}(u,G_{\sigma}).$

We note again that this definition adheres to a left-to-right convention,
reversing the direction used in prior work. Unlike
$\operatorname{R}_{r}(u,G_{\sigma})$ and $\operatorname{W}_{r}(u,G_{\sigma})$
which are sets, notice that $\operatorname{B}_{r}(u,G_{\sigma})$ is simply a
non-negative integer, and a set of disjoint paths witnessing
$\operatorname{B}_{r}(u,G_{\sigma})$ need not be unique. By definition,
$\operatorname{adm}_{r}(G_{\sigma})\leq\operatorname{col}_{r}(G_{\sigma})\leq\operatorname{wcol}_{r}(G_{\sigma})$.
In [3], Dvořák observed that bounds also hold in the opposite direction.

######  Lemma 4.2.

[3] If $\operatorname{adm}_{r}(G_{\sigma})\leq k$, then
$\operatorname{col}_{r}(G_{\sigma})\leq k\cdot(k-1)^{r-1}$ and
$\operatorname{wcol}_{r}(G_{\sigma})\leq\frac{k^{r+1}-1}{k-1}$.

Computing the $r$-backconnectivity of a vertex is NP-hard [7], and so Dvořák’s
algorithm for the generalized coloring numbers approximates the
$r$-admissibility before applying these relationships. This approach yields an
$(r\cdot(rk-1)^{r-1})$-approximation for the $r$-coloring number and an
$O((rk)^{r-1})$-approximation for the weak $r$-coloring number. We show that
the approximation factors can be improved to $(k-1)^{r-1}$ and $O(k^{r-1})$
respectively by applying a similar analysis directly to a greedy algorithm.
The greedy algorithm we use generalizes the strategy used to compute
degeneracy and constructs an order $\sigma$ by repeatedly selecting the vertex
with the smallest _estimated_ $r$-backconnectivity.

######  Definition 4.3.

Given a graph $G=(V,E)$ and a prefix order $\sigma$, an $\ell$-qualifying
$u$-$v$ path is _shortest_ if there does not exist an $(\ell-1)$-qualifying
$u$-$v$ path. The estimated $r$-backconnectivity of $u$, denoted
$\operatorname{est}_{r}(u,G_{\sigma})$, is the maximum number of disjoint
(aside from $u$) shortest $r$-qualifying paths.

Clearly,
$\operatorname{est}_{r}(u,G_{\sigma})\leq\operatorname{B}_{r}(u,G_{\sigma})$
since any paths $P_{1},\dots,P_{\ell}$ witnessing that
$\operatorname{est}_{r}(u,G_{\sigma})\geq\ell$ also witness that
$\operatorname{B}_{r}(u,G_{\sigma})\geq\ell$. The estimated
$r$-backconnectivity of $u$ can be computed in $O(kn)$ time by computing a
maximum flow in a directed acyclic graph derived from the level graph rooted
at $u$. Since every source-sink path in this graph is necessarily shortest and
has length at most $r$ by construction, flow techniques work in this setting
even though they fail for general $r$-backconnectivity (where the maximum flow
can exceed $\operatorname{B}_{r}(u,G_{\sigma})$ by using a path with length
greater than $r$).

input : a graph $G$ with $\operatorname{adm}_{r}(G)=k$ and an integer $r>0$.

output : a total order $\sigma$ with $\operatorname{col}_{r}(G_{\sigma})\leq
k\cdot(k-1)^{r-1}$ and
$\operatorname{wcol}_{r}(G_{\sigma})\leq\frac{k^{r+1}-1}{k-1}$.

1 $S\leftarrow\\{u:\deg(u)\ |\ u\in V(G)\\}$

2 $\sigma\leftarrow[\emptyset]$

3 while  _$S$ is not empty_ do

4

5 $u\leftarrow$ arg min $S$

6 append $u$ to $\sigma$ and remove $u$ from $S$

7 for  _$v$ in $\operatorname{R}_{r}(u,G_{\sigma})$_ do

8 $S[v]=\operatorname{est}_{r}(v,G_{\sigma})$

return _$\sigma$_

Algorithm 1 BoundedColoring($G,r$)

Algorithm 1 describes our approach in detail. At each step, the algorithm
selects the vertex with minimum estimated $r$-backconnectivity in constant
time using a bucket queue. Then, the algorithm updates the estimated
$r$-backconnectivity for each vertex that may have been affected by ordering
$u$. Since these are exactly the vertices in
$\operatorname{R}_{r}(u,G_{\sigma})$, Algorithm 1 takes $O(tkn^{2})$ time in
total when $\operatorname{col}_{r}(G_{\sigma})=t$. To prove the correctness of
Algorithm 1, we first show that for any prefix order, there exists an
unordered vertex with small backconnectivity.

######  Lemma 4.4.

Given a graph $G=(V,E)$ and a prefix order $\sigma$, there exists an unordered
vertex $u$ with respect to $\sigma$ such that
$\operatorname{B}_{r}(u,G_{\sigma})\leq\operatorname{adm}_{r}(G)=k$.

###### Proof.

Let $\xi=(v_{1},\dots,v_{n})$ be a total order of $G$ such that
$\operatorname{adm}_{r}(G_{\xi})=k$, and let $v_{i}$ be the first vertex in
$\xi$ which is unordered in $\sigma$. By our choice of $v_{i}$,
$\\{v_{1},\dots,v_{i-1}\\}$ are ordered in $\sigma$. Let
$P_{1},\dots,P_{\ell}$ be a set of disjoint $r$-qualifying paths which witness
that $\operatorname{B}_{r}(v_{i},G_{\sigma})=\ell$. Let $P^{\prime}_{j}$ be
the subpath of $P_{j}$ beginning at $v_{i}$ and ending at the first vertex
along $P_{j}$ which is not in $\\{v_{1},\dots,v_{i-1}\\}$. Since $P_{j}$ is an
$r$-qualifying path from $v_{i}$, its endpoint must be in
$\\{v_{i+1},\dots,v_{n}\\}$, and so the path $P^{\prime}_{j}$ is well-defined.
The paths $P^{\prime}_{1},\dots,P^{\prime}_{\ell}$ witness that
$\operatorname{B}_{r}(v_{i},G_{\xi})\geq\ell$. Thus,
$\operatorname{B}_{r}(v_{i},G_{\sigma})\leq\operatorname{B}_{r}(v_{i},G_{\xi})\leq\operatorname{adm}_{r}(G_{\xi})=k$.
∎

Lemma 4.4 implies that the estimated backconnectivity of some unordered vertex
will always be at most the admissibility. Now, we prove that if the estimated
$r$-backconnectivity is small, then the $r$-reach is also bounded. To state
the result precisely, we need additional notation. Given a graph $G=(V,E)$, a
prefix order $\sigma$, and a vertex $u$, let $d_{v}(u,G_{\sigma})$ be the
minimum $i$ such that $v$ is $i$-reachable from $u$. We will abbreviate
$d_{v}(u,G_{\sigma})$ as $d_{v}$ when $u$ is clear from context.

######  Lemma 4.5.

Let $G=(V,E)$ be a graph, and let $k=\operatorname{adm}_{r}(G)$. If $\sigma$
is a total order on $V$ such that $\operatorname{est}_{r}(u,G_{\sigma})\leq k$
for all $u$, then

$\sum_{v\in\operatorname{R}_{r}(u,G_{\sigma})}(k-1)^{r-d_{v}}\leq
k\cdot(k-1)^{r-1}.$

###### Proof.

Let $T\subseteq G$ be a tree rooted at $u$ such that the internal vertices of
$T$ appear before $u$ in $\sigma$ and the leaves of $T$ at depth at most $i$
are exactly the vertices in $\operatorname{R}_{i}(u,G_{\sigma})$. Such a tree
can be constructed by combining shortest $r$-qualifying $u$-$v$ paths for
every $v\in\operatorname{R}_{r}(u,G_{\sigma})$. Suppose there exists a vertex
$v\in T$ such that $\deg_{T}(v)>k$. By the definition of $T$, the paths from
$v$ to $u$ and from $v$ to the leaves in the subtree rooted at $v$ must be
shortest and have length at most $r$. At least one vertex along each of these
paths must be reachable from $v$ since $u$ and all of the vertices in
$\operatorname{R}_{r}(u,G_{\sigma})$ appear after $v$, since
$v<_{\sigma}u<_{\sigma}w\in\operatorname{R}_{r}(u,G_{\sigma})$ by definition.
Thus, $\operatorname{est}_{r}(v,G_{\sigma})>k$, contradicting our assumption
on $\sigma$, and so the vertices of $T$ have degree at most $k$.

Let $L_{v}$ denote the set of leaves in the subtree of $T$ rooted at $v$. We
claim that for every vertex $v\neq u$ in $T$, $\sum_{w\in
L_{v}}(k-1)^{r-d_{w}}\leq(k-1)^{r-\operatorname{depth}_{T}(v)}$. Assume there
exists a vertex $v\neq u$ in $T$ such that the claim does not hold. We may
assume that $v$ is the vertex maximizing $\operatorname{depth}_{T}(v)$ out of
all such vertices. The vertex $v$ cannot be a leaf since then $L_{v}$ contains
only $v$. Since we chose $v$ to be the deepest vertex, the claim must hold for
the children of $v$. Combined with the fact that $v$ has at most $k-1$
children and $\operatorname{depth}_{T}(v)$ is exactly one less than the depth
of each child, the claim must also hold for $v$.

We can apply the same logic to the root $u$ which has at most $k$ children in
$T$, and so $\sum_{w\in L_{u}}(k-1)^{r-d_{w}}\leq k\cdot(k-1)^{r-1}$. The
construction of $T$ implies that $L_{u}=\operatorname{R}_{r}(u,G_{\sigma})$,
and so the lemma holds as desired. ∎

Since $(k-1)^{r-d_{v}}\geq 1$, this proves that
$\operatorname{col}_{r}(G_{\sigma})\leq k\cdot(k-1)^{r-1}$ as desired. To
complete the correctness proof of Algorithm 1, we only need to demonstrate the
weak $r$-coloring number bound. As noted in Dvořák’s proof of Lemma 6 in [3],
the weak $r$-coloring number bound follows directly from the bound on the
$r$-coloring number. We replicate the argument here in our notation for
convenience.

######  Observation 4.6.

[3] Given a graph $G=(V,E)$ and a total order $\sigma$, the following holds
for all $u\in V$:

$\operatorname{W}_{r}(u,G_{\sigma})=\bigcup_{v\in\operatorname{R}_{r}(u,G_{\sigma})}\\{v\\}\cup\operatorname{W}_{r-d_{v}}(v,G_{\sigma}).$

To see this, consider a weak $r$-qualifying path $P$ from $u$ to $w$. Let $v$
be the first vertex on $P$ to appear after $u$ in $\sigma$. The vertex $v$
divides $P$ into $P_{uv}$ and $P_{vw}$ so that $P_{uv}$ is an $r$-qualifying
path certifying that $v\in\operatorname{R}_{i}(u,G_{\sigma})$ and $P_{vw}$ is
a weak $r$-qualifying path certifying that
$w\in\operatorname{W}_{r-i}(v,G_{\sigma})$.

######  Lemma 4.7.

[3] Let $G=(V,E)$ be a graph, and let $\sigma$ be a total order. If for some
value of $k$,
$\sum_{v\in\operatorname{R}_{r}(u,G_{\sigma})}(k-1)^{r-d_{v}}\leq
k\cdot(k-1)^{r-1}$ for all $u\in V$, then
$|\operatorname{W}_{r}(u,G_{\sigma})|\leq\frac{k^{r+1}-1}{k-1}-1$ for all
$u\in V$.

###### Proof.

We proceed by induction on $r$. When $r=1$, the claim holds since
$\operatorname{W}_{1}(u,G_{\sigma})=\operatorname{R}_{1}(u,G_{\sigma})$ for
all $u\in V$. Assume that $r>1$ and that the claim holds for all smaller
values of $r$. By Observation 4.6,

$\displaystyle|\operatorname{W}_{r}(u,G_{\sigma})|$
$\displaystyle\leq\sum_{v\in\operatorname{R}_{r}(u,G_{\sigma})}1+|\operatorname{W}_{r-d_{v}}(v,G_{\sigma})|.$
By the inductive hypothesis, we can rewrite the sum as
$\displaystyle|\operatorname{W}_{r}(u,G_{\sigma})|$
$\displaystyle\leq\sum_{v\in\operatorname{R}_{r}(u,G_{\sigma})}\frac{k^{r-d_{v}+1}-1}{k-1}$
$\displaystyle=\sum_{v\in\operatorname{R}_{r}(u,G_{\sigma})}(k-1)^{r-d_{v}}\cdot\frac{k^{r-d_{v}+1}-1}{(k-1)^{r-d_{v}+1}}$
$\displaystyle\leq\frac{k^{r}-1}{(k-1)^{r}}\cdot\sum_{v\in\operatorname{R}_{r}(u,G_{\sigma})}(k-1)^{r-d_{v}}.$
By Lemma 4.5, we can bound the sum, giving
$\displaystyle|\operatorname{W}_{r}(u,G_{\sigma})|$
$\displaystyle\leq\frac{k^{r}-1}{(k-1)^{r}}\cdot k\cdot(k-1)^{r-1}$
$\displaystyle=\frac{k^{r+1}-k}{k-1}$
$\displaystyle=\frac{k^{r+1}-1-(k-1)}{k-1}$
$\displaystyle=\frac{k^{r+1}-1}{k-1}-1.$

∎

######  Theorem 4.8.

Given a graph $G=(V,E)$ with $\operatorname{adm}_{r}(G)=k$, Algorithm 1
produces a total order $\sigma$ such that
$\operatorname{col}_{r}(G_{\sigma})\leq k\cdot(k-1)^{r-1}$ and
$\operatorname{wcol}_{r}(G_{\sigma})\leq\frac{k^{r+1}-1}{k-1}$.

###### Proof.

By Lemma 4.4, there is always an unordered vertex with estimated
$r$-backconnectivity at most $k$ for any prefix order $\sigma$ that the
algorithm produces. Then, Lemma 4.5 shows that
$|\operatorname{R}_{r}(u,G_{\sigma})|\leq k\cdot(k-1)^{r-1}$ for all $u\in V$,
and Lemma 4.7 extends this to show
$|\operatorname{W}_{r}(u,G_{\sigma})|\leq\frac{k^{r+1}-1}{k-1}$ for all $u\in
V$. Thus, $\operatorname{col}_{r}(G_{\sigma})\leq k\cdot(k-1)^{r-1}$ and
$\operatorname{wcol}_{r}(G_{\sigma})\leq\frac{k^{r+1}-1}{k-1}$. ∎

##  5 Conclusion

In this paper, we considered the hardness and approximability of the
generalized coloring numbers. These parameters characterize bounded expansion
classes and have recently been the basis for new FPT algorithms. We prove that
the $r$-coloring number and the weak $r$-coloring number are both para-NP-hard
to compute for $r\geq 2$ when parameterized by the natural parameter $k$. This
implies that neither of the generalized coloring numbers admit an XP algorithm
parameterized by $k$. Moreover, our results imply that there exists a constant
$c$ such that it is NP-hard to approximate the generalized coloring numbers
within a factor of $c$. These results do not extend to the related parameters
treewidth and treedepth (equivalent to $\operatorname{col}_{n}(G)$ and
$\operatorname{wcol}_{n}(G)$ respectively) since we explicitly subdivide edges
up to $r-1$ times. We also note that our constructions require the generalized
coloring numbers to be at least 5, leaving a few open cases. Graphs with
$r$-coloring number 1 or 2 can be easily recognized (independent of $r$) since
this is equivalent to recognizing trees and series-parallel graphs
respectively. However, recognizing graphs with $r$-coloring number 3 or 4
remains open. This is an inherent limitation of 2-Clause 3-SAT and Exact
$r$-SAT, and will require a different technique to resolve.

We also give an improved approximation for the generalized coloring numbers
which runs in time $O(bkn^{2})$ where $b$ is the $r$-coloring number of the
order produced by the algorithm. The algorithm greedily selects vertices with
small estimated $r$-backconnectivity and gives a $(k-1)^{r-1}$-approximation
for the $r$-coloring number and an $O(k^{r-1})$-approximation for the weak
$r$-coloring number. Whether constant factor approximations exist for the
generalized coloring numbers remains open, even for $r=2$.

## References

  * [1] P. G. Drange, M. Dregi, F. V. Fomin, S. Kreutzer, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, F. Reidl, F. S. Villaamil, S. Saurabh, S. Siebertz, and S. Sikdar.  Kernelization and sparseness: the case of dominating set.  In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), volume 47, 2016.
  * [2] P. G. Drange, I. Muzi, and F. Reidl.  Kernelization and hardness of harmless sets in sparse classes.  CoRR, abs/2111.11834, 2021.
  * [3] Z. Dvořák.  Constant-factor approximation of the domination number in sparse graphs.  European Journal of Combinatorics, 34:833–840, 2013.
  * [4] Z. Dvořák, D. Král, and R. Thomas.  Deciding first-order properties for sparse graphs.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010.
  * [5] M. Grohe, S. Kreutzer, R. Rabinovich, S. Siebertz, and K. Stavropoulos.  Coloring and covering nowhere dense graphs.  SIAM Journal on Discrete Mathematics, 32:2467–2481, 2018.
  * [6] S. Har-Peled and K. Quanrud.  Approximation algorithms for polynomial-expansion and low-density graphs.  In Algorithms - ESA 2015, 2015.
  * [7] A. Itai, Y. Perl, and Y. Shiloach.  The complexity of finding maximum disjoint paths with length constraints.  Networks, 12:277–286, 1982.
  * [8] R. M. Karp.  Reducibility among combinatorial problems.  In Complexity of Computer Computations, pages 85–103. Springer US, 1972.
  * [9] H. A. Kierstead and D. Yang.  Orderings on graphs and game coloring number.  Order, 20:255–264, 2003.
  * [10] S. Kreutzer, I. Muzi, P. O. de Mendez, R. Rabinovich, and S. Siebertz.  Algorithmic Properties of Sparse Digraphs.  In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126, 2019.
  * [11] W. Nadara, M. Pilipczuk, R. Rabinovich, F. Reidl, and S. Siebertz.  Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness.  ACM Journal of Experimental Algorithmics, 24:1–34, 2019.
  * [12] J. Nesetril and P. O. de Mendez.  Grad and classes with bounded expansion ii. algorithmic aspects.  European Journal of Combinatorics, 2008.
  * [13] J. Nešetřil and P. O. de Mendez.  Sparsity.  Algorithms and Combinatorics. Springer Berlin Heidelberg, 2012.
  * [14] J. Nešetřil and P. Ossona de Mendez.  Grad and classes with bounded expansion i. decompositions.  European Journal of Combinatorics, 29(3), 2008.
  * [15] F. Reidl and B. D. Sullivan.  A color-avoiding approach to subgraph counting in bounded expansion classes.  Algorithmica, 85, 2023.
  * [16] F. Reidl, F. S. Villaamil, and K. S. Stavropoulos.  Characterising bounded expansion by neighbourhood complexity.  European Journal of Combinatorics, 75, 2019.
  * [17] C. A. Tovey.  A simplified NP-complete satisfiability problem.  Discrete Applied Mathematics, 8:85–89, 1984.
  * [18] X. Zhu.  Colouring graphs with bounded generalized colouring number.  Discrete Mathematics, 309:5562–5568, 2009.