On the hull and interval numbers of oriented graphs J. Ara ujo1 A. K. Maia2 P. P. Medeiros1 and L. Penso3

2025-05-02 0 0 637.83KB 26 页 10玖币

侵权投诉

On the hull and interval numbers of oriented

graphs⋆

J. Ara´ujo1, A. K. Maia2, P. P. Medeiros1, and L. Penso3

1Departamento de Matem´atica, Universidade Federal do Cear´a, Brazil

julio@mat.ufc.br, pedropmed1@gmail.com

2Departamento de Computa¸c˜ao, Universidade Federal do Cear´a, Brazil

karolmaia@ufc.br

3Universit¨at Ulm, Ulm, Germany

lucia.penso@uni-ulm.de

Abstract. In this work, for a given oriented graph D, we study its inter-

val and hull numbers, denoted by −→

in(D) and −→

hn(D), respectively, in the

oriented geodetic, −→

P3and

−→

3convexities. This last one, we believe to be

formally deﬁned and ﬁrst studied in this paper, although its undirected

version is well-known in the literature.

Concerning bounds, for a strongly oriented graph D, and the oriented

geodetic convexity, we prove that −→

hng(D)≤m(D)−n(D) + 2 and that

there is at least one such that −→

hng(D) = m(D)−n(D). We also de-

termine exact values for the hull numbers in these three convexities for

tournaments, which imply polynomial-time algorithms to compute them.

These results allow us to deduce polynomial-time algorithms to compute

−→

hnP3(D) when the underlying graph of Dis split or cobipartite.

Moreover, we provide a meta-theorem by proving that if deciding whether

−→

ing(D)≤kor −→

hng(D)≤kis NP-hard or W[i]-hard parameterized by

k, for some i∈Z∗

+, then the same holds even if the underlying graph

of Dis bipartite. Next, we prove that deciding whether −→

hnP3(D)≤k

or −→

hnP*

3(D)≤kis W[2]-hard parameterized by k, even if Dis acyclic

and its underlying graph is bipartite; that deciding whether −→

hng(D)≤

kis W[2]-hard parameterized by k, even if Dis acyclic; that deciding

whether −→

inP3(D)≤kor −→

inP*

3(D)≤kis NP-complete, even if Dhas

no directed cycles and the underlying graph of Dis a chordal bipartite

graph; and that deciding whether −→

inP3(D)≤kor −→

inP*

3(D)≤kis W[2]-

hard parameterized by k, even if the underlying graph of Dis split.

Finally, also argue that the interval and hull numbers in the −→

P3and

−→

3convexities can be computed in cubic time for graphs of bounded

clique-width by using Courcelle’s theorem.

Keywords: Graph Convexity ·Oriented Graphs ·Hull Number ·Inter-

val Number.

⋆Partly supported by FUNCAP-Pronem 4543945/2016, Funcap 186-155.01.00/21,

CNPq 313153/2021-3.

arXiv:2210.01598v3 [math.CO] 1 Mar 2024

2 Araujo et al.

1 Introduction

Aconvexity space is an ordered pair (V, C), where Vis an arbitrary set and Cis

a family of subsets of V, called convex sets, that satisﬁes:

– (C1) ∅, V ∈ C;

– (C2) For all C′⊆ C, we have TC′∈ C;

– (C3) Every nested union of convex sets is a convex set.

Convexity spaces are a classic topic, studied in diﬀerent branches of math-

ematics. The research of convexities applied to graphs is a more recent topic,

from about 50 years ago. Classical convexity deﬁnitions and results motivated

the deﬁnitions of some graph parameters (Carath´eodory’s number [5], Helly’s

number [16], Radon’s number [15], hull number [21], rank [28], etc.). The com-

plexity aspects related to the determination of the values of those parameters has

been the central issue of several recent works in this ﬁeld. For basic notions on

Graph Theory and Computational Complexity, the reader is referred to [4,6,24].

For graphs, convexity spaces are deﬁned over the vertex set of a given (ori-

ented) graph G. Here, we consider only ﬁnite, simple and non-null graphs. Thus,

we always consider the set of vertices V(G) to be ﬁnite and non-empty and the

set of edges to be ﬁnite. This makes Condition (C3) irrelevant, since any such

union will have a larger set.

To deﬁne a convexity for a graph G, it remains to deﬁne the family C. All

graph convexities studied here are interval convexities, i.e. deﬁned by an interval

function. Given a graph G= (V, E), an interval function I:V×V→2Vis a

function such that {u, v} ⊆ I(u, v) and I(u, v) = I(v, u), for every u, v ∈V(G).

If S⊆V×V, with a slight abuse of notation, we deﬁne I(S) = S(u,v)∈SI(u, v).

We say that C⊆Vis convex (or I-closed) if I(C×C) = C. Let the family Cbe

composed by all I-closed subsets of V. Thus, (V, C) is a convexity space [7,18].

Note that the unitary subsets of V, as well as the set Vitself, are convex. Such

sets will be called trivial convex sets.

Given an undirected graph G= (V, E), when I(u, v) returns the set of

all vertices belonging to some shortest u, v-path (a.k.a. u, v-geodesic), we have

the geodetic convexity [22]. If I(u, v) returns the set of all vertices that lie in

some path on three vertices having uand vas endpoints, then we have the P3-

convexity [34]. In case I(u, v) returns the set vertices that lie in some shortest

(u, v)-path of length two, then we have the P∗

3-convexity [2]. The interval func-

tions in the geodetic, P3and P∗

3convexities are denoted here by Ig(G), IP3(G)

and IP*

3(G), respectively. Some other graph convexities have been studied in the

literature [19].

If (V, C) is a convexity space, the convex hull of S⊆Vwith respect to (V, C)

is the unique inclusion-wise minimum C∈ C containing Sand we denoted it by

HC(S). In the case of an interval convexity (V, C), HC(S) can be obtained by the

interval function Ithat deﬁnes C, for any S⊆V, as follows:

Ik(S) = (S, if k= 0;

I(Ik−1(S)),otherwise.

On the hull and interval numbers of oriented graphs 3

Since we deal with interval convexities deﬁned over a ﬁnite graph G, there

is an integer 0 ≤k≤n(G) such that HC(S) = Sk

i=0 Ii(S) (see [7,18] for details

and further references). The convex hulls of a subset S⊆Vin the geodetic, P3

and P∗

3convexities are denoted by Hg(S), HP3(S) and HP*

3(S).

For each graph convexity, as we have mentioned before, several parameters

have been deﬁned in the literature. We focus in two of them. Given a graph

convexity deﬁned by an interval function Iover the vertex set of a graph G=

(V, E), an interval set (resp. hull set)S⊆Vsatisﬁes that I(S) = V(resp.

H(S) = V). The interval number (resp. hull number) is the cardinality of a

smallest interval set (resp. hull set) S⊆Vof G. The interval numbers in the

geodetic, P3and P∗

3convexities are denoted by ing(G), inP3(G) and inP*

3(G),

respectively. Analogously, the hull number in these convexities are denoted by

hng(G), hnP3(G) and hnP*

3(G). We emphasize that an interval set in the geodetic

convexity is also known as geodetic set and the interval number in this convexity

is also called geodetic number and it is often denoted by gn(G) = ing(G).

1.1 Convexity on oriented graphs

Although graph convexities and their diﬀerent parameters have been extensively

studied in recent years, this topic has not yet been equally investigated consid-

ering directed or oriented graphs.

An oriented graph Dis an orientation of a simple graph G, i.e., Dis obtained

from Gby choosing an orientation (uto vor vto u) for each edge uv of G.

For a given oriented graph D, the following convexities have been studied in

the literature.

The geodetic convexity, that we also refer as −→

g-convexity, over an oriented

graph Dis deﬁned by the interval function −→

Igthat returns, for a pair (u, v)∈

V×V, the set of vertices that lie in any shortest directed (u, v)-path or in

any shortest directed (v, u)-path.

The two-path convexity, which we will more often call −→

P3-convexity, over an

oriented graph Dis deﬁned by the interval function −→

IP3that returns, for a pair

(u, v)∈V×Vthe set of vertices that lie in any directed (u, v)-path of length

two or in any directed (v, u)-path of length two.

The distance-two convexity, to which we refer as −→

3-convexity, over an ori-

ented graph Dis deﬁned by the interval function −→

IP*

3that returns, for a pair

(u, v)∈V×Vthe set of vertices that lie in any shortest directed (u, v)-path

of length two or in any shortest directed (v, u)-path of length two. Note that

thus there is no arc (u, v) in the ﬁrst case, nor (v, u) in the second.

Now, let consider X ∈ {g,P3,P*

3}. A convex set Sin −→

X-convexity will be

denoted as −→

X-convex. The convex hull of a set S⊆V(D) in the −→

X-convexity

is denoted by −→

HX(S). An interval (resp. hull) set in the −→

X-convexity will be

referred as an interval (resp. hull)−→

X-set. The interval and hull numbers in the

−→

X-convexity of an oriented graph Dare denoted here by −→

inX(D) and −→

hnX(D),

respectively.

4 Araujo et al.

It is important to emphasize that as Dis an orientation of a simple graph,

then it cannot have both arcs (u, v) and (v, u), for distinct u, v ∈V(D). Thus,

the parameters in the oriented versions are not equivalent to the undirected ones.

Although the ﬁrst papers related to convexity in graphs study directed graphs

[20,31,37], most of the papers we can ﬁnd in the literature about graph convex-

ities deal with undirected graphs. For instance, the hull and geodetic numbers

with respect to undirected graphs [21,26] were ﬁrst studied in the literature

around a decade before their corresponding directed versions [10,11].

With respect to the directed case, most results in the literature provide

bounds on the maximum and minimum values of −→

hn(D(G)) and −→

gn(D(G)) among

all possible orientations D(G) of a given undirected simple graph G[10,11,23].

It is important to emphasize the results on the parameter hn+(G), the upper

orientable hull number of a simple graph G, since these are the only ones re-

lated to the upper bound we present. Such parameter is deﬁned in [11], as the

maximum value of −→

hn(D) among all possible orientations Dof a simple graph

G, and it is easy to see that hn+(G) = n(G) if and only if there is an orientation

Dof Gsuch that every vertex V(D)\ {v}is convex i.e. v∈V(D) is extreme.

They also compare this parameter with others, such as the lower orientable hull

number (hn-(G)) and the lower and upper orientable geodetic numbers (gn-(G)

and gn+(G) respectively), which are deﬁned analogously.

There are also few results about some related parameters: the forcing hull and

geodetic numbers [9,36], the pre-hull number [35] and the Steiner number [27]

are a few examples.

In [34], the authors provide upper bounds for the parameters rank, Helly

number, Radon number, Carath´eodory number, and hull number when restricted

to multipartite tournaments.

In [3], the authors focus in the hull and interval numbers for the geodetic

convexity in oriented graphs. They ﬁrst present a general upper bound to −→

hng(D),

for any oriented graph D, and present a tight upper bound for a tournament

Tsatisfying −→

hng(T) = 2

3n(T). Then, they use the result in the undirected case

proved in [1] to show that computing the geodetic hull number of an oriented

graph Dis NP-hard even if the underlying graph of Dis a partial cube. Although

they do not emphasize, their reduction builds a strongly oriented graph D. They

also show that deciding whether −→

ing(D)≤kfor an oriented graph Dwhose

underlying graph is bipartite or cobipartite or split is a W[2]-hard problem when

parameterized by k.

Once more, although the authors do not emphasize, their reduction to the

class of bipartite graphs also works for the −→

P3and −→

3convexities as it uses only

paths on three vertices, much are always shortest due to the bipartition, and so

does their reduction to cobipartite graphs for the −→

3convexity. Their reduction

to split graphs uses paths on four vertices, and their reduction to cobipartite

graphs does not hold for the −→

P3as it is has many paths on three vertices that

are not shortest and could be used in the −→

P3.

On the hull and interval numbers of oriented graphs 5

Consequently, by the results in [3], determining whether −→

inP*

3(D)≤kis

W[2]-hard parameterized by keven if the underlying graph Gof Dis bipartite

or cobipartite, and determining whether −→

inP3(D)≤kis W[2]-hard parameter-

ized by keven if the underlying graph Gof Dis bipartite. They also present

polynomial-time algorithms to compute both parameters for any oriented cactus

graph and they present a tight upper bound for the geodetic hull number of an

oriented split graph.

1.2 Our contributions and organization of the paper

We ﬁrst present some basic results concerning the elements of hull and interval

sets at the geodetic, −→

P3and −→

3convexities, in Section 2.

Then dedicate Section 3to the results concerning bounds and equalities for

the oriented hull number. In Section 3.1, for a strongly oriented graph D, we

prove that −→

hng(D)≤m(D)−n(D)+2 and that there is a strongly oriented graph

such that −→

hng(D) = m(D)−n(D). In Section 3.2, we determine exact values

for the hull numbers in the geodetic and −→

3convexities for tournaments. These

formulas imply polynomial-time algorithms for computing these parameters for

this particular case of tournaments. The case of −→

P3was already studied [25].

We present a shorter proof that −→

hnP3(T)≤2 for a given tournament T, and

we use this result to deduce that −→

hnP3(D) can be computed in polynomial time,

whenever the underlying graph of Dis cobipartite or split.

Section 4is devoted to hardness results from the computational complexity

point of view. Section 4.1, we provide a meta-theorem by proving that if deciding

whether −→

ing(D)≤kor −→

hng(D)≤kis NP-hard or W[i]-hard parameterized by

k, for some i∈Z∗

+, then the same holds even if the underlying graph of Dis

bipartite. In the Sections 4.2 and 4.3, we seek to complement the study of [3] from

the computational complexity point of view when restricted to bipartite, split,

or cobipartite graphs. We prove that deciding whether −→

hnP3(D)≤kis W[2]-

hard parameterized by keven if Dis acyclic and the underlying graph of Dis

bipartite. With a slight modiﬁcation in the reduction, we deduce that deciding

whether −→

hng(D)≤kis W[2]-hard parameterized by keven if Dis acyclic. Then,

we prove that deciding whether −→

inP3(D)≤kis NP-complete, even if Dhas

no directed cycles and the underlying graph of Dis a chordal bipartite graph.

Since both results about the hardness of computing −→

hnP3(D) hold for oriented

graphs Dwhose underlying graph is also bipartite, then both results also hold for

−→

hnP*

3(D) and −→

inP*

3(D), respectively. Finally, we also prove that deciding whether

−→

inP3(D)≤kor −→

inP*

3(D)≤kis W[2]-hard when parameterized by k, even if the

underlying graph of Dis split.

Since such parameters are hard to compute for bipartite graphs, a natural

question is to ask whether they can be computed in polynomial time for trees. We

argue in Section 5that interval and hull numbers in the −→

P3and −→

3convexities

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Onthehullandintervalnumbersoforientedgraphs⋆J.Ara´ujo1,A.K.Maia2,P.P.Medeiros1,andL.Penso31DepartamentodeMatem´atica,UniversidadeFederaldoCear´a,Braziljulio@mat.ufc.br,pedropmed1@gmail.com2DepartamentodeComputa¸c˜ao,UniversidadeFederaldoCear´a,Brazilkarolmaia@ufc.br3Universit¨atUlm,Ulm,Germanylucia....

展开>> 收起<<

On the hull and interval numbers of oriented graphs J. Ara ujo1 A. K. Maia2 P. P. Medeiros1 and L. Penso3.pdf

共26页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

On the hull and interval numbers of oriented graphs J. Ara ujo1 A. K. Maia2 P. P. Medeiros1 and L. Penso3

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: