Certifying Induced Subgraphs in Large Graphs Ulrich Meyer1 Hung Tran1 and Konstantinos Tsakalidis2 1Goethe University Frankfurt Germany

2025-04-30 1 0 573.8KB 15 页 10玖币

侵权投诉

Certifying Induced Subgraphs in Large Graphs

Ulrich Meyer1, Hung Tran1, and Konstantinos Tsakalidis2

1Goethe University Frankfurt, Germany

{umeyer,htran}@ae.cs.uni-frankfurt.de

2University of Liverpool, United Kingdom

K.Tsakalidis@liverpool.ac.uk

Abstract. We introduce I/O-optimal certifying algorithms for bipar-

tite graphs, as well as for the classes of split, threshold, bipartite chain,

and trivially perfect graphs. When the input graph is a class member,

the certifying algorithm returns a certiﬁcate that characterizes this class.

Otherwise, it returns a forbidden induced subgraph as a certiﬁcate for

non-membership. On a graph with nvertices and medges, our algorithms

take optimal O(sort(n+m)) I/Os in the worst case or with high prob-

ability for bipartite chain graphs, and the certiﬁcates are returned in

optimal I/Os. We give implementations for split and threshold graphs

and provide an experimental evaluation.

Keywords: certifying algorithm ·graph algorithm ·external memory

1 Introduction

Certifying algorithms [13] ensure the correctness of an algorithm’s output with-

out having to trust the algorithm itself. The user of a certifying algorithm in-

puts xand receives the output ywith a certiﬁcate or witness wthat proves

that yis a correct output for input x. Certifying the bipartiteness of a graph is

a textbook example where the returned witness wis a bipartition of the vertices

(YES-certiﬁcate) or an induced odd-length cycle subgraph, i.e. a cycle of vertices

with an odd number of edges (NO-certiﬁcate).

Emerging big data applications need to process large graphs eﬃciently. Stan-

dard models of computation in internal memory (RAM, pointer machine) do not

capture the algorithmic complexity of processing graphs with size that exceed the

main memory. The I/O model by Aggarwal and Vitter [1] is suitable for studying

large graphs stored in an external memory hierarchies, e.g. comprised of cache,

RAM and hard disk memories. The input data elements are stored in external

memory (EM) packed in blocks of at most Belements and computation is free

in main memory for at most Melements. The I/O-complexity is measured in

I/O-operations (I/Os) that transfer a block from external to main memory and

vice versa. I/O-optimal external memory algorithms for sorting and scanning n

elements take sort(n)=O((n/B) logM/B (n/B)) I/Os and scan(n) = O(n/B)

I/Os, respectively.

arXiv:2210.13057v1 [cs.DS] 24 Oct 2022

2 U. Meyer et al.

1.1 Previous Work

Certifying bipartiteness in internal memory takes time linear in the number

of edges by any traversal of the graph. However, all known external memory

breadth-ﬁrst search [2] and depth-ﬁrst search [4] traversal algorithms take sub-

optimal ω(sort (n+m)) I/Os for an input graph with nvertices and medges.

Heggernes and Kratsch [10] present optimal internal memory algorithms for cer-

tifying whether a graph belongs to the classes of split, threshold, bipartite chain,

and trivially perfect graphs. They return in linear time a YES-certiﬁcate char-

acterizing the corresponding class or a forbidden induced subgraph of the class

(NO-certiﬁcate). The YES- and NO-certiﬁcates are authenticated in linear and con-

stant time, respectively. A straightforward application to the I/O model leads

to suboptimal certifying algorithms since graph traversal algorithms in exter-

nal memory are much more involved and no worst-case eﬃcient algorithms are

known.

1.2 Our Results

We present I/O-optimal certifying algorithms for bipartite,split,threshold,bi-

partite chain, and trivially perfect graphs. All algorithms return in the mem-

bership case, a YES-certiﬁcate wcharacterizing the graph class, or a O(1)-size

NO-certiﬁcate in the non-membership case. As a byproduct, we show how to

eﬃciently certify graph bipartiteness in external memory using standard I/O-

eﬃcient techniques. Additionally, we perform experiments for split and threshold

graphs showing scaling beyond the size of main memory.

2 Preliminaries and Notation

For a graph G= (V, E), let n=|V|and m=|E|denote the number of vertices V

and edges E, respectively. For a vertex v∈Vwe denote by N(v)the neighborhood

of vand by N[v] = N(v)∪ {v}the closed neighborhood of v. The degree deg(v)

of a vertex vis given by deg(v) = |N(v)|. A vertex is called simplicial if N(v)is

a clique and universal if N[v] = V.

Graph Substructures and Orderings The subgraph of Gthat is induced by

a subset A⊆Vof vertices is denoted by G[A]. The substructure (subgraph) of

a cycle on kvertices is denoted by Ckand of a path on kvertices is denoted by

Pk. The substructure 2K2is a graph that is isomorphic to the following constant

size graph: ({a, b, c, d},{ab, cd}).

Henceforth we refer to diﬀerent types of orderings of vertices: an order-

ing (v1, . . . , vn)is a (i) perfect elimination ordering (peo) if viis simplicial

in G[{vi, vi+1, . . . , vn}]for i∈ {1, . . . , n}, and a (ii) universal-in-a-component-

ordering (uco) if viis universal in its connected component in G[{vi, vi+1, . . . , vn}]

for i∈ {1, . . . , n}. For a subset X={v1, . . . , vk}, we call (v1, . . . , vk)anested

neighborhood ordering (nno) if (N(v1)\X)⊆(N(v2)\X)) ⊆. . . ⊆(N(vk)\X).

Certifying Induced Subgraphs in Large Graphs 3

Finally for any ordering, we partition N(vi)into lower and higher ranked neigh-

bors, respectively, L(vi) = {x∈N(vi) : viis ranked lower than x}and H(vi) =

{x∈N(vi) : viis ranked higher than x}.

Graph Representation We assume an adjacency row representation where the

graph G= (V, E)is represented by two arrays P= [ Pi]n

i=1 and E= [ ui]m

i=1.

The neighbors of a vertex viare then given by the vertices at position P[vi]

to P[vi+1]−1in E. We use the adjacency row representation to allow for eﬃ-

cient scanning of G: (i) computing kconsecutive adjacency lists consisting of m

edges requires O(scan(m)) I/Os and (ii) computing the degrees of kconsecutive

vertices requires O(scan(k)) I/Os.

Time-Forward Processing Time-forward processing (TFP) is a generic tech-

nique to manage data dependencies of external memory algorithms [12]. These

dependencies are typically modeled by a directed acyclic graph G= (V, E)where

every vertex vi∈Vmodels the computation of ziand an edge (vi, vj)∈Eindi-

cates that ziis required for the computation of zj.

Computing a solution then requires the algorithm to traverse Gaccording

to some topological order ≺Tof the vertices V. The TFP technique achieves

this in the following way: after zihas been calculated, the algorithm inserts a

message hvj, ziiinto a minimum priority-queue data structure for every succes-

sor (vi, vj)∈Ewhere the items are sorted by the recipients according to ≺T.

By construction, vjreceives all required values ziof its predecessors vi≺Tvj

as messages in the data structure. Since these predecessors already removed

their messages from the data structure, items addressed to vjare currently the

smallest elements in the data structures and thus can be dequeued with a delete-

minimum operation. By using suitable external memory priority-queues [3], TFP

incurs O(sort(k)) I/Os, where kis the number of messages sent.

3 Certifying Graphs Classes in External Memory

3.1 Certifying Split Graphs in External Memory

A split graph is a graph that can be partitioned into two sets of vertices (K, I)

where Kand Iinduce a clique and an independent set, respectively. The par-

tition (K, I)is called the split partition. They are additionally characterized by

the forbidden induced substructures 2K2, C4and C5, meaning that any vertex

subset of a split graph cannot induce these structures [9]. Since split graphs are

a subclass of chordal graphs, there exists a peo of the vertices for every split

graph. In fact, any non-decreasing degree ordering of a split graph is a peo [10].

Our algorithm adapts the internal memory certifying algorithm of Heggernes

and Kratsch [10] to external memory by adopting TFP. As output it either

returns the split partition (K, I)as a YES-certiﬁcate or one of the forbidden

substructures C4, C5or 2K2as a NO-certiﬁcate.

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

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

10 玖币 0人已下载

立即下载

摘要：

CertifyingInducedSubgraphsinLargeGraphsUlrichMeyer1,HungTran1,andKonstantinosTsakalidis21GoetheUniversityFrankfurt,Germany{umeyer,htran}@ae.cs.uni-frankfurt.de2UniversityofLiverpool,UnitedKingdomK.Tsakalidis@liverpool.ac.ukAbstract.WeintroduceI/O-optimalcertifyingalgorithmsforbipar-titegraphs,aswell...

展开>> 收起<<

Certifying Induced Subgraphs in Large Graphs Ulrich Meyer1 Hung Tran1 and Konstantinos Tsakalidis2 1Goethe University Frankfurt Germany.pdf

共15页,预览3页

还剩页未读，继续阅读

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

Certifying Induced Subgraphs in Large Graphs Ulrich Meyer1 Hung Tran1 and Konstantinos Tsakalidis2 1Goethe University Frankfurt Germany

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: