# R(Det)2: Randomized Decision Routing for Object Detection

Ya-Li Li Shengjin Wang
Department of Electronic Engineering, Tsinghua University and BNRist, Beijing,
China
<EMAIL_ADDRESS>Corresponding author

###### Abstract

In the paradigm of object detection, the decision head is an important part,
which affects detection performance significantly. Yet how to design a high-
performance decision head remains to be an open issue. In this paper, we
propose a novel approach to combine decision trees and deep neural networks in
an end-to-end learning manner for object detection. First, we disentangle the
decision choices and prediction values by plugging soft decision trees into
neural networks. To facilitate effective learning, we propose randomized
decision routing with node selective and associative losses, which can boost
the feature representative learning and network decision simultaneously.
Second, we develop the decision head for object detection with narrow branches
to generate the routing probabilities and masks, for the purpose of obtaining
divergent decisions from different nodes. We name this approach as the
randomized decision routing for object detection, abbreviated as R(Det)2.
Experiments on MS-COCO dataset demonstrate that R(Det)2 is effective to
improve the detection performance. Equipped with existing detectors, it
achieves $1.4\sim 3.6$% AP improvement.

##  1 Introduction

Figure 1: Overview of the proposed approach. (a) Inspired by decision trees,
we disentangle the decision choices and predictive values by introducing tree
structure for decision head in object detection. With multi-node prediction,
we can explore more diverse cues. (b) We use the soft probability to denote
decision choices for different routes of nodes. The overall decision is the
weighted sum of prediction values from different nodes. Specially, we propose
randomized decision routing to learn divergent decisions from different nodes
for overall performance improvement.

Object detection, which aims to recognize and localize the objects of interest
in images, is a fundamental yet challenging task in computer vision. It is
important for various applications, such as video surveillance, autonomous
driving, and robotics vision. Due to its practical importance, object
detection has attracted significant attention in the community. In recent
decades, deep neural networks (DNNs) have brought significant progress into
object detection. Typically, existing deep learning-based detection methods
include one-stage detectors [31, 25, 22], two-stage detectors [16, 33, 7, 1,
30], end-to-end detectors [3, 51, 39].

Generally, current deep architectures constructed for object detection involve
two components. One is the backbone for feature extraction, which can be pre-
trained with large-scale visual recognition datasets such as ImageNet [35].
The other is the decision head, which produces the predictions for computing
losses or inferring detection boxes. Collaborated with region sampling, object
detection can be converted into a multitask learning issue, where the decision
tasks include classification and bounding box (bbox) regression. For existing
detection networks, the decision head is simply constructed by sequentially
connecting several convolution or fully-connected layers. For one-stage
detectors, the decision head is commonly constructed by stacking several
convolutional layers. The decision head for region proposal in two-stage
detectors is similar. For two-stage detectors, the region-wise decision in
R-CNN stage is typically implemented with 2 fully-connected layers. Since the
decision head is quite important for high-performance detectors, there are
recently devoted researches [43, 37, 8, 12]. However, most of these works
focus on task disentanglement and task-aware learning, leaving the universal
decision mechanism far from exploitation.

Considering that the features from DNNs show great potential for high-level
vision tasks, the simple design of widely-adopted single-node decision might
impede the performance of object detection. A natural question arises: is
single-node prediction good enough for feature exploration in object
detection? To answer this, we focus on novel decision mechanism and propose an
approach to introduce soft decision trees into object detection. As in Figure
1, we integrate soft decision trees to disentangle the routing choices and
prediction values. To jointly learn the soft decision trees and neural
networks in an end-to-end manner, we propose the randomized decision routing
with the combination of so-called selective loss and associate loss.
Experiments validate the effectiveness of the proposed approach and address
the necessity of introducing multi-node predictions. Since our work is mainly
on Randomized Decision routing for object Detection, we name it as R(Det)2.
From the perspective of machine learning, our R(Det)2 is an attempt to bridge
the neural networks and decision trees – two mainstream algorithms, which
would bring insights into future research.

The contributions of this paper are three-fold.

  * •

We propose to disentangle the route choices and prediction values for multi-
node decision in object detection. In particular, we propose randomized
decision routing for the end-to-end joint learning of the tree-based decision
head.

  * •

We construct a novel decision head for object detection, which introduces
routing probabilities and masks to generate divergent decisions from multiple
nodes for the overall decision boosting.

  * •

Extensive experiments validate the effectiveness of our proposed R(Det)2. In
particular, R(Det)2 achieves over 3.6% of $AP$ improvement when equipped with
Faster R-CNN. It improves the detection accuracy of large objects by a large
margin as well.

##  2 Related work

One-stage detectors. Overfeat [36] predicts the decision values for
classification and localization directly with convolutional feature maps. YOLO
[31, 32] regresses the object bounds and category probabilities directly based
on image gridding. SSD [25] improves the one-stage detection with various
scales of multilayer features. Retina Net [22] proposes the focal loss to
tackle the foreground-background imbalance issue. Besides, keypoints-based
one-stage detectors [20, 49, 11, 5] have been extensively studied. CornerNet
[20] generates the heatmaps of top-left and bottom-right corners for
detection. CenterNet [11] uses a triplet of keypoints for representation with
additional center points. Moreover, FCOS [40] and ATSS [47] introduce
centerness branch for anchor-free detection. Other methods delve into sample
assignment strategies [47, 50, 2, 19, 14, 28].

Two-stage detectors. R-CNN [16], Fast R-CNN [15], Faster R-CNN [33] predict
object scores and bounds with pooled features of proposed regions. R-FCN [7]
introduces position-sensitive score maps to share the per-ROI feature
computation. Denet [41] predicts and searches sparse corner distribution for
object bounding. CCNet [29] connects chained classifiers from multiple stages
to reject background regions. Cascade R-CNN [1] uses sequential R-CNN stages
to progressively refine the detected boxes. Libra R-CNN [30] mainly tackles
the imbalance training. Grid R-CNN [27] introduces pixel-level grid points for
predicting the object locations. TSD [37] decouples the predictions for
classification and box bounding with the task-aware disentangled proposals and
task-specific features. Dynamic R-CNN [46] adjusts the label-assigning IoU
thresholds and regression hyper-parameters to improve the detection quality.
Sparse R-CNN [38] learns a fixed set of sparse candidates for region proposal.

End-to-end detectors. DETR [3] models object detection as a set prediction
issue and solve it with transformer encoder-decoder architecture. It inspires
the researches on transformer-based detection frameworks [10, 51, 24, 9, 39].
Deformable DETR [51] proposes the sparse sampling for key elements. TSP [39]
integrates FCOS and R-CNN head into set prediction issue for faster
convergence.

Decision mechanism. The decision head in object detection frameworks usually
involves multiple computational layers (i.e., convolution layers, fully-
connected layers and transformer modules). Typically, for one-stage detectors
with dense priors [31, 25, 22, 11, 40], stacked convolutions are used to
obtain features with larger receptive fields, with separate convolution for
classification, localization and other prediction tasks. For the decision in
R-CNN stages [33, 1, 30, 46, 27], stacked fully-connected layers are common.
Double-head R-CNN [43] uses fully-connected layers for position-insensitive
classification and fully-convolutional layers for position-sensitive
localization. Dynamic head [8] unifies the scale-, spatial- and task-aware
self-attention modules for multitask decisions.

##  3 Randomized decision trees

###  3.1 Soft decision trees

To disentangle the decision choices and prediction values, we first construct
soft decision trees [13] for multiclass classification and bbox regression in
object detection. We use the soft routing probability ranging from 0 to 1 to
represent the decision choice and facilitate network optimization.

Soft decision tree for classification. For multiclass classification, the soft
decision tree is formulated as:

$\mathbf{c}=\sum_{j\in\textit{Nodes}}p_{j}\mathbf{c}_{j},\sum_{j\in\textit{Nodes}}p_{j}=1$
(1)

where $\mathbf{c}$ is the output of the whole classification tree and
$\mathbf{c}_{j}$ is the prediction value from each node. $p_{j}$ is the
routing probability for decision choice. It indicates the probability of
choosing $j$-th classification node. For all the nodes,
$\sum_{j\in\textit{Nodes}}p_{j}=1$. Eqn. 1 shows that $\mathbf{c}$ is the
weighted sum of the classification scores from all the nodes. Different from
traditional decision tree, $p_{j}$ is ”soft” ranging from 0 to 1. $p_{j}$ can
be obtained in networks by a scalar score with activations such as Softmax,
Sigmoid.

Soft decision tree for regression. For bbox regression, we formulate the soft
decision tree in a similar way as:

$\mathbf{b}=\sum_{j\in\textit{Nodes}}q_{j}\mathbf{b}_{j},\sum_{j\in\textit{Nodes}}q_{j}=1$
(2)

where $\mathbf{b}_{j}$ is the regression value output from each node $j$.
$q_{j}$ is the routing probability for the $j$-th regression node.
$\mathbf{b}$ is the output of the tree regressor. Similar to soft
classification tree, the routing probability $q_{j}\in[0,1]$ is “soft”.

Noting that the routing probabilities $p_{j}$, $q_{j}$ denote decision
choices, which indicates the probability of routing the $j$-th node. It can be
viewed as decision confidence in test phase. $\mathbf{c}_{j}$ and
$\mathbf{b}_{j}$ are the prediction values for classification and regression
tasks attached with the $j$-th node. Both the decision choices and prediction
values can be easily obtained with neural layers. With soft decision trees,
multiple discriminative and divergent decisions can be obtained with features
from different aspects. To facilitate the discussion, we restrict the soft
decision tree as binary and $j\in\\{l,r\\}$.

###  3.2 Randomized Decision Routing

To learn soft decision trees in neural networks, we propose randomized
decision routing. The motivation is two-fold. First, in order to obtain a
high-performance decision head with tree structure, we need to avoid the high
relevance of multiple predictions from different nodes. It means that we
should differentiate the training to reduce the decision relevance of
different nodes. Second, we also need to guarantee the decision performance of
the whole tree. In a word, we need to achieve high-performance tree decision
with low-relevant node decisions. To realize this, we propose the selective
loss to supervise the per-node learning and associative loss to guide the
whole-tree optimization. We then unify the selective and associative loss into
a general training framework. Since we involve random factors to model the
probability of routing different nodes, we name this training strategy as
randomized decision routing.

Figure 2: Illustration on training deep networks with decision tree head. We
propose randomized decision routing which includes selective and associative
losses. The selective loss identifies the dominant decisive prediction and
weights the node loss accordingly in a randomized way. The associate loss
learns the routing probability by measuring the difference between the fused
output and the ground truth.

To achieve node decisions with low relevance, we first perform node selection
to identify the node with higher optimization priority. We then attach the
selected node with a higher routing probability. Oppositely, a lower routing
probability is attached with the remaining node. Divergent routing
probabilities lead to different learning rates for different nodes. Therefore,
to diversify the decision of different nodes, we construct the selective loss
by setting different randomized weights for different node losses. As
illustrated in Figure 2-left, the selective losses for classification and bbox
regression are denoted as:

$\displaystyle L_{s}^{cls}(\mathbf{c}_{l},$
$\displaystyle\mathbf{c}_{r},y)=\gamma_{l}^{c}L_{l}^{c}+\gamma_{r}^{c}L_{r}^{c}$
(3)
$\displaystyle=\gamma_{l}^{c}L^{cls}(\mathbf{c}_{l},y)+\gamma_{r}^{c}L^{cls}(\mathbf{c}_{r},y)$
$\displaystyle L_{s}^{bbox}(\mathbf{b}_{l},$
$\displaystyle\mathbf{b}_{r},B)=\gamma_{l}^{b}L_{l}^{b}+\gamma_{r}^{b}L_{r}^{b}$
(4)
$\displaystyle=\gamma_{l}^{b}L^{bbox}(\mathbf{b}_{l},B)+\gamma_{r}^{b}L^{bbox}(\mathbf{b}_{r},B)$

where $y$ is the ground truth label and $B$ is the ground truth for bbox
regression. $\gamma_{l}^{c},\gamma_{r}^{c}$ are the weights indicating the
probability for selective routing of classification tree.
$\gamma_{l}^{b},\gamma_{r}^{b}$ are the weights indicating the probability for
selective decision routing of bbox regression tree.

Figure 3: Decision head for object detection. (a) shows the common decision
head. (b) shows R(Det)2-B which disentangles the decision choice and values by
soft decision trees. (c) shows R(Det)2-M which leverages the routing masks to
produce the divergent input features for decision. (d) shows R(Det)2-T which
unifies task disentanglement into R(Det)2-based decision head.

We leverage random weights to differentiate the node learning. For
classification, we set $\gamma^{c}_{l}$, $\gamma^{c}_{r}$ based on the
comparison of $L_{l}^{c},L_{r}^{c}$. We set the nodes with lower loss values
with higher random weights. For bbox regression, we set the weights
$\gamma^{b}_{l}$, $\gamma_{r}^{b}$ according to the relative comparison of
$q_{l},q_{r}$. For instance, if $q_{l}<q_{r}$, we restrict
$\gamma_{l}^{b}<\gamma_{r}^{b}$. It is consistent with the intuition that we
learn the selective node with higher priority in a fast way, meanwhile
learning the remaining one in a slow way. Empirically, we sample the lower
weight from $U(0.1,0.3)$ and the higher weight from $U(0.9,1.1)$. This slow-
fast randomized manner would benefit the learning of the whole decision head.

Besides of differentiating node decisions, we also need to ensure the
performance of the whole decision tree. That is, the predictive decision
output from the whole tree should be good. To achieve this, we formulate
associative loss based on the fused prediction $\mathbf{c}$, $\mathbf{b}$. The
associative loss can be the same as the original classification or bbox
regression loss in form, with the fused prediction as the input. As
illustrated in Figure 2-right, the associative loss for classification and
bbox regression is formulated as:

$L_{a}^{cls}\left(\mathbf{c},y\right)=L^{cls}\left(p_{l}\mathbf{c}_{l}+p_{r}\mathbf{c}_{r},y\right)$
(5)
$L_{a}^{bbox}\left(\mathbf{b},B\right)=L^{bbox}\left(q_{l}\mathbf{b}_{l}+q_{r}\mathbf{b}_{r},B\right)$
(6)

The routing probabilities and prediction values are simultaneously optimized
with the associative loss. Specially, the routing probability which indicates
the decision choice is only supervised by this associative loss, resulting in
appropriate routing in inference.

The whole loss is formulated as follows:

$L_{all}=\lambda\left(L_{s}^{cls}+L_{s}^{bbox}\right)+(1-\lambda)\left(L_{a}^{cls}+L_{a}^{bbox}\right)$
(7)

where $\lambda\in[0,1]$ is the coefficient to balance between selective loss
and associative loss. It is noteworthy that the $L^{cls}$, $L^{bbox}$ for
computing the selective and associative loss can be commonly-used loss
functions for classification (e.g., cross-entropy loss, Focal loss [22]) and
bbox regression (e.g., Smooth-L1 loss, IoU loss [45, 42, 34, 48]). With soft
decision trees, we can generate multiple decisions with different visual cues.
Moreover, the divergent learning helps enhance feature representations and
suppress over-optimization, further promote object detection.

##  4 Decision head for detection

We construct the head with decision trees for object detection. The common-
used head of R-CNN detectors [33, 17, 1, 21] is single-prediction type, as in
Figure 3(a). Typically, two fully-connected (fc) layers are sequentially
connected with region-pooled features, with one additional fc layer for
classification and bbox regression, respectively. In order to obtain decision
values for multiple nodes, we first generate predictions
$\mathbf{c}_{l},\mathbf{c}_{r}$ and $\mathbf{b}_{l},\mathbf{b}_{r}$ with the
features output from the same structure as the common head. We further add
another narrow branch with 1$\sim$2 fc layers to produce the routing
probabilities $p_{l},p_{r}$ and $q_{l},q_{r}$, as illustrated in Figure 3(b).
We record this as the Basic head for randomized decision routing, as
R(Det)2-B. The routing choices and predictions are disentangled with this
basic head structure.

Moreover, we add the routing masks for features before prediction to increase
the divergence of decisions from multiple nodes. The decision values
$\mathbf{c}_{l},\mathbf{c}_{r}$ and $\mathbf{b}_{l},\mathbf{b}_{r}$ are
generated with route-wise masked features. As in Figure 3(c), we average the
batched region-wise features to obtain a single context-like vector. Another
fc layer with Sigmoid is imposed on this vector to produce routing masks for
different nodes. By multiplying the route-wise masks on the last features
before decision, we further diversify the input for different nodes of
decision. The dependence of node decisions can be further reduced. We record
this as Masked head for randomized decision routing, as R(Det)2-M.

Inspired by efforts on disentangling the classification and localization tasks
for detection, we develop another R(Det)2-T. We separate the last feature
computation before the multitask prediction and unify the task-aware feature
learning into our framework, as in Figure 3(d). Since it is not the main focus
of this work, we have not involved more complicated task-aware head designs
[43, 37, 46]. Yet it is noteworthy that the proposed R(Det)2 can easily be
plugged into these detectors for performance improvement.

##  5 Experiments

Datasets. We evaluate our proposed approach on the large-scale benchmark MS
COCO 2017 [23]. Following common practice, we train detectors on training
split with $\sim$115k images and evaluate them on val split with 5k images. We
also report the results and compare with the state-of-the-art on COCO test-dev
split with 20k images. The standard mean average precision (AP) across
different IoU thresholds is used as the evaluation metric.

Training details. We implement the proposed R(Det)2 as the plug-in head and
integrate it into existing detectors. Our implementation is based on the
popular mmdetection [4] platform. If not specially noted, the R(Det)2 serves
for the decision in R-CNN of two-stage detectors, as Faster R-CNN [33],
Cascade R-CNN [1]. We train the models with ResNet-50/ResNet-101 [18]
backbones with 8 Nvidia TitanX GPUs. The learning rate is set to 0.02 and the
weight decay is 1e-4, with momentum 0.9. The models for ablation studies are
trained with the standard 1$\times$ configuration. No data augmentation is
used except for standard horizontal image flipping. We only conduct multiscale
training augmentation for evaluation on COCO test-dev to compare with the
state-of-the-art.

Inference details. It is noteworthy that the randomized decision routing is
only performed in training phase. In inference, we perform on the single image
scale without specific noticing. Following standard practice, we evaluate the
models with test time augmentation (TTA) as multiscale testing to compare with
the state-of-the-art.

|  B |  M |  T |  $AP$ |  $AP_{50}$ |  $AP_{75}$ |  $AP_{S}$ |  $AP_{M}$ |  $AP_{L}$
---|---|---|---|---|---|---|---|---|---
2fc |  |  |  |  37.4 |  58.1 |  40.4 |  21.2 |  41.0 |  48.1
2fc |  ✓ |  |  |  38.8 |  59.8 |  41.8 |  22.3 |  42.3 |  50.9
|  |  ✓ |  |  39.1 |  60.5 |  42.3 |  22.5 |  43.1 |  50.5
|  |  |  ✓ |  38.9 |  60.2 |  42.1 |  23.1 |  42.1 |  50.2
4conv |  ✓ |  |  |  38.7 |  59.0 |  41.9 |  22.4 |  42.0 |  50.4
1fc |  |  ✓ |  |  39.2 |  59.7 |  42.4 |  22.8 |  42.8 |  51.5
|  |  |  ✓ |  39.5 |  59.8 |  42.9 |  22.7 |  43.1 |  51.7
4conv |  ✓ |  |  |  39.3 |  60.2 |  42.7 |  22.5 |  42.8 |  51.6
(res) |  |  ✓ |  |  40.1 |  60.8 |  43.3 |  23.3 |  43.5 |  52.6
1fc |  |  |  ✓ |  40.4 |  61.2 |  44.1 |  23.8 |  43.7 |  53.0
Table 1: Ablation study on different types with R(Det)2. The baseline is
Faster R-CNN equipped with ResNet-50 backbone. B, M and T represents
R(Det)2-B, R(Det)2-M and R(Det)2-T for decision heads, respectively.

###  5.1 Ablation study

Effects of components. We first conduct the ablative experiment to evaluate
the effects of different components for R(Det)2 (Table. 1). We integrate the
proposed decision head structure into the R-CNN stage and apply randomized
decision routing for training. We first follow the common setting with
2$\times$1024 fully-connected layers (referred as 2fc) to generate region-wise
features, with decision values for multiclass classification and bbox
regression predicted based on them. By converting 2fc to R(Det)2-B, we
increase the detection $AP$ to 38.8%, yielding 1.4% of improvement. By adding
routing masks for region-wise features, R(Det)2-M achieves 39.1% detection
$AP$, 1.7% of improvement. It is reasonable since the mask multiplying would
promote the decision differences between nodes, leading to the improvement of
joint decision. We further replace 2fc with 4$\times$256 convolutional layers
with 1 fully-connected layer (referred as 4conv1fc). The achieved $AP$
increases to 38.7%, 39.2% and 39.5% with R(Det)2-B, R(Det)2-M, R(Det)2-T,
respectively. We further add residual connections between neighboring
convolutions for feature enhancement, referred to as 4conv(res)1fc. By
integrating 4conv(res)1fc with R(Det)2-B, we achieve $AP$ of 39.3% and
$AP_{75}$ of 42.7%. By integrating R(Det)2-M, the achieved $AP$ is 40.1% and
$AP_{75}$ is 43.3%. With task disentanglement as R(Det)2-T, we achieve $AP$,
$AP_{50}$, $AP_{75}$ of 40.4%, 61.2% and 44.1%, respectively. Compared to the
baseline, the $AP$, $AP_{50}$, $AP_{75}$ is increased by 3.0%, 3.1% and 3.7%,
respectively. In particular, the R(Det)2 significantly improves the detection
accuracy on large objects, leading to the $AP_{L}$ improvement by a large
margin. Compared with the baseline, we achieve 4.9% of $AP_{L}$ improvement
ultimately. It verifies that the features contain much more information to be
exploited, especially for larger objects with high-resolution visual cues. Our
proposed R(Det)2 which produces decisions with multiple nodes can focus on the
evidence from diverse aspects, leading to significant performance improvement.

$L^{cls}$ |  $L^{bbox}$ |  $AP$ |  $AP_{50}$ |  $AP_{75}$ |  $AP_{S}$ |  $AP_{M}$ |  $AP_{L}$
---|---|---|---|---|---|---|---
Baseline |  |  37.4 |  58.1 |  40.4 |  21.2 |  41.0 |  48.1
CE |  S-L1 |  40.4 |  61.2 |  44.1 |  23.8 |  43.7 |  53.0
Focal |  S-L1 |  40.5 |  61.2 |  44.4 |  24.2 |  43.6 |  52.6
CE |  IoU |  40.9 |  61.2 |  44.5 |  23.9 |  44.2 |  53.7
Focal |  IoU |  41.0 |  61.1 |  44.5 |  24.3 |  44.3 |  53.7
Table 2: Comparison with different loss functions. The baseline model is
Faster R-CNN with ResNet-50 as the backbone. CE indicates the cross-entropy
loss. Focal indicates the original focal loss [22]. S-L1 indicates the
Smooth-L1 loss. IoU indicates the loss computed by the negative-log of
intersection-over-union [45].

Effectiveness with different loss functions. The proposed randomized decision
routing can be combined with any existing classification and localization
losses. We conduct experiments to evaluate the effectiveness of R(Det)2 with
different loss functions(Table 2). When we apply the Softmax cross-entropy
loss for classification and Smooth-L1 loss for bbox regression, we achieve
40.4% $AP$, 61.2% $AP_{50}$, 44.1% $AP_{75}$. Compared to baseline Faster
R-CNN with the same losses, we increase the $AP$, $AP_{50}$, $AP_{75}$ by
3.0%, 3.1%, 3.7%, respectively. The $AP$ is slightly higher with focal loss
[22] applying for classification. The detection $AP$ is further increased with
IoU loss [45] applied for bbox regression. The detection $AP$ reaches 41.0%.
Compared with the baseline, the $AP$ is increased by 3.6% and $AP_{L}$ is
increased by 5.6%. It indicates that the proposed R(Det)2 performs well with
different combinations of loss functions, which further demonstrates its
effectiveness.

Backbone |  $AP$ |  $AP_{50}$ |  $AP_{75}$ |  $AP_{S}$ |  $AP_{M}$ |  $AP_{L}$
---|---|---|---|---|---|---
R50 |  37.4 |  58.1 |  40.4 |  21.2 |  41.0 |  48.1
+R(Det)2 |  41.0 |  61.2 |  44.8 |  24.6 |  44.1 |  53.7
|  (+3.6) |  (+3.1) |  (+4.4) |  (+3.4) |  (+3.1) |  (+5.6)
R50-DCN |  41.3 |  62.4 |  45.0 |  24.6 |  44.9 |  54.4
+R(Det)2 |  44.2 |  64.5 |  48.3 |  26.6 |  47.7 |  58.6
|  (+2.9) |  (+2.1) |  (+3.3) |  (+2.0) |  (+2.8) |  (+4.2)
R101 |  39.4 |  60.1 |  43.1 |  22.4 |  43.7 |  51.1
+R(Det)2 |  42.5 |  62.8 |  46.3 |  25.1 |  46.4 |  55.7
|  (+3.1) |  (+2.7) |  (+3.2) |  (+2.7) |  (+3.7) |  (+4.8)
R101-DCN |  42.7 |  63.7 |  46.8 |  24.9 |  46.7 |  56.8
+R(Det)2 |  45.0 |  65.4 |  49.2 |  27.2 |  48.8 |  59.6
|  (+2.3) |  (+1.7) |  (+2.4) |  (+2.3) |  (+2.1) |  (+2.8)
Table 3: Comparison with different backbone networks. R-50 and R-101 indicates
ResNet-50 and ResNet-101, respectively. R(Det)2 is plugged in Faster R-CNN
with various backbones and achieves consistent performance gains.

Effectiveness on different backbone networks. With Faster R-CNN as the
baseline detector, we conduct the ablative experiment to evaluate the
effectiveness of R(Det)2 on various backbones(Table 3). With ResNet-50 as the
backbone, the achieved $AP$, $AP_{50}$ and $AP_{75}$ of R(Det)2 is improved by
3.6%, 3.0%, and 4.1%, respectively. With ResNet-50-DCN (ResNet-50 with
deformable convolution) as the backbone, we achieve the detection $AP$ of
44.2%, 2.9% improvement. The performance gain of R(Det)2 with ResNet-101 is
also significant. By equipping with R(Det)2, the detection $AP$ of ResNet-101
reaches 42.5% and $AP_{75}$ reaches 46.3%, 3.1% and 3.2% higher than the
baseline. With ResNet-101-DCN as the backbone, the $AP$ reaches 45.0% and
$AP_{75}$ is 49.2%. In particular, the detection accuracy over large objects
is improved significantly. The $AP_{L}$ over the different backbones is
increased by 5.6%, 4.2%, 4.8% and 2.8%, respectively. Experiments show that
the proposed R(Det)2 is effective among object detectors with various
backbones.

Detector |  $AP$ |  $AP_{50}$ |  $AP_{75}$ |  $AP_{S}$ |  $AP_{M}$ |  $AP_{L}$
---|---|---|---|---|---|---
Libra R-CNN [30] |  38.3 |  59.5 |  41.9 |  22.1 |  42.0 |  48.5
+R(Det)2 |  41.4(+3.1) |  61.4(+1.9) |  45.5(+3.6) |  24.7(+2.5) |  45.0(+3.0) |  53.7(+5.2)
Cascade R-CNN [1] |  40.3 |  58.6 |  44.0 |  22.5 |  43.8 |  52.9
+R(Det)2 |  42.5(+2.2) |  61.0(+2.4) |  45.8(+1.8) |  24.6(+2.1) |  45.5(+1.7) |  57.0(+4.1)
Dynamic R-CNN [46] |  38.9 |  57.6 |  42.7 |  22.1 |  41.9 |  51.7
+R(Det)2 |  41.0(+2.1) |  59.7(+2.1) |  44.8(+2.1) |  23.3(+1.2) |  44.2(+2.3) |  54.8(+3.1)
DoubleHead R-CNN [43] |  40.1 |  59.4 |  43.5 |  22.9 |  43.6 |  52.9
+R(Det)2 |  41.5(+1.4) |  60.8(+1.4) |  44.5(+1.0) |  24.2(+1.3) |  45.0(+1.4) |  53.9(+1.0)
RetinaNet [22] |  36.5 |  55.4 |  39.1 |  20.4 |  40.3 |  48.1
+R(Det)2 |  38.3(+1.8) |  57.4(+2.0) |  40.8(+1.7) |  22.6(+2.2) |  42.0(+1.7) |  50.5(+2.4)
Table 4: Generalization with different detectors. R(Det)2 shows $AP$
improvement on various detectors.

Generalization on different detectors. We plug R(Det)2 into existing detectors
to evaluate the generalization capability (Table 4). Other than Faster R-CNN,
we integrate R(Det)2 with libra R-CNN [30], dynamic R-CNN [46], cascade R-CNN
[1]. The backbone is ResNet-50. Upon libra R-CNN, R(Det)2 improves the
detection $AP$ by 3.1% and $AP_{75}$ by 3.6%, yielding 41.4% $AP$ and 45.5%
$AP_{75}$. On cascade R-CNN, the powerful detector with cascade structure,
R(Det)2 also shows consistent improvement. It improves the detection $AP$ by
2.2% and $AP_{50}$ by 2.4%, respectively. Since the dynamic R-CNN [46]
adaptively changes the hyperparameters of Smooth-L1 loss for bbox regression,
we present the detection accuracy by randomized routing upon Smooth-L1 loss,
instead of IoU loss with better performance. By equipping R(Det)2, the $AP$
and $AP_{75}$ is increased by 2.1%. Besides, R(Det)2 is quite effective to
improve the detection performance of large objects. The $AP_{L}$ of libra
R-CNN and cascade R-CNN is increased by a large margin with R(Det)2, leading
to 5.2% and 4.1% improvement, respectively. For DoubleHead R-CNN [43] and one-
stage RetinaNet [22] with designed head, we fix the head for task-aware
decision. Only randomized routing based training leads to 1.4% of $AP$
improvement with DoubleHead R-CNN and 1.8% of $AP$ improvement with RetinaNet
[22]. The experiment validates that the proposed R(Det)2 performs well on
existing detectors.

Figure 4: Effects on hyperparameter $\lambda$ to balance the selective loss
and associative loss for decision routing.

Effects of hyperparameter $\lambda$. We leverage the hyperparameter $\lambda$
to balance the selective and associative loss in randomized decision routing.
We further evaluate the effects of $\lambda$ with ResNet-50-based Faster
R-CNN. The curves of detection $AP$ changing along with $\lambda$ are plotted
in Figure 4. The detection accuracy is the highest when $\lambda=0.5$. That
means we assign the weights for the selective and associative loss nearly
equal. The detection $AP$ remains stable when $\lambda$ is between 0.1 to 0.9.
If we further reduce $\lambda$ to 0.001 and reduce the impact of selective
loss, the detection $AP$ with Smooth-L1 loss for bbox regression decreases to
38.6%, by 1.8% points. It indicates that the selective loss which aims to
differentiate node decisions is essential for performance improvement. Since
only associative loss guides the optimization of routing probabilities,
increasing $\lambda$ to nearly 1 would lead to unstable models (the parameters
to generate routing probabilities $p_{l},p_{r},q_{l},q_{r}$ is nearly the same
as random initialized ones), we restrict $\lambda\leq 0.95$. The detection
$AP$ at $\lambda=0.95$ is decreased by 0.3$\sim$0.4%.

Type |  #FLOPs |  #params |  $AP$(%)
---|---|---|---
4conv1fc |  129.0G |  15.62M |  37.6
R(Det)2-B |  132.6G |  19.31M |  39.8
R(Det)2-M |  132.6G |  25.88M |  40.5
R(Det)2-T |  146.3G |  45.97M |  40.9
R(Det)2-Lite |  130.2G |  18.48M |  40.2
Table 5: Model complexity comparison of R(Det)2 head.

Model complexity and computational efficiency. The model complexity of R(Det)2
is mainly caused by the additional branches for routing probability, routing
mask, and task-aware features. From Table 5 we can see that the complexity is
mainly caused by task-aware feature computation. Considering this, we develop
R(Det)2-Lite with narrow computation for routing probabilities and masks,
leading to 40.2% $AP$ and nearly ignorable model complexity.

Visualization. We present the comparative visualization in Figure 5. The
detected results by ResNet-101 based Faster R-CNN are shown in Figure 5(a) and
those from the R(Det)2 are shown in Figure 5(b). It can be seen that the
proposed R(Det)2 is effective to improve both the detection and localization
performance. Specially, the R(Det)2 is quite effective in reducing the
repeated detections and avoiding over-confident ones.

Figure 5: Comparison of detection results for the baseline Faster R-CNN and R(Det)2 equipped one. The models are with ResNet-101 as the backbone and trained with COCO 115k-train. The example test images are from COCO 5k-val. The rectangles mark the detected bounding boxes with attached category labels and confidences. The detection results of baseline model are presented in (a) (39.3% AP) and those of R(Det)2 are presented in (b) (42.5% AP).  Methods |  Backbone |  ME |  TTA |  $AP$ |  $AP_{50}$ |  $AP_{75}$ |  $AP_{S}$ |  $AP_{M}$ |  $AP_{L}$
---|---|---|---|---|---|---|---|---|---
Retina-Net [22] |  ResNeXt-101 |  18e |  |  40.8 |  61.1 |  44.1 |  24.1 |  44.2 |  51.2
FCOS [40] |  ResNeXt-101 |  24e |  |  43.2 |  62.8 |  46.6 |  26.5 |  46.2 |  53.3
ATSS [47] |  ResNeXt-101-DCN |  24e |  |  47.7 |  66.5 |  51.9 |  29.7 |  50.8 |  59.4
OTA [14] |  ResNeXt-101-DCN |  24e |  |  49.2 |  67.6 |  53.5 |  30.0 |  52.5 |  62.3
IQDet [28] |  ResNeXt-101-DCN |  24e |  |  49.0 |  67.5 |  53.1 |  30.0 |  52.3 |  62.0
Faster R-CNN [33] |  ResNet-101 |  12e |  |  36.7 |  54.8 |  39.8 |  19.2 |  40.9 |  51.6
Libra R-CNN [30] |  ResNeXt-101 |  12e |  |  43.0 |  64.0 |  47.0 |  25.3 |  45.6 |  54.6
Cascade R-CNN [1] |  ResNet-101 |  18e |  |  42.8 |  62.1 |  46.3 |  23.7 |  45.5 |  55.2
TSP-RCNN [39] |  ResNet-101-DCN |  96e |  |  47.4 |  66.7 |  51.9 |  29.0 |  49.7 |  59.1
Sparse R-CNN [38] |  ResNeXt-101-DCN |  36e |  |  48.9 |  68.3 |  53.4 |  29.9 |  50.9 |  62.4
Deformable DETR [51] |  ResNeXt-101-DCN |  50e |  |  50.1 |  69.7 |  54.6 |  30.6 |  52.8 |  64.7
Ours - R(Det)2 |  ResNeXt-101-DCN |  12e |  |  50.0 |  69.2 |  54.3 |  30.9 |  53.0 |  63.9
Ours - R(Det)2 |  Swin-L [26] |  12e |  |  55.1 |  74.1 |  60.4 |  36.0 |  58.6 |  70.0
Centernet [11] |  Hourglass-104 |  100e |  ✓ |  47.0 |  64.5 |  50.7 |  28.9 |  49.9 |  58.9
ATSS [47] |  ResNeXt-101-DCN |  24e |  ✓ |  50.7 |  68.9 |  56.3 |  33.2 |  52.9 |  62.4
IQDet [28] |  ResNeXt-101-DCN |  24e |  ✓ |  51.6 |  68.7 |  57.0 |  34.5 |  53.6 |  64.5
OTA [14] |  ResNeXt-101-DCN |  24e |  $\checkmark$ |  51.5 |  68.6 |  57.1 |  34.1 |  53.7 |  64.1
Dynamic R-CNN [46] |  ResNet-101-DCN |  36e |  ✓ |  50.1 |  68.3 |  55.6 |  32.8 |  53.0 |  61.2
TSD [37] |  SENet154-DCN |  36e |  ✓ |  51.2 |  71.9 |  56.0 |  33.8 |  54.8 |  64.2
Sparse R-CNN [38] |  ResNeXt-101-DCN |  36e |  ✓ |  51.5 |  71.1 |  57.1 |  34.2 |  53.4 |  64.1
RepPoints v2 [5] |  ResNeXt-101-DCN |  24e |  ✓ |  52.1 |  70.1 |  57.5 |  34.5 |  54.6 |  63.6
Deformable DETR [51] |  ResNeXt-101-DCN |  50e |  ✓ |  52.3 |  71.9 |  58.1 |  34.4 |  54.4 |  65.6
RelationNet++ [6] |  ResNeXt-101-DCN |  24e |  ✓ |  52.7 |  70.4 |  58.3 |  35.8 |  55.3 |  64.7
DyHead [8] |  ResNeXt-101-DCN |  24e |  ✓ |  54.0 |  72.1 |  59.3 |  37.1 |  57.2 |  66.3
Ours - R(Det)2 |  ResNeXt-101-DCN |  24e |  ✓ |  54.1 |  72.4 |  59.4 |  35.5 |  57.0 |  67.3
Ours - R(Det)2 |  Swin-L [26] |  12e |  ✓ |  57.4 |  76.1 |  63.0 |  39.4 |  60.5 |  71.5
Table 6: Comparison of R(Det)2 with the state-of-the-art object detection
methods on COCO test-dev dataset. DCN indicates that using the deformable
convolution to enhance the feature representations of backbone. TTA indicates
test-time augmentation such as multi-scale testing and horizontal image
flipping. ME indicates more epochs of training.

###  5.2 Comparison with the state-of-the-art

We integrate the proposed R(Det)2 into Cascade R-CNN to compare with the
state-of-the-art methods on COCO test-dev dataset. The backbone is ResNeXt-101
(64$\times$4d) [44] with deformable convolution and swin transformer [26]. The
comparative study is presented in Table 6. We first compare the single-model
single-scale model performance. With 12 epochs ($1\times$) of training, the
R(Det)2 achieves $AP$ of 50.0%, outperforming Faster R-CNN [33], Libra R-CNN
[30], Cascade R-CNN [1] by a large margin. Compared with the recent Sparse
R-CNN [38] with the same backbone, we achieve 1.1% $AP$ improvement with 1/3
training iterations. It is also comparable with deformable DETR [51] with
transformer architecture and much more epochs of training (50 epochs). The
detection accuracy is further improved with more epochs of training and test-
time augmentation as multi-scale testing and horizontal image flipping. With
24 epochs of training and TTA, the R(Det)2 achieves $AP$ of 54.1% and
$AP_{50}$ of 72.4%. Compared with DyHead with stacked self-attention modules
[8], the $AP_{50}$, $AP_{L}$ is improved by 0.3% and 1.0%, respectively.
Besides, we adapt the backbone of ViT as swin transformer [26]. With 12 epochs
of training, the achieved $AP$ of single-scale testing is 55.1% and that of
multi-scale testing is 57.4%. It validates the R(Det)2 performs well with
various backbones and is effective for high-performance object detection.

##  6 Conclusion

The decision head is important for high-performance object detection. In this
paper, we propose a novel approach as the randomized decision routing for
object detection. First, we plug soft decision trees into neural networks. We
further propose the randomized routing to produce accurate yet divergent
decisions. By randomized routing for soft decision trees, we can obtain multi-
node decisions with diverse feature exploration for object detection. Second,
we develop the decision head for detection with a narrow branch to generate
routing probabilities and a wide branch to produce routing masks. By reducing
the relevance of node decisions, we develop a novel tree-like decision head
for deep learning-based object detection. Experiments validate the performance
of our proposed R(Det)2.

## Acknowledgement

This work was supported by the state key development program in 14th Five-Year
under Grant Nos.2021QY1702, 2021YFF0602103, 2021YFF0602102. We also thank for
the research fund under Grant No. 2019GQG0001 from the Institute for Guo
Qiang, Tsinghua University.

## References

  * [1] Zhaowei Cai and Nuno Vasconcelos.  Cascade r-cnn: Delving into high quality object detection.  CVPR, pages 6154–6162, 2018.
  * [2] Yuhang Cao, Kai Chen, Chen Change Loy, and Dahua Lin.  Prime sample attention in object detection.  CVPR, pages 11583–11591, 2020.
  * [3] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  ECCV, pages 213–229, 2020.
  * [4] Kai Chen, Jiaqi Wang, Jiangmiao Pang, Yuhang Cao, Yu Xiong, Xiaoxiao Li, Shuyang Sun, Wansen Feng, Ziwei Liu, Jiarui Xu, Zheng Zhang, Dazhi Cheng, Chenchen Zhu, Tianheng Cheng, Qijie Zhao, Buyu Li, Xin Lu, Rui Zhu, Yue Wu, Jifeng Dai, Jingdong Wang, Jianping Shi, Wanli Ouyang, Chen Change Loy, and Dahua Lin.  MMDetection: Open mmlab detection toolbox and benchmark.  arXiv preprint arXiv:1906.07155, 2019.
  * [5] Yihong Chen, Zheng Zhang, Yue Cao, Liwei Wang, Stephen Lin, and Han Hu.  Reppoints v2: Verification meets regression for object detection.  NIPS, pages 5621–5631, 2020.
  * [6] Cheng Chi, Fangyun Wei, and Han Hu.  Relationnet++: Bridging visual representations for object detection via transformer decoder.  NIPS, pages 13564–13574, 2020.
  * [7] Jifeng Dai, Yi Li, Kaiming He, and Jian Sun.  R-fcn: Object detection via region-based fully convolutional networks.  NIPS, pages 379–387, 2016.
  * [8] Xiyang Dai, Yinpeng Chen, Bin Xiao, Dongdong Chen, Mengchen Liu, Lu Yuan, and Lei Zhang.  Dynamic head: Unifying object detection heads with attentions.  CVPR, pages 7373–7382, 2021.
  * [9] Xiyang Dai, Yinpeng Chen, Jianwei Yang, Pengchuan Zhang, Lu Yuan, and Lei Zhang.  Dynamic detr: End-to-end object detection with dynamic attention.  ICCV, pages 2988–2997, 2021.
  * [10] Zhigang Dai, Bolun Cai, Yugeng Lin, and Junying Chen.  Up-detr: Unsupervised pre-training for object detection with transformers.  CVPR, pages 1601–1610, 2021.
  * [11] Kaiwen Duan, Song Bai, Lingxi Xie, Honggang Qi, Qingming Huang, and Qi Tian.  Centernet: Keypoint triplets for object detection.  ICCV, pages 6569–6578, 2019.
  * [12] Chengjian Feng, Yujie Zhong, Yu Gao, Matthew R. Scott, and Weilin Huang.  Tood: Task-aligned one-stage object detection.  ICCV, pages 3490–3499, 2021.
  * [13] Nicholas Frosst and Geoffrey Hinton.  Distilling a neural network into a soft decision tree.  arXiv preprint arXiv:1711.09784, 2017.
  * [14] Zheng Ge, Songtao Liu, Zeming Li, Osamu Yoshie, and Jian Sun.  Ota: Optimal transport assignment for object detection.  CVPR, pages 303–312, 2021.
  * [15] Ross Girshick.  Fast r-cnn.  ICCV, pages 1440–1448, 2015.
  * [16] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  CVPR, pages 580–587, 2014.
  * [17] Kaiming He, Georgia Gkioxari, Piotr Dollar, and Ross Girshick.  Mask r-cnn.  ICCV, pages 2961–2969, 2017.
  * [18] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  CVPR, pages 770–778, 2016.
  * [19] Tao Kong, Fuchun Sun, Huaping Liu, Yuning Jiang, Lei Li, and Jianbo Shi.  Foveabox: Beyound anchor-based object detection.  IEEE Trans. Image Proc., 29:7389–7398, 2020.
  * [20] Hei Law and Jia Deng.  Cornernet: Detecting objects as paired keypoints.  ECCV, pages 734–750, 2018.
  * [21] Zeming Li, Chao Peng, Gang Yu, Xiangyu Zhang, Yangdong Deng, and Jian Sun.  Light-head r-cnn: In defense of two-stage object detector.  arXiv:1711.07264, 2017.
  * [22] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollar.  Focal loss for dense object detection.  ICCV, pages 2980–2988, 2017.
  * [23] Tsung-Yi Lin, Michael Maire, Serge Belongie, Lubomir Bourdev, Ross Girshick, James Hays, Pietro Perona, Deva Ramanan, C. Lawrence Zitnick, and Piotr Dollar.  Microsoft coco: Common objects in context.  ECCV, pages 740–755, 2014.
  * [24] Fanfan Liu, Haoran Wei, Wenzhe Zhao, Guozhen Li, Jingquan Peng, and Zihao Li.  Wb-detr: Transformer-based detector without backbone.  ICCV, pages 2979–2987, 2021.
  * [25] Wei Liu, Dragomir Anguelov, Dumitru Erhan, Christian Szegedy, Scott Reed, Cheng-Yang Fu, and Alexander C. Berg.  Ssd: Single shot multibox detector.  ECCV, pages 21–37, 2016.
  * [26] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  ICCV, pages 10012–10022, 2021.
  * [27] Xin Lu, Buyu Li, Yuxin Yue, Quanquan Li, and Junjie Yan.  Grid r-cnn.  In CVPR, pages 7363–7372, 2019.
  * [28] Yuchen Ma, Songtao Liu, Zeming Li, and Jian Sun.  Iqdet: Instance-wise quality distribution sampling for object detection.  CVPR, pages 1717–1725, 2021.
  * [29] Wanli Ouyang, Kun Wang, Xin Zhu, and Xiaogang Wang.  Chained cascade network for object detection.  ICCV, pages 1938–1946, 2017.
  * [30] Jiangmiao Pang, Kai Chen, Jianping Shi, Huajun Feng, Wanli Ouyang, and Dahua Lin.  Libra r-cnn: Towards balanced learning for object detection.  CVPR, pages 821–830, 2019.
  * [31] Joseph Redmon, Santosh Divvala, Ross Girshick, and Ali Farhadi.  You only look once: Unified, real-time object detection.  CVPR, pages 779–788, 2016.
  * [32] Joseph Redmon and Ali Farhadi.  Yolov3: An incremental improvement.  arXiv:1804.02767, 2018.
  * [33] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  IEEE Trans. on Pat. Anal. and Mach. Intell., 39(6):1137–1149, 2017\.
  * [34] Hamid Rezatofighi, Nathan Tsoi, JunYoung Gwak, Amir Sadeghian, Ian Reid, and Silvio Savarese.  Generalized intersection over union: A metric and a loss for bounding box regression.  CVPR, pages 658–666, 2019.
  * [35] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei.  Imagenet large scale visual recognition challenge.  arXiv:1409.0575, 2014.
  * [36] Pierre Sermanet, David Eigen, Xiang Zhang, Michael Mathieu, Rob Fergus, and Yann LeCun.  Overfeat: Integrated recognition, localization and detection using convolutional networks.  arXiv:1312.6229, 2013.
  * [37] Guanglu Song, Yu Liu, and Xiaogang Wang.  Revisiting the sibling head in object detector.  CVPR, pages 11563–11572, 2020.
  * [38] Peize Sun, Rufeng Zhang, Yi Jiang, Tao Kong, Chenfeng Xu, Wei Zhan, Masayoshi Tomizuka, Lei Li, Zehuan Yuan, Changhu Wang, and Ping Luo.  Sparse r-cnn: End-to-end object detection with learnable proposals.  CVPR, pages 14454–14463, 2021.
  * [39] Zhiqing Sun, Shengcao Cao, Yiming Yang, and Kris Kitani.  Rethinking transformer-based set prediction for object detection.  ICCV, pages 3611–3620, 2021.
  * [40] Zhi Tian, Chunhua Shen, Hao Chen, and Tong He.  Fcos: Fully convolutional one-stage object detection.  ICCV, pages 9627–9636, 2019.
  * [41] Lachlan Tychsen-Smith and Lars Petersson.  Denet: Scalable real-time object detection with directed sparse sampling.  ICCV, pages 428–436, 2017.
  * [42] Lachlan Tychsen-Smith and Lars Petersson.  Improving object localization with fitness nms and bounded iou loss.  CVPR, pages 6877–6885, 2018.
  * [43] Yue Wu, Yinpeng Chen, Lu Yuan, Zicheng Liu, Lijuan Wang, Hongzhi Li, and Yun Fu.  Rethinking classification and localization for object detection.  CVPR, pages 10186–10195, 2020.
  * [44] Saining Xie, Ross Girshick, Piotr Dollar, Zhuowen Tu, and Kaiming He.  Aggregated residual transformations for deep neural networks.  arXiv preprint arXiv:1611.05431, 2016.
  * [45] Jiahui Yu, Yuning Jiang, Zhangyang Wang, Zhimin Cao, and Thomas Huang.  Unitbox: An advanced object detection network.  Proceedings of the 24th ACM international conference on Multimedia, pages 516–520, 2016.
  * [46] Hongkai Zhang, Hong Chang, Bingpeng Ma, Naiyan Wang, and Xilin Chen.  Dynamic r-cnn: Towards high quality object detection via dynamic training.  ECCV, pages 260–275, 2020.
  * [47] Shifeng Zhang, Cheng Chi, Yongqiang Yao, Zhen Lei, and Stan Z. Li.  Bridging the gap between anchor-based and anchor-free detection via adaptive training sample selection.  CVPR, pages 9759–9768, 2020.
  * [48] Zhaohui Zheng, Ping Wang, Wei Liu, Jinze Li, Rongguang Ye, and Dongwei Ren.  Distance-iou loss: Faster and better learning for bounding box regression.  AAAI, 34(07):12993–13000, 2020.
  * [49] Xingyi Zhou, Dequan Wang, and Philipp Krähenbühl.  Objects as points.  In arXiv preprint arXiv:1904.07850, 2019.
  * [50] Chenchen Zhu, Yihui He, and Marios Savvides.  Feature selective anchor-free module for single-shot object detection.  CVPR, pages 840–849, 2019.
  * [51] Xizhou Zhu, Weijie Su, Lewei Lu, Bin Li, Xiaogang Wang, and Jifeng Dai.  Deformable detr: Deformable transformers for end-to-end object detection.  ICLR, 2021.


# Geodesic packing in graphs

Paul Manuela Boštjan Brešarb,c Sandi Klavžarb,c,d

###### Abstract

A geodesic packing of a graph $G$ is a set of vertex-disjoint maximal
geodesics. The maximum cardinality of a geodesic packing is the geodesic
packing number ${{\rm gpack}}(G)$. It is proved that the decision version of
the geodesic packing number is NP-complete. We also consider the geodesic
transversal number, ${{\rm gt}}(G)$, which is the minimum cardinality of a set
of vertices that hit all maximal geodesics in $G$. While ${\rm gt}(G)\geq{\rm
gpack}(G)$ in every graph $G$, the quotient ${\rm gt}(G)/{\rm gpack}(G)$ is
investigated. By using the rook’s graph, it is proved that there does not
exist a constant $C<3$ such that $\frac{{\rm gt}(G)}{{\rm gpack}(G)}\leq C$
would hold for all graphs $G$. If $T$ is a tree, then it is proved that ${\rm
gpack}(T)={\rm gt}(T)$, and a linear algorithm for determining ${\rm
gpack}(T)$ is derived. The geodesic packing number is also determined for the
strong product of paths.

a Department of Information Science, College of Life Sciences, Kuwait
University, Kuwait

<EMAIL_ADDRESS>

b Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia

<EMAIL_ADDRESS>

c Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia

d Faculty of Mathematics and Physics, University of Ljubljana, Slovenia

<EMAIL_ADDRESS>

Keywords: geodesic packing; geodesic transversal; computational complexity;
tree; diagonal grid

AMS Subj. Class.: 05C69; 05C12; 05C85

##  1 Introduction

Pairs of covering-packing problems, known also as dual min-max invariant
problems [2], are important topics in graph theory and in combinatorics. The
max independent set problem and the min vertex cover problem is an appealing
example [3]. Another well-known example is the max matching problem versus the
min edge cover problem [6]. Examples from combinatorial optimization are the
min set cover problem & the max set packing problem, and the bin covering &
bin packing problem [8]. In this paper, we identify a new dual min-max pair:
the geodesic transversal problem and the geodesic packing problem. The first
one was recently independently investigated in [13, 15], here we complement
these studies by considering the geodesic packing problem.

A geodesic (i.e., a shortest path) in a graph $G$ is maximal if it is not
contained (as a subpath) in any other geodesic of $G$. A set $S$ of vertices
of $G$ is a geodesic transversal of $G$ if every maximal geodesic of $G$
contains at least one vertex of $S$. When $s\in S$ is contained in a maximal
geodesic $P$ we say that vertex $s$ hits or covers $P$. The geodesic
transversal number of $G$, ${\rm gt}(G)$, is the minimum cardinality of a
geodesic transversal of $G$. A geodesic packing of a graph $G$ is a set of
vertex-disjoint maximal geodesics in $G$. The geodesic packing number, ${\rm
gpack}(G)$, of $G$ is the maximum cardinality of a geodesic packing of $G$,
and the geodesic packing problem of $G$ is to determine ${\rm gpack}(G)$. By a
${\rm gpack}$-set of $G$ we mean a geodesic packing of size ${\rm gpack}(G)$.

Let us mention some related concepts. A packing of a graph often means a set
of vertex-disjoint (edge-disjoint) isomorphic subgraphs, that is, the
$H$-packing problem for an input graph $G$ is to find the largest number of
its disjoint subgraphs that are isomorphic to $H$. In particular, the problem
has been investigated for different types of paths. For instance, Akiyama and
Chvátal [1] considered the problem from algorithmic point of view when $H$ is
a path of fixed length. A survey on efficient algorithms for vertex-disjoint
(as well as edge-disjoint) Steiner trees and paths packing problems in planar
graphs was given in [16]. Dreier et al. [4] have studied the complexity of
packing edge-disjoint paths where the paths are restricted to lengths $2$ and
$3$. In [11] edge-disjoint packing by stars and edge-disjoint packing by
cycles were studied.

In the rest of this section we first recall some notions needed in the rest of
the paper. In the next section it is first proved that the geodesic packing
problem is NP-complete. After that we investigate the quotient ${\rm
gt}(G)/{\rm gpack}(G)$. We first prove that ${\rm
gt}(K_{n}\,\square\,K_{n})=n^{2}-2n+2$ and use this result to demonstrate that
there does not exist a constant $C<3$ such that $\frac{{\rm gt}(G)}{{\rm
gpack}(G)}\leq C$ would hold for all graphs $G$. In Section 3 we consider the
geodesic packing number of trees and prove that for a tree $T$ we have ${\rm
gpack}(T)={\rm gt}(T)$. A linear algorithm for determining ${\rm gpack}(T)$ is
also derived. In the subsequent section the geodesic packing number is
determined for the strong product of paths, while the paper is concluded with
some closing remarks.

Let $G=(V(G),E(G))$ be a graph. The order of $G$ will be denoted by $n(G)$. A
path on consecutive vertices $a_{1},a_{2}\ldots,a_{k}$ will be denoted by
$a_{1}a_{2}\ldots a_{k}$. If $n$ is a positive integer $n$, then let
$[n]=\\{1,\ldots,n\\}$. The Cartesian product $G\,\square\,H$ of graphs $G$
and $H$ is the graph with the vertex set $V(G)\times V(H)$ and edges
$(g,h)(g^{\prime},h^{\prime})$, where either $g=g^{\prime}$ and
$hh^{\prime}\in E(H)$, or $h=h^{\prime}$ and $gg^{\prime}\in E(G)$. The strong
product $G\,\boxtimes\,H$ is obtained from $G\,\square\,H$ by adding, for
every edge $gg^{\prime}\in E(G)$ and every edge $hh^{\prime}\in E(H)$, an edge
between the vertices $(g,h)$ and $(g^{\prime},h^{\prime})$ and another edge
between the vertices $(g,h^{\prime})$ and $(g^{\prime},h)$.

##  2 Preliminary results and NP-completeness

We start by showing NP-completeness of the geodesic packing problem which is
formally defined as follows.

Geodesic Packing Problem
Input: A graph $G$ and a positive integer $k$. Question: Does there exist a
set of $k$ vertex-disjoint maximal geodesics in $G$?

For our reduction we use the concept of the induced path partition.
Computationally, given a graph $G$ and a positive integer $k$, the
MaxInduced$P_{k}$Packing Problem seeks for a maximum number of vertex-disjoint
induced paths $P_{k}$. Saying that a set of vertex-disjoint induced paths on
$k$ vertices is an induced $P_{k}$-packing of $G$, the problem is thus to
maximize the cardinality of an induced $P_{k}$-packing. By [14, Theorem 3.1]
we know that MaxInduced$P_{3}$Packing Problem is NP-hard on bipartite graphs
with maximum degree $3$.

Let $G$ be a graph with $V(G)=\\{x_{1},\ldots,x_{n}\\}$. Then the derived
graph $G^{\prime}$ is defined as follows: $V(G^{\prime})=V(G)\cup\\{x,y,z\\}$
and $E(G^{\prime})=E(G)\cup\\{xz,zy\\}\cup\\{zx_{i}:\,i\in[n]\\}$. Without any
possibility of confusion, we denote by $G$ also the subgraph of $G^{\prime}$
induced by the vertices of the derived graph $G$.

######  Lemma 2.1.

A set $\Psi$ of vertex-disjoint induced paths $P_{3}$ in $G$ is an induced
$P_{3}$-packing of $G$ if and only if $\Psi\cup\\{(x,z,y)\\}$ is a geodesic
packing of the derived graph $G^{\prime}$.

###### Proof.

Note that all maximal geodesics in $G^{\prime}$ are of length $2$. In
particular, the path $P:xyz$ is a maximal geodesic, and every induced path
$P_{3}$ in $G$ is a maximal geodesic in $G^{\prime}$. The statement of the
lemma now follows. ∎

From Lemma 2.1 we also infer that ${\rm
gpack}(G^{\prime})=1+pack_{ind}^{3}(G)$, where we denote by
$pack_{ind}^{k}(G)$ the maximum size of an induced $P_{k}$-packing in $G$.
Now, turning back out attention to the decision versions of the problem, it is
easy to see that a polynomial-time algorithm to resolve Geodesic Packing
Problem in general graphs would imply that there is a polynomial time
algorithm to resolve the MaxInduced$P_{3}$Packing Problem in bipartite graphs
with maximum degree $3$ (taking $G$ as such a graph). We have thus derived the
desired computational complexity result.

######  Theorem 2.2.

Geodesic Packing Problem is NP-complete.

By Theorem 2.2 it is of interest to bound the geodesic packing number and to
determine it for specific families of graphs. The following straightforward
upper bound is useful.

######  Lemma 2.3.

Let $d$ be the length of a shortest maximal geodesic of a graph $G$. Then,
${\rm gpack}(G)\leq\lfloor n(G)/(d+1)\rfloor$.

Given a set of vertex-disjoint maximal geodesics, each geodetic transversal
clearly hits each of the paths by at least one private vertex of the path.
This fact in particular implies the following upper bound.

######  Lemma 2.4.

If $G$ is a graph, then ${\rm gpack}(G)\leq{\rm gt}(G)$.

It is clear that ${\rm gpack}(P_{n})=1={\rm gt}(P_{n})$ as well as ${\rm
gpack}(K_{1,n})=1={\rm gt}(K_{1,n})$, hence the bound of Lemma 2.4 is sharp.
On the other hand, the value ${\rm gt}(G)$ can be arbitrarily bigger than
${\rm gpack}(G)$. For instance, ${\rm gpack}(K_{n})=\lfloor\frac{n}{2}\rfloor$
and ${\rm gt}(K_{n})=n-1$. Observe also that in $K_{n,n}$, $n\geq 2$, every
maximal geodesic is of length $2$, hence ${\rm
gpack}(K_{n,n})=\lfloor\frac{2n}{3}\rfloor$, while on the other hand ${\rm
gt}(K_{n,n})=n$. However, we do not know whether the ratio of the two
invariants is bounded and pose this as a problem.

######  Problem 2.5.

Is there an absolute constant $C$ such that $\frac{{\rm gt}(G)}{{\rm
gpack}(G)}\leq C$, for all graphs $G$?

The example of complete graphs shows that if the constant $C$ in Problem 2.5
exists, it cannot be smaller than $2$. To show that it actually cannot be
smaller than $3$, consider the rook’s graphs [10] that can be described as the
Cartesian product of two complete graphs or, equivalently, as the line graphs
of complete bipartite graphs [9].

######  Proposition 2.6.

If $n\geq 1$, then ${\rm gt}(K_{n}\,\square\,K_{n})=n^{2}-2n+2$.

###### Proof.

Set $R_{n}=K_{n}\,\square\,K_{n}$, and note that vertices of $R_{n}$ can be
presented in the Cartesian $n\times n$ grid such that two vertices are
adjacent if and only if they belong to the same row or the same column.

For $n=1$, the statement is clear, so let $n\geq 2$. Note that maximal
geodesics $P$ in $R_{n}$ are of length $2$ and consist of three vertices,
which can be described as follows: $(g,h)\in V(P)$, and there is a vertex
$(g^{\prime},h)\in V(P)$ in the same column as $(g,h)$ and a vertex
$(g,h^{\prime})\in V(P)$ that is in the same row as $(g,h)$. Let $S$ be the
complement of a (smallest) ${\rm gt}$-set of $R_{n}$. Hence $S$ contains no
maximal geodesics as just described.

First, we prove that $|S|\leq 2n-2$. Let $S_{i}$ be the set of vertices in $S$
that belong to the $i^{\rm th}$ row of $R_{n}$. Due to symmetry, we may assume
that rows are ordered in such a way that $|S_{1}|\geq\cdots\geq|S_{n}|$. Note
that $|S_{1}|=1$, implies $|S|\leq n$ and we are done. Hence, let $|S_{1}|\geq
2$. Note that in the column in which there is a vertex of $S_{1}$ there are no
other vertices of $S$, and the same holds for every row $S_{i}$ having more
than one vertex in $S$. Let $k\geq 1$ be the number of rows in which there are
more than two vertices in $S$, That is, in $S_{i}$, $i\in[k]$, we have
$|S_{i}|\geq 2$, but if $|S_{j}|>0$, where $j>k$, then $|S_{j}|=1$. Let $C$ be
the set of columns in which there are vertices from the sets $S_{i}$, where
$i\in[k]$. Note that there are $|C|$ vertices of $S$ in these columns. Since
in the remaining columns there are at most $n-k$ vertices from $S$ (because in
each of the remaining rows there is at most one vertex in $S$), we altogether
get $|S|\leq|C|+n-k$. Now, if $|C|=n$, then $|S|=n$ and we are done.
Otherwise, $|S|\leq|C|+n-k\leq(n-1)+(n-1)=2n-2$. To see that $|S|=2n-2$, take
$k=1$ with $|S_{1}|=n-1$, and add $n-1$ vertices in the last column to $S$. ∎

Since all maximal geodesics in $K_{n}\,\square\,K_{n}$ are of length $2$,
Lemma 2.3 implies that ${\rm
gpack}(K_{n}\,\square\,K_{n})\leq\frac{n^{2}}{3}$. We can thus estimate as
follows:

$\displaystyle\frac{{\rm gt}(K_{n}\,\square\,K_{n})}{{\rm
gpack}(K_{n}\,\square\,K_{n})}$
$\displaystyle\geq\frac{3(n^{2}-2n+2)}{n^{2}}=3\left(1-\frac{2}{n}+\frac{2}{n^{2}}\right)\,.$

Letting $n$ to infinity we have shown that in case the constant $C$ from
Problem 2.5 exists, it cannot be smaller than $3$.

In rook’s graphs $K_{n}\,\square\,K_{n}$, $n\geq 2$, every maximal geodesic is
of length $2={\rm diam}(K_{n}\,\square\,K_{n})$. More generally, a graph $G$
is uniform geodesic if every maximal geodesic in $G$ is of length ${\rm
diam}(G)$. Complete graphs, cycles, and paths are simple additional families
of uniform geodesic graphs. The fact that rook’s graphs are uniform geodesic
generalizes as follows.

######  Proposition 2.7.

If $G_{1},\ldots,G_{r}$, $r\geq 1$, are uniform geodesic graphs, then the
product $G_{1}\,\square\,\cdots\,\square\,G_{r}$ is also a uniform geodesic
graph.

###### Proof.

The result clearly holds for $r=1$. Moreover, by the associativity of the
Cartesian product, it suffices to prove the lemma for two factors. Let hence
$P$ be an arbitrary maximal geodesic in $G\,\square\,H$. Then the projections
$P_{G}$ and $P_{H}$ of $P$ on $G$ and on $H$ are geodesics in $G$ and $H$,
respectively. If $P_{G}$ is not maximal in $G$, then $P_{G}$ can be extended
to a longer geodesic in $G$, but then also $P$ can be extended to a longer
geodesic in $G\,\square\,H$, a contradiction. So $P_{G}$ and $P_{H}$ are
maximal geodesics in $G$ and $H$, respectively. By our assumption this means
that the lengths of $P_{G}$ and $P_{H}$ are ${\rm diam}(G)$ and ${\rm
diam}(H)$, respectively. As the distance function is additive in Cartesian
products, it follows that the length of $P$ is ${\rm diam}(G)+{\rm
diam}(H)={\rm diam}(G\,\square\,H)$. ∎

Proposition 2.7, Lemma 2.3, and the fact that the diameter is also additive on
Cartesian products, yield the following result.

######  Corollary 2.8.

If $G_{1},\ldots,G_{r}$, $r\geq 1$, are uniform geodesic graphs, then

${\rm
gpack}(G_{1}\,\square\,\cdots\,\square\,G_{r})\leq\left\lfloor\frac{n(G_{1})\cdots
n(G_{r})}{{\rm diam}(G_{1})+\cdots+{\rm diam}(G_{r})+1}\right\rfloor\,.$

##  3 Trees

In this section we derive an efficient algorithm to obtain the geodesic
packing number of an arbitrary tree. The approach used is in part similar to
the approach from [13] to determine the geodetic transversal number of a tree.

Let $G$ be a graph, let $u\in V(G)$ be a vertex of degree $2$, and let $x$ and
$y$ be the neighbors of $u$. If $G^{\prime}$ is the graph obtained from $G$ be
removing the vertex $u$ and adding the edge $xy$, then we say that
$G^{\prime}$ is obtained from $G$ by smoothing the vertex $u$. Let further
${\rm SM}(G)$ denote the graph obtained from $G$ by smoothing all the vertices
of $G$ of degree $2$. Since the smoothing operation preserves the degree of
vertices, ${\rm SM}(G)$ is well-defined, that is, unique up to isomorphism. It
was proved in [13, Lemma 4.2] that ${\rm gt}(T)={\rm gt}({\rm SM}(T))$ in any
tree $T$. We prove a similar result for the packing invariant.

######  Lemma 3.1.

If $T$ is a tree, then ${\rm gpack}(T)={\rm gpack}({\rm SM}(T))$.

###### Proof.

Note that each maximal geodesic in a tree connects two leaves of the tree. Let
$\Psi_{T}$ be a largest geodesic packing in $T$. Its elements can thus be
represented by pairs of leaves that are endvertices of the corresponding
geodesics. Note that a maximal geodesic in $\Psi_{T}$ from which we remove all
vertices of degree $2$ becomes a maximal geodesic in ${\rm SM}(T)$. Thus the
same pairs of leaves can be used in ${\rm SM}(T)$ to represent the maximal
geodesics by its end-vertices. We denote by ${\rm SM}(\Psi_{T})$ the resulting
set of maximal geodesics in ${\rm SM}(T)$. Since any two geodesics
$g_{1},g_{2}\in\Psi_{T}$ are disjoint, so are also the corresponding geodesics
in ${\rm SM}(\Psi_{T})$. This implies that ${\rm gpack}(T)\leq{\rm gpack}({\rm
SM}(T))$. The reversed inequality can be proved in a similar way. Notably,
since the maximal geodesics in ${\rm SM}(T)$ have two leaves of ${\rm SM}(T)$
as its end-vertices, the same two leaves are end-vertices of a maximal
geodesic in $T$. It is clear that the resulting maximal geodesics in $T$ are
also mutually vertex-disjoint, and thus together form a geodesic packing in
$T$ of cardinality ${\rm gpack}({\rm SM}(T)$. Thus, ${\rm gpack}(T)\geq{\rm
gpack}({\rm SM}(T))$. ∎

Lemma 3.1 does not hold for an arbitrary graph $G$. See Fig. 1, where a graph
$G$ is shown for which we have ${\rm gpack}(G)=4$ and ${\rm gpack}({\rm
SM}(G))=3$. Pairs of endvertices of maximal geodesics are marked by distinct
colors.

Figure 1: A graph $G$ with ${{\rm gpack}}(G)=4$, and ${\rm SM}(G)$ with ${{\rm
gpack}}({\rm SM}(G))=3$.

A support vertex in a tree is a vertex adjacent to a leaf. An end support
vertex is a support vertex that has at most one non-leaf neighbor. It is easy
to see that an end support vertex does not lie between two end support
vertices. In addition, every tree on at least two vertices contains an end
support vertex (see, for instance, [13]). In [13, Lemma 4.3] the following
result was proved.

######  Lemma 3.2.

[13] Let $T$ be a tree with no vertices of degree $2$. Let $u$ be an end
support vertex of $T$ and $u_{1},\ldots,u_{s}$ the leaves adjacent to $u$.
Then ${\rm gt}(T)={\rm gt}(T-\\{u,u_{1},\ldots,u_{s}\\})+1$. Moreover, there
exists a gt-set $S$ of $T$ such that $u\in S$.

We prove a result parallel to Lemma 3.2 concerning the geodesic packing
number.

######  Lemma 3.3.

Let $T$ be a tree with no vertices of degree $2$. Let $u$ be an end support
vertex of $T$ and $u_{1},\ldots,u_{s}$ the leaves adjacent to $u$. Then ${\rm
gpack}(T)={\rm gpack}(T-\\{u,u_{1},\ldots,u_{s}\\})+1$. Moreover, there exists
a ${\rm gpack}$-set $\Psi$ of $T$ such that $u_{1}uu_{2}\in\Psi$.

###### Proof.

Since $T$ has no vertices of degree $2$, the end support vertex $u$ is
adjacent to at least two leaves, that is, $s\geq 2$. If $T$ is a star, and
hence $u$ being the center of it, then the assertion of the lemma is clear. In
the rest of the proof we may thus assume that $u$ has at least one non-leaf
neighbor, and since $u$ is an end support vertex, it has only one non-leaf
neighbor. We denote the latter vertex by $w$, and let $T^{\prime}$ be the
component of $T-u$ that contains the vertex $w$.

Let $\Psi^{\prime}$ be a ${\rm gpack}$-set of $T^{\prime}$. Since
$u_{1}uu_{2}$ is a maximal geodesic in $T$, and every maximal geodesic in
$T^{\prime}$ is a maximal geodesic also in $T$, we infer that
$\Psi^{\prime}\cup\\{u_{1}uu_{2}\\}$ is a geodesic packing of $T$. Hence ${\rm
gpack}(T)\geq{\rm gpack}(T^{\prime})+1$.

Note that there can be at most one maximal geodesic in a geodesic packing of
$T$ that contains vertex $u$. In addition, there is at least one geodesic that
contains $u$ if a geodesic packing of $T$ is of maximum cardinality (for
otherwise, one could add the geodesic $u_{1}uu_{2}$ and make it of larger
cardinality, which is a contradiction). Now, let $\Psi$ be a ${\rm gpack}$-set
of $T$ and let $P\in\Psi$ be the geodesic that contains $u$. It is easy to see
that all maximal geodesics in $\Psi\setminus\\{P\\}$ belong to $T^{\prime}$
and are also pairwise vertex-disjoint maximal geodesics of $T^{\prime}$. Hence
${\rm gpack}(T^{\prime})\geq{\rm gpack}(T)-1$, and we are done. ∎

Combining the facts that ${\rm gpack}(K_{2})=1={\rm gt}(K_{2})$, that in any
tree $T$ we have ${\rm gt}(T)={\rm gt}({\rm SM}(T))$ and ${\rm gpack}(T)={\rm
gpack}({\rm SM}(T))$, and using Lemmas 3.2 and 3.3, we deduce the following
result.

######  Theorem 3.4.

If $T$ is a tree, then ${\rm gpack}(T)={\rm gt}(T)$.

Using the lemmas from this section, we can now present an algorithm that
constructs a ${\rm gpack}$-set of an arbitrary tree $T$. Note that a ${\rm
gpack}$-set of $T$ is uniquely determined by pairs of endvertices of its
maximal geodesics, and the outcome of the algorithm is the set of such
(ordered) pairs.

Input: A tree $T$.

Output: A ${\rm gpack}$-set $\Psi$, represented by pairs of end-vertices.

1

2 $\Psi=\emptyset$

3 $T={\rm SM}(T)$

4 while  _$n(T)\geq 3$_ do

5 identify an end support vertex $p$ of ${\rm SM}(T)$, and its leaf-neigbors
$u_{1},u_{2}$

6 $\Psi=\Psi\cup\\{(u_{1},u_{2})\\}$

7 $T=T-\\{p,u_{1},\ldots,u_{t}\\}$, where $u_{1},\ldots,u_{t}$ are the leaf
neighbors of $p$

8 $T={\rm SM}(T)$

9

10if  _$n(T)=2$_ then

11 $\Psi=\Psi\cup V(T)$

Algorithm 1 ${\rm gpack}$-set of a tree

######  Theorem 3.5.

Given a tree $T$, Algorithm 1 returns the set of pairs of end vertices of
maximal geodesics of a ${\rm gpack}$-set of $T$ in linear time.

The correctness of Algorithm 1 follows from Lemmas 3.1 and 3.3. The time
complexity of the algorithm is clearly linear. For the running time of the
algorithm, in Step 7, there is nothing to be done if $T$ is a star. Otherwise,
the unique non-leaf neighbor of the vertex $p$ selected in Step 4 is the only
vertex for which we need to check whether the smoothing operation is required.

##  4 Diagonal grids

Diagonal grids are strong products of paths [9]. If a diagonal grid is the
strong product of $r$ paths, then it is called an $r$-dimensional diagonal
grid. By definition, the $r$-dimensional grid
$P_{d_{1}}\,\square\,\cdots\,\square\,P_{d_{r}}$ is a spanning subgraph of
$P_{d_{1}}\,\boxtimes\,\cdots\,\boxtimes\,P_{d_{r}}$, cf. Fig. 2. The edges of
$P_{d_{1}}\,\square\,\cdots\,\square\,P_{d_{r}}$ (considered as a subgraph of
$P_{d_{1}}\,\boxtimes\,\cdots\,\boxtimes\,P_{d_{r}}$) are called Cartesian
edges of $P_{d_{1}}\,\boxtimes\,\cdots\,\boxtimes\,P_{d_{r}}$, the other edges
are diagonal edges. We say that a geodesic consisting of only Cartesian edges
is a Cartesian geodesic of
$P_{d_{1}}\,\boxtimes\,\cdots\,\boxtimes\,P_{d_{r}}$. In the rest we will
assume that the vertices of a path on $r$ vertices are integers $1,\ldots,r$,
and if $x\in V(P_{d_{1}}\,\boxtimes\,\cdots\,\boxtimes\,P_{d_{r}})$, then we
will use the notation $x=(x_{1},\ldots,x_{r})$.

Figure 2: (a) A $2$-dimensional grid $P_{5}\,\square\,P_{7}$ and (b) a
$2$-dimensional diagonal grid $P_{5}\,\boxtimes\,P_{7}$

######  Lemma 4.1.

If $P$ is a maximal geodesic in $P_{d_{1}}\boxtimes\cdots\boxtimes P_{d_{r}}$,
where $r\geq 2$, and $d_{1},\ldots,d_{r}\geq 2$, then
$n(P)\in\\{d_{1},\ldots,d_{r}\\}$.

###### Proof.

Let $P$ be an arbitrary geodesic of $G=P_{d_{1}}\boxtimes\cdots\boxtimes
P_{d_{r}}$ of length $\ell\geq 2$, so that $n(P)=\ell+1$. Let $xx^{\prime}$
and $yy^{\prime}$ be the first and the last edge of $P$, where $x$ and
$y^{\prime}$ are the first and the last vertex of $P$, respectively. It is
possible that $x^{\prime}=y$. Then
$\ell=d_{G}(x,y^{\prime})=1+d_{G}(x^{\prime},y)+1$. (Note that if
$x^{\prime}=y$, then $d_{G}(x^{\prime},y)=0$.)

Since
$d_{G}(x,y^{\prime})=\max\\{|x_{1}-y_{1}^{\prime}|,\ldots,|x_{r}-y_{r}^{\prime}|\\}$,
we may without loss of generality assume (having in mind that the strong
product operation is commutative) that
$\ell=d_{G}(x,y^{\prime})=|x_{1}-y_{1}^{\prime}|$. We now claim that
$y_{1}\neq y_{1}^{\prime}$ and suppose on the contrary that
$y_{1}=y_{1}^{\prime}$. Using the facts that
$d_{G}(x^{\prime},y)=\max\\{|x_{1}^{\prime}-y_{1}|,\ldots,|x_{r}^{\prime}-y_{r}|\\}$,
$|x_{1}-y_{1}^{\prime}|=\ell$, $|x_{1}-x_{1}^{\prime}|\leq 1$, and
$y_{1}=y_{1}^{\prime}$, we get that $|x_{1}^{\prime}-y_{1}|\geq\ell-1$.
Consequently, $d_{G}(x^{\prime},y)\geq\ell-1$, which in turn implies that

$\ell=d_{G}(x,y^{\prime})=1+d_{G}(x^{\prime},y)+1\geq 1+(\ell-1)+1=\ell+1\,,$

a contradiction. We have thus proved that if
$d_{G}(x,y^{\prime})=|x_{1}-y_{1}^{\prime}|$, then $y_{1}\neq y_{1}^{\prime}$.
Let us emphasize that $P$ was assumed to be an arbitrary geodesic.

Let now $P$ be a maximal geodesic in $G$ and use the same notation as above.
Assume again wlog that $\ell=d_{G}(x,y^{\prime})=|x_{1}-y_{1}^{\prime}|$. If
$uv$ is an arbitrary edge of $P$ which is different from $xx^{\prime}$, then
the above claim asserts that $u_{1}\neq v_{1}$. Since
$\ell=d_{G}(x,y^{\prime})=|x_{1}-y_{1}^{\prime}|$ it follows that the first
coordinates of the vertices of $P$ are $\ell+1$ consecutive integers
$i,i+1,\ldots,i+\ell$. If $i>1$, then adding the edge between $x$ and the
vertex $(i-1,x_{2},\ldots,x_{r})$ yields a geodesic which strictly contains
$P$, a contradiction. Hence $i=1$. By a parallel argument we get that
$i+\ell=d_{1}$. We conclude that $n(P)=d_{1}$. ∎

From the proof of Lemma 4.1 we can deduce also the following.

######  Lemma 4.2.

Let $G=P_{d_{1}}\,\boxtimes\,\cdots\,\boxtimes\,P_{d_{r}}$, where $r\geq 2$
and $d_{i}\geq 2$ for $i\in[r]$. If $x=(x_{1},\ldots,x_{i-1},1,x_{i+1},\ldots
x_{r})$ and $y=(y_{1},\ldots,y_{i-1},d_{i},y_{i+1},\ldots y_{r})$ are vertices
of $G$, then there exists a maximal $x,y$-geodesic in $G$ of length $d_{i}-1$.

We are now in position to determine the geodesic packing number of diagonal
grids.

######  Theorem 4.3.

If $r\geq 2$ and $2\leq d_{1}\leq\min\\{d_{2},\ldots,d_{r}\\}$, then

${\rm gpack}(P_{d_{1}}\,\boxtimes\,\cdots\,\boxtimes\,P_{d_{r}})=d_{2}\cdot
d_{3}\cdots d_{r}\,.$

###### Proof.

Set $G=P_{d_{1}}\,\boxtimes\,\cdots\,\boxtimes\,P_{d_{r}}$. For each vector
$(i_{2},\ldots,i_{r})$, where $i_{j}\in[d_{j}]$, $j\in\\{2,\ldots,r\\}$, let
$P_{i_{2},\ldots,i_{r}}$ be the path

$(1,i_{2},\ldots,i_{r})(2,i_{2},\ldots,i_{r})\ldots(d_{1},i_{2},\ldots,i_{r})\,.$

By Lemma 4.2, $P_{i_{2},\ldots,i_{r}}$ is a maximal geodesic of $G$. Hence the
set

$\\{P_{i_{2},\ldots,i_{r}}:\ i_{j}\in[d_{j}],j\in\\{2,\ldots,r\\}\\}$

is a geodesic packing of $G$. Its size is $d_{2}\cdot d_{3}\cdots d_{r}$ which
means that hence ${\rm gpack}(G)\geq d_{2}\cdot d_{3}\cdots d_{r}$.

From Lemma 4.1 we know that a shortest maximal geodesic of $G$ is of length
$d_{1}-1$. This implies, by using Lemma 2.3, that ${\rm gpack}(G)\leq
n(G)/d_{1}=d_{2}\cdot d_{3}\cdots d_{r}$ and we are done. ∎

##  5 Conclusions

We have introduced the geodesic packing problem which is a min-max dual
invariant to the earlier studied geodesic transversal problem. We have settled
the complexity status of the geodesic packing problem for general graphs and
arbitrary trees, and determined the geodesic packing number for several
classes of graphs. We have proved that ${\rm gpack}(T)={\rm gt}(T)$ for
arbitrary trees $T$. It is not known that ${\rm gpack}(G)={\rm gt}(G)$ when
$G$ is a cactus graph or block graphs. There are numerous open problems that
are left for future investigation. One open problem is explicitly stated in
Problem 2.5. Other natural extensions of our research would be to study the
geodesic packing number for general strong products or other graph products
and the general packing number for intersection graphs such as interval
graphs, circular arc graphs or chordal graphs.

## Acknowledgments

This work was supported and funded by Kuwait University, Research Project No.
(FI01/22).

## Conflict of interest

The authors declare that they have no conflict of interest.

## References

  * [1] J. Akiyama, V. Chvátal, Packing paths perfectly, Discrete Math. 85 (1990) 247–255.
  * [2] Y. Azar, N. Buchbinder, H. Chan, S. Chen, I. Cohen, A. Gupta, Z. Huang, N. Kang, V. Nagarajan, J. Naor, D. Panigrahi, Online algorithms for covering and packing problems with convex objectives. 57th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2016, 148–157, IEEE Computer Soc., Los Alamitos, CA, 2016.
  * [3] K. Casel, H. Fernau, M. Khosravian Ghadikolaei, J. Monnot, F. Sikora, Extension of vertex cover and independent set in some classes of graphs, Lecture Notes in Comput. Sci. 11485 (2019) 124–136.
  * [4] J. Dreier, J. Fuchs, T.A. Hartmann, P. Kuinke, P. Rossmanith, B. Tauer H.-L. Wang, The complexity of packing edge-disjoint paths. 14th International Symposium on Parameterized and Exact Computation, Art. No. 10, 16 pp., Leibniz Int. Proc. Inform., 148, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019.
  * [5] D. C. Fisher, S.L. Fitzpatrick, The isometric number of a graph, J. Combin. Math. Combin. Comput. 38 (2001) 97–110.
  * [6] T. Gallai, Über extreme Punkt- und Kantenmengen, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 2 (1959) 133–138.
  * [7] M. Ghorbani, S. Klavžar, H.R. Maimani, M. Momeni, F. Rahimi-Mahid, G. Rus, The general position problem on Kneser graphs and on some graph operations, Discuss. Math. Graph Theory 41 (2021) 1199–1213.
  * [8] P. Hansen, M. Labbé, D. Schindl, Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results, Discrete Opt. 6 (2009) 135–147.
  * [9] R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, FL, 2011.
  * [10] A.J. Hoffman, On the line graph of the complete bipartite graph, Ann. Math. Statist. 35 (1964) 883–885.
  * [11] M. Jiang, G. Xia, Y. Zhang, Edge-disjoint packing of stars and cycles, Theoret. Comput. Sci. 640 (2016) 61–69.
  * [12] P. Manuel, On the isometric path partition problem, Discuss. Math. Graph Theory 41 (2021) 1077–1089.
  * [13] P. Manuel, B. Brešar, S. Klavžar, The geodesic-transversal problem, Appl. Math. Comput. 413 (2022) 126621.
  * [14] J. Monnot, S. Toulouse, The path partition problem and related problems in bipartite graphs, Oper. Res. Lett. 35 (2007) 677–684.
  * [15] I. Peterin, G. Semanišin, On the maximal shortest path cover number, Mathematics 9 (2021) 1592.
  * [16] D. Wagner, Simple algorithms for Steiner trees and paths packing problems in planar graphs, CWI Quarterly 6 (1993) 219–240.