1. Introduction
A graph searching game is a game where searchers (or cops) want to capture a fugitive (or robber) and the fugitive want to escape from the searchers, and they move through a graph for their purpose. Graph searching games have been well-studied [1] [2] [3], since graph searching games have many practical and theoretical applications such as robot motion planning, network security, and artificial intelligence (see e.g. [4] ).
There are several variants of graph searching games such as edge search, node search, and mixed search (see e.g. [5] ) and there are several graph width-parameters such as path-width, tree-width, and branch-width. In the study of graph searching games, it is known that there are some strong connections between graph searching games and graph width parameters, in which the minimum number of searchers (i.e., search number) usually corresponds to the value of width. For example, mixed search number is essentially equivalent to linear-width1 (see [6] [7] ).
The concept of linear tangle was introduced in [7] as an obstruction to the existence of mixed searching strategy: there is a linear tangle of order
iff there is no mixed searching strategy with k searchers, where k is a prefixed integer. From the equivalence, as mentioned above, between mixed search number and linear-width, a linear tangle of order
is an obstruction to being linear-width is at most k (see also [8] ).
The concept of single ideal has been introduced in [9] as an obstruction to linear-width: there is a single ideal of order
iff the linear-width is more than k. Thus, a linear tangle of a large order and a single ideal of a large order are both obstructions to small linear-width, which means that the concepts of linear tangle and single ideal are the same. In this short report, we give an alternative proof of the equivalence between linear tangle and single ideal.
2. Definitions and Notations
In this paper, we consider a pair
rather than graphs, where E is an underlying set and f is a symmetric submodular function on E, and such a pair is called connectivity system (see cf. [10] ). All sets considered in this paper are finite. For an underlying set E and a subset X of E, we denote
by
.
A function
is symmetric submodular if f satisfies the following:
1)
for any
,
2)
for any
.
It is known that a symmetric submodular function f satisfies the following properties [10] : for each
,
1)
and
2)
.
A set X is k-efficient if
. Throughout the paper, f means a symmetric submodular function, k a fixed positive integer, and we assume that
for every
, hence we have
.
Definition 1 ( [7] ). A linear tangle of order
2 on a connectivity system
is a family
of k-efficient subsets of E, satisfying the following axioms:
(L1)
,
(L2) For each k-efficient subset X of E, exactly one of
or
in
,
(L3) If
,
, and
, then
holds.
Definition 2 ( [9] ). A single ideal of order
on a connectivity system
is a family
of k-efficient subsets of E, satisfying the following axioms:
(S1)
,
(S2) If
,
,
, and
, then
holds,
(S3) If
,
,
, and
, then
holds.
We also consider the following additional axiom:
(S4) For each k-efficient subset A of E, exactly one of A or
in
It is shown in [9] that the linear-width of
is at least
if and only if there is a single ideal on
of order
which satisfies (S4).
Since we assume that
for every
, the axioms (L3) and (S3) can be restated, respectively, as follows:
(L3) If
and
, then
holds.
(S3) If
,
, and
, then
holds.
3. Result
Lemma 1. A linear tangle
of order
is a single ideal of order
satisfying the additional axiom (S4).
Proof. From the axioms (L1) and (L2), it is obvious that
satisfies the axioms (S1) and (S4).
We claim that
satisfies the axioms (S2). Suppose, to the contrary, that there exist k-efficient subsets A and B such that
,
, and
. Then, we have
by (L2), and for any
,
holds, but this contradicts the axiom (L3).
Finally, we show that
satisfies the axioms (S3). Suppose, to the contrary, that there exists k-efficient subset
and an element
such that
and
hold. Then, we have
, hence
and
hold, however, this contradicts the axiom (L3).
Lemma 2. A single ideal
of order
satisfying the additional axiom (S4) is a linear tangle of order
.
Proof. From the axioms (S1) and (S4), it is obvious that
satisfies the axioms (L1) and (L2).
We show that
satisfies the axiom (L3). Suppose, to the contrary, that there exists a triple
such that
,
, and
. We choose a triple minimizing
in such triples
. First, we claim that
holds. Since
holds, at least one of
or
is at most k. Without loss of generality, we may assume that
is at most k. Hence, by (S2) from
, we have
. If
, then we have
, however, this contradicts the choice of the triple. Thus, we have shown that
.
Next, we claim that
holds. Suppose if not, that is, if
, then we have
, which implies that
holds, however, this contradicts the axiom (S4). Similarly, we know that
holds.
Now, we know that the triple
consists of a partition of E. Hence, we have
, and from this, it follows that
holds by the axiom (S3). However, this contradicts the axiom (S4).
From lemmas 1 and 2, we have the following theorem.
Theorem 1. Under the assumption that
for every
,
is a linear tangle of order
iff
is a single ideal of order
satisfying the additional axiom (S4).
Acknowledgements
This work was supported by JSPS KAKENHI Grant Number 15K00007.
NOTES
1If a graph has no pendant vertices, the equivalence holds.
2In [7], the order is k rather than k + 1.