Local Density and Its Distributed Approximation

Christiansen, Aleksander Bjørn; van der Hoog, Ivor; Rotenberg, Eva

doi:10.4230/LIPIcs.STACS.2025.25

Local Density and Its Distributed Approximation

Aleksander Bjørn Christiansen

Technical University of Denmark, Lyngby, Denmark Ivor van der Hoog

Technical University of Denmark, Lyngby, Denmark Eva Rotenberg

Technical University of Denmark, Lyngby, Denmark

Abstract

The densest subgraph problem is a classic problem in combinatorial optimisation. Graphs with low maximum subgraph density are often called “uniformly sparse”, leading to algorithms parameterised by this density. However, in reality, the sparsity of a graph is not necessarily uniform. This calls for a formally well-defined, fine-grained notion of density.

Danisch, Chan, and Sozio propose a definition for local density that assigns to each vertex $v$ a value $\rho^{*}(v)$ . This local density is a generalisation of the maximum subgraph density of a graph. I.e., if $\rho(G)$ is the subgraph density of a finite graph $G$ , then $\rho(G)$ equals the maximum local density $\rho^{*}(v)$ over vertices $v$ in $G$ . They present a Frank-Wolfe-based algorithm to approximate the local density of each vertex with no theoretical (asymptotic) guarantees.

We provide an extensive study of this local density measure. Just as with (global) maximum subgraph density, we show that there is a dual relation between the local out-degrees and the minimum out-degree orientations of the graph. We introduce the definition of the local out-degree $\textsl{g}^{*}(v)$ of a vertex $v$ , and show it to be equal to the local density $\rho^{*}(v)$ . We consider the local out-degree to be conceptually simpler, shorter to define, and easier to compute.

Using the local out-degree we show a previously unknown fact: that existing algorithms already dynamically approximate the local density for each vertex with polylogarithmic update time. Next, we provide the first distributed algorithms that compute the local density with provable guarantees: given any $\varepsilon$ such that $\varepsilon^{-1}\in O(\operatorname{poly}n)$ , we show a deterministic distributed algorithm in the LOCAL model where, after $O(\varepsilon^{-2}\log^{2}n)$ rounds, every vertex $v$ outputs a $(1+\varepsilon)$ -approximation of their local density $\rho^{*}(v)$ . In CONGEST, we show a deterministic distributed algorithm that requires $\text{poly}(\log n,\varepsilon^{-1})\cdot 2^{O(\sqrt{\log n})}$ rounds, which is sublinear in $n$ .

As a corollary, we obtain the first deterministic algorithm running in a sublinear number of rounds for $(1+\varepsilon)$ -approximate densest subgraph detection in the CONGEST model.

Keywords and phrases:

Distributed graph algorithms, graph density computation, graph density approximation, network analysis theory

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Graph algorithms analysis ; Theory of computation

\rightarrow

Distributed algorithms

Related Version:

Full Version: https://arxiv.org/abs/2411.12694

Funding:

This work was supported by the the VILLUM Foundation grant (VIL37507) “Efficient Recomputations for Changeful Problems”, the Independent Research Fund Denmark grant 2020-2023 (9131-00044B) “Dynamic Network Analysis”, and the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 899987.

DOI:

10.4230/LIPIcs.STACS.2025.25

Event:

42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Editors:

Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Density or sparsity measures of graphs are widely studied and have many applications. Examples include the arboricity, the degeneracy, and the maximum subgraph density, all of which are asymptotically related within a factor of $2$ . Given a graph or subgraph $H$ , its density, $\rho(H)$ , is the average number of edges per vertex in $H$ . The maximum subgraph density $\rho^{\max}(G)$ of a graph $G$ is the maximum density $\rho(H)$ amongst all subgraphs $H\subseteq G$ .

Computing maximum subgraph density has been studied both in the dynamic [10, 27], streaming [1, 4] and distributed [15, 28] setting. Often these measures are used to parameterise the sparsity of “uniformly sparse graphs” [2, 8, 25]. These measures are global measures in the sense that they measure the sparsity of the most dense part of the graph. In many cases the graph is not equally sparse (or dense) everywhere. Consider for example a lollipop graph: a large clique joined to a long path. The clique is a subgraph of high density, yet the vertices along the path sit in a part of the graph that is significantly less dense. Often, solutions for graph density related problems provide guarantees based on the most dense part of the graph. In some areas of computation more “local” solutions are desirable. Prior works of a global nature often completely disregard certain parts of the graphs, meaning that the output in sparser parts holds little to no information. We give three examples:

$1)$ Many dynamic algorithms for estimating the subgraph density rely on modifying the solution locally. Algorithmic performance is expressed in terms of (global) graph sparsity, and thus fails to exploit the more fine-grained guarantee that local sparse areas yield.

$2)$ In network analysis, one is often interested in determining dense subgraphs as these subgraphs can be interpreted, for instance, as communities within a social network. However, since many classical algorithms are tuned towards only detecting the densest subgraphs, these algorithms might fail to detect communities in sparser parts of the network [14, 26, 29].

$3)$ Computing the maximum subgraph density is not very local, nor distributed. We consider the models LOCAL and CONGEST, and the lollipop graph. Here, almost instantly, the vertices of the clique realise they are part of a (very dense) clique. The vertices on the path may have to wait for diameter-many rounds before realising the maximum subgraph density of the graph. Distributed algorithms that wish to compute the value of the subgraph density are thus posed with a choice: either use $\Omega(D)$ rounds (where $D$ is the diameter of the graph), or let every vertex output a value that is at most the maximum subgraph density.

1.1 Local density and results

We consider the definition of local density $\rho^{*}(v)$ by Danisch, Chan, and Sozio [14], defined at each node $v$ of the graph (Definition 7). Our contributions can be split into four categories, which we present in four sections with corresponding titles.

A: Conceptual results for local density.

Our primary contribution is an extensive overview of the theoretical properties of this local density measure. We show that, just as in the maximum-subgraph density problem, computing local density has a natural dual problem as we define the local out-degree. Consider a (fractional) orientation of the graph that is locally fair. i.e., for each directed edge $(u,v)$ , the out-degree $g(u)$ is at most $g(v)$ . We prove that for each vertex $v$ , the out-degree of $v$ has the same value over all locally fair orientations. We define this value $\textsl{g}^{*}(v)$ as the local out-degree of $v$ . We prove that the local density of each vertex is the dual of its local out-degree and thereby $\textsl{g}^{*}(v)=\rho^{*}(v)$ . This new definition for local out-degree is considerably shorter than the definition for local density. It allows us to show some previously unknown interesting properties of local density:

B: Results for dynamic algorithms.

We prove that in an approximately fair orientation (a definition by Chekuri et al. [10]) the out-degree $g(v)$ of each vertex is a $(1+\varepsilon)$ -approximation of $\textsl{g}^{*}(v)=\rho^{*}(v)$ (Theorem 12). This implies a previously unknown fact: that there exist dynamic polylogarithmic algorithms [10, 13, 12] where each vertex $v$ maintains a $(1+\varepsilon)$ -approximation of its local density $\rho^{*}(v)$ as by Danisch, Chan, and Sozio [14].

C: Results in LOCAL.

We show that each node $v$ can obtain a $(1+\varepsilon)$ -approximation of $\rho^{*}(v)$ by surveying its $O(\varepsilon^{-2}\log^{2}n)$ -hop neighbourhood. This induces a LOCAL algorithm where each vertex $v\in V$ computes a $(1+\varepsilon)$ -approximation of $\rho^{*}(v)$ in $O(\varepsilon^{-2}\log^{2}n)$ rounds.

Commentary on runtime: We observe that $\rho^{\max}(G)$ can be computed in LOCAL in $O(\varepsilon^{-1}\log n)$ rounds. In contrast, the stricter local density is computed in $O(\varepsilon^{-2}\log^{2}n)$ rounds. This gap may be explained by considering the local density $\rho^{*}(v)$ for low-local-density vertices $v$ in a graph that has high global density. The local density of $v$ can be affected by a dense subgraph within a hop distance of $\Theta(\varepsilon^{-2}\log^{2}n)$ (although it unclear if it can be affected enough to prohibit a $(1+\varepsilon)$ -approximation of $\rho^{*}(v)$ in $o(\varepsilon^{-2}\log^{2}n)$ time). The potential for a barrier of $O(\varepsilon^{-2}\log^{2}n)$ rounds is also illustrated by existing dynamic algorithms [10, 28] that maintain $\eta$ -fair orientations. In this scenario, these algorithms have a worst-case recourse of $\Omega(\varepsilon^{-2}\log^{2}n)$ . We consider it an interesting open problem to either improve our running time in LOCAL, or, show that $O(\varepsilon^{-2}\log^{2}n)$ is tight.

D: Results in CONGEST.

We show a significantly more involved algorithm in CONGEST, where after $O(\operatorname{poly}\{\varepsilon^{-1},\log n\}\cdot 2^{O(\sqrt{\log n})})$ rounds, each vertex $v$ outputs a $(1+\varepsilon)$ -approximation of $\rho^{*}(v)$ . Since $\max\limits_{v\in V}\rho^{*}(v)=\rho^{\max}(G)$ , this is the first deterministic algorithm for $(1+\varepsilon)$ -approximating of the global subgraph density $\rho^{\max}(G)$ in CONGEST, that runs in a number of rounds that is sublinear in the diameter of the graph.

In the main body, we focus on the value variant where we want each vertex $v$ to output an approximation of $\rho^{*}(v)$ . In the full version, we extend our analysis so that each vertex $v$ can output a subgraph $H$ with $v\in H$ where $\rho(H)$ approximates $\rho^{*}(v)$ . See also Table 1.

Table 1: Results in LOCAL (L) or CONGEST (C) where prior work for computing the global subgraph density is compared to our running time for the local subgraph density. D denotes the diameter. Orange running times are not deterministic and occur with high probability.

Model	Problem	Each $v$ outputs $\rho_{v}$ with	Rounds	Source
L	2.1	$\rho_{v}\in[(1+\varepsilon)^{-1}\rho^{\max}(G),(1+\varepsilon)\rho^{\max}(G)]$	$\Theta(D)$	[28]
	2.2	$\max_{v}\rho_{v}\in[(1+\varepsilon)^{-1}\rho^{\max}(G),(1+\varepsilon)\rho^{% \max}(G)]$	$O(\varepsilon^{-1}\log n)$	[28]
	3	$\boldsymbol{\rho_{v}\in[(1+\varepsilon)^{-1}\rho^{}(v),(1+\varepsilon)\rho^{% }(v)]}$	$\boldsymbol{O(\varepsilon^{-2}\log^{2}n)}$	Cor. 15
C	2.1	$\rho_{v}\in[(2+\varepsilon)^{-1}\rho^{\max}(G),(2+\varepsilon)\rho^{\max}(G)]$	$O(D\cdot\varepsilon^{-1}\log n)$	[15]
	2.1	$\rho_{v}\in[(1+\varepsilon)^{-1}\rho^{\max}(G),(1+\varepsilon)\rho^{\max}(G)]$	$O(\varepsilon^{-4}\log^{4}n+D)$ whp.	[28]
	2.2	$\max_{v}\rho_{v}\in[(1+\varepsilon)^{-1}\rho^{\max}(G),(1+\varepsilon)\rho^{% \max}(G)]$	$O(\varepsilon^{-4}\log^{4}n)$ whp.	[28]
	2.2	$\boldsymbol{\rho_{v}\in[(1+\varepsilon)^{-1}\rho^{}(v),(1+\varepsilon)\rho^{% }(v)]}$	$\boldsymbol{O(\operatorname{poly}\{\log n,\varepsilon^{-1}\})\cdot 2^{O(\sqrt{% \log n})}}$	Thm. 16
	3	$\boldsymbol{\rho_{v}\in[(1+\varepsilon)^{-1}\rho^{}(v),(1+\varepsilon)\rho^{% }(v)]}$	$\boldsymbol{O(\operatorname{poly}\{\log n,\varepsilon^{-1}\})\cdot 2^{O(\sqrt{% \log n})}}$	Thm. 16
	3	$\boldsymbol{\rho_{v}\in[(1+\varepsilon)^{-1}\rho^{}(v),(1+\varepsilon)\rho^{% }(v)]}$	$\boldsymbol{O(\operatorname{poly}\{\log n,\varepsilon^{-1}\})}$ whp.	Thm. 16

2 Preliminaries and related work

Let $G=(V,E)$ be an undirected weighted graph with $n$ vertices and $m$ edges. For any $v\in V$ and any integer $k$ , we denote by $H_{k}(v)$ the $k$ -hop neighborhood of $v$ . For each edge $e\in E$ we denote by $\textsl{g}(e)$ the weight of $e$ . Any edge with endpoints $u, v$ may be denoted as $\overline{uv}$ .

We can augment any weighted graph $G$ with a (fractional) orientation. An orientation $\overrightarrow{G}$ assigns to each edge $\overline{uv}$ two positive real values: $\textsl{g}(u\!\to\!v)$ and $\textsl{g}(v\!\to\!u)$ such that $\textsl{g}(\overline{uv})=\textsl{g}(u\!\to\!v)+\textsl{g}(v\!\to\!u)$ . These values may be interpreted as pointing a fraction of the edge $\overline{uv}$ from $u$ to $v$ , and the other fraction from $v$ to $u$ . Given an orientation $\overrightarrow{G}$ , we denote by $\textsl{g}(u)=\sum\limits_{v\in V}\textsl{g}(u\!\to\!v)$ the out-degree of $u$ (i.e., how much fractional edges point outwards from $u$ in $\overrightarrow{G}$ ). Given these definitions, we can consider two graph measures of $G$ : the maximum subgraph density and the minimum orientation of $G$ .

Global graph measures.

For any subgraph $H\subseteq G$ , its density $\rho(H)$ is defined as $\rho(H)=\frac{1}{|V(H)|}\sum\limits_{e\in E(H)}\textsl{g}(e)$ . The maximum subgraph density $\rho^{\max}(G)$ is then the maximum over all $H\subseteq G$ of $\rho(H)$ . A subgraph $H\subseteq G$ is densest whenever $\rho(H)=\rho^{\max}(G)$ . For any orientation $\overrightarrow{G}$ of $G$ , its maximum out-degree $\Delta(\overrightarrow{G})$ is the maximum over all $u$ of the out-degree $\textsl{g}(u)$ . The optimal out-degree of $G$ , denoted by $\Delta^{\min}(G)$ , is subsequently the minimum over all $\overrightarrow{G}$ of $\Delta(\overrightarrow{G})$ . An orientation $\overrightarrow{G}$ itself is minimum whenever $\Delta(\overrightarrow{G})=\Delta^{\min}(G)$ .

The density of $G$ and the optimal out-degree are closely related. One way to illustrate this is through the following dual linear programs:

DS (Densest Subgraph)		$\displaystyle\\|$	FO (Fractional Orientation)
$\displaystyle\max\sum_{\overline{uv}\in E}\textsl{g}(\overline{uv})\cdot y_{u,v}$	s.t.	$\displaystyle\\|$	$\displaystyle\min\rho$	s.t.
$\displaystyle x_{u},x_{v}\geq y_{u,v}$	$\displaystyle\forall\overline{uv}\in E$	$\displaystyle\\|$	$\displaystyle\textsl{g}(u\!\to\!v)+\textsl{g}(v\!\to\!u)\geq\textsl{g}(% \overline{uv})$	$\displaystyle\forall\overline{uv}\in E$
$\displaystyle\sum_{v\in V}x_{v}\leq 1$		$\displaystyle\\|$	$\displaystyle\rho\geq\sum_{v\in V}\textsl{g}(u\!\to\!v)$	$\displaystyle\forall u\in V$
$\displaystyle\quad x_{v},y_{u,v}\geq 0$	$\displaystyle\forall u,v\in V$	$\displaystyle\\|$	$\displaystyle\textsl{g}(u\!\to\!v),\textsl{g}(v\!\to\!u)\geq 0$	$\displaystyle\forall u,v\in V$

Denote by $R$ the optimal value of DS and by $\Delta$ the optimal value of FO. By duality, $R=\Delta$ . Moreover, Charikar [9] relates these two linear programs to the densest subgraph problem:

Theorem 1 (Theorem 1 in [9]).

Let $G$ be a unit weight graph. Denote by $R$ the optimal solution of DS and by $D$ the optimal solution of $F O$ . Then $\rho^{\max}(G)=R=\Delta=\Delta^{\min}(G)$ .

We show that this can be generalised to when $G$ is a weighted graph:

Lemma 2 (See the full version).

Let $G$ be any weighted graph. Denote by $R$ the optimal solution of DS and by $D$ the optimal solution of $F O$ . Then $\rho^{\max}(G)=R=D=\Delta^{\min}(G)$ .

2.1 Densest subgraph in dynamic algorithms

In a classical, non-distributed model of computation we can immediately formalise both the value variant of the (approximate) densest subgraph:

Problem 1.

Given a graph $G$ and an $\varepsilon>0$ , output $\rho^{\prime}\in[(1+\varepsilon)^{-1}\rho^{\max}(G),(1+\varepsilon)\rho^{\max}% (G)]$ .

Alternatively, in the Fractional Orientation (FO) problem the goal is to output a $(1+\varepsilon)$ -approximation of $\Delta^{\min}(G)$ . It turns out that FO is a more accessible problem to study. The LP formulations allow for a straightforward way to compute $\Delta^{\min}(G)$ and/or $\rho^{\max}(G)$ . However, solving the LP requires information about the entire graph, and this information is expensive to collect. Sawlani and Wang [27] get around this difficulty by instead solving an approximate version of (FO). They work with a concept we call local fairness.

Definition 3.

Let $\overrightarrow{G}$ be a fractional orientation of a graph $G$ . We say that $\overrightarrow{G}$ is locally fair whenever $\textsl{g}(u\!\to\!v)>0$ implies $\textsl{g}(u)\leq\textsl{g}(v)$ .

Chekuri et al. [10] extend this definition to $\eta$ -fairness:

Definition 4.

Let $\overrightarrow{G}$ be a fractional orientation of a graph $G$ . We say that $\overrightarrow{G}$ is $\eta$ -fair (for $\eta>0$ ) whenever $\textsl{g}(u\!\to\!v)>0$ implies that $\textsl{g}(u)\leq(1+\eta)\textsl{g}(v)$ .

Related work in dynamic algorithms.

Chekuri et al. [10] continue to focus on computing a $(1+\varepsilon)$ -approximation of the Densest Subgraph problem. They show that, if $G$ is a unit weight graph, there exists a $(1+\varepsilon)$ -approximate solution to FO that is $\eta$ -fair (for some smartly chosen $\eta$ ). They subsequently prove that an $\eta$ -fair orientation allows you to find a $(1+\varepsilon)$ -approximate densest subgraph. This allows them to dynamically maintain the value of the densest subgraph of $G$ in $O(\varepsilon^{-6}\log^{3}n\log\rho^{\max}(G))$ time per insertion or deletion of edges in $G$ . By leveraging the $\eta$ -fairness of the orientation, they can report a $(1+\varepsilon)$ -approximate densest subgraph in time proportional to the size of the subgraph.

2.2 Approximate densest subgraph in LOCAL and CONGEST

We focus on the value variant of the problem, where each vertex outputs a value (as opposed to the reporting variant in the full version, where the goal is to report a densest subgraph).

Problem 2.

Given a graph $G$ and an $\varepsilon>0$ , each vertex $v$ outputs a value $\rho_{v}$ and either:

$\blacksquare$

Problem 2.1: we require that $\,\forall v,\rho_{v}\in[(1+\varepsilon)^{-1}\rho^{\max}(G),(1+\varepsilon)\rho% ^{\max}(G)]$ , or
$\blacksquare$

Problem 2.2: we require that $\,\max_{v}\rho_{v}\in[(1+\varepsilon)^{-1}\rho^{\max}(G),(1+\varepsilon)\rho^{% \max}(G)]$ .

Related work.

Problem 2.1 has a trivial $\Omega(D)$ lower bound, obtained by constructing a lollipop graph (where $D$ denotes the diameter). In LOCAL, it is trivial to solve Problem 2.1 in $\Theta(D)$ time. Problem 2.2 was studied by Ghaffari and Su [20] who present a randomised $(1+\varepsilon)$ -approximation in LOCAL that uses $O(\varepsilon^{-3}\log^{4}n)$ rounds. Fischer et al. [16] present a deterministic $(1+\varepsilon)$ -approximation in LOCAL that uses $2^{O(\log^{2}(\varepsilon^{-1}\log n))}$ rounds. Ghaffari et al. [19] improve this to $O(\varepsilon^{-9}\log^{15}n)$ rounds. The work by Harris [24] improves this to $\tilde{O}(\varepsilon^{-6}\log^{6}n)$ rounds. Su and Vu [28] present the state-of-the-art in this area. They prove that for any graph $G$ , there exists a vertex $v$ such that for the $k$ -hop neighbourhood $H_{k}(v)$ (with $k\in O(\varepsilon^{-1}\log n)$ ) the density $\rho^{\max}(H_{k})$ is a $(1+\varepsilon)$ -approximation of $\rho^{\max}(G)$ . This immediately leads to a trivial LOCAL algorithm: each vertex $u$ collects its $k$ -hop neighbourhood $H_{k}(u)$ in $O(\varepsilon^{-1}\log n)$ rounds, solves the LP of Densest Subgraph in its own node, and reports the value $\rho^{\max}(H_{k}(u))$ .

In CONGEST, the state-of-the-art deterministic algorithm for Problem 2.1 and 2.2 is by Das Sarma et al. [15] who present a $(2+\varepsilon)$ -approximation in $O(D\cdot\varepsilon^{-1}\log n)$ rounds. The best randomised work is by Su and Vu [28] who present a randomised algorithm for Problem 2.2 that runs in $O(\varepsilon^{-4}\log^{4}n)$ rounds w.h.p. See also Table 1 for an overview.

2.3 Local density

Danisch, Chan, and Sozio [14] introduce a more local measure which they call the local density. Its lengthy definition assigns to each vertex $v$ a value. We note for the reader that we almost immediately define our local out-degree (Definition 8), and only use local out-degree in proofs. Hence, the reader is not required to have a thorough understanding of the following:

Definition 5 (Definition 2.2 in [14]).

Let $G=(V,E)$ be a weighted graph where an edge $e$ has weight $\textsl{g}(e)$ . Let $B\subseteq V$ . For any $X\subseteq V-B$ , we define the quotient edges $\hat{E}_{B}(X)$ as all edges in $G$ with one endpoint in $X$ , and the other endpoint in $X$ or $B$ . We define:

$\blacksquare$

for $X\subseteq V-B$ , the quotient subgraph density $\hat{\rho}_{B}(X):=\frac{1}{|X|}\sum\limits_{e\in\hat{E}_{B}(X)}\textsl{g}(e)$ .
$\blacksquare$

the maximum quotient density $\hat{\rho}_{B}(G):=\max\limits_{X\subseteq V-B}\,\hat{\rho}_{B}(X)$ .

Definition 6 (Definition 2.3 in [14]).

Given a weighted undirected graph $G=(V,E)$ , we define the diminishing-dense decomposition $\mathcal{B}$ of $G$ as the sequence $B_{0}\subset B_{1}\ldots\subset B_{\ell}=V$ :

We define $B_{0}=\emptyset$ . For $i\geq 1$ if $B_{i-1}=V$ then $\ell:=i$ . Otherwise:

S_{i}:=arg\,\max_{X\subseteq V-B_{i-1}}\hat{\rho}_{B_{i-1}}(X),\textnormal{ % and }B_{i}:=B_{i-1}\cup S_{i}.

Definition 7 (Definition 2.3 in [14]).

Given a weighted undirected graph $G=(V,E)$ and a diminishing-dense decomposition $\mathcal{B}$ , each vertex $v\in V$ has one integer $i$ where $v\in S_{i}$ . We define the local density $\rho^{*}(v):=\hat{\rho}_{B_{i-1}}(S_{i})$ .

The benefit of local measures.

Problem 2’s variants have drawbacks in a distributed model of computation. Problem 2.1 has an $\Omega(d)$ lower bound (making it trivial in LOCAL). Problem 2.2 allows some vertices to output nonsense. The definition of local density alleviates these issues, as we may define an algorithmic problem which we consider to be more natural:

Problem 3.

Given $(G,\varepsilon)$ , each vertex $v$ outputs $\rho_{v}\in[(1+\varepsilon)^{-1}\rho^{*}(v),(1+\varepsilon)\rho^{*}(v)]$ .

Related work.

Danisch, Chan, and Sozio [14] introduce the local density (Definition 7). Intuitively, they define a partition $V_{1}\ldots V_{k}$ of $V$ . For each $i$ , they consider the set $X_{i}=\bigcup_{j=1}^{i}V_{j}$ . They then define the graph $H_{i}$ as the vertex-induced subgraph of $X_{i}$ where for each edge in $G$ between a vertex in $X_{i}$ and a vertex not in $X_{i}$ , they add a self loop. They define the quotient density of $V_{i}$ as the density of $H_{i}$ . The local density $\rho^{*}(v)$ of a vertex $v$ is the quotient density of $V_{i}$ for $v\in V_{i}$ . Danisch, Chan, and Sozio [14] then define a quadratic program $\textbf{FO}^{2}$ . The domain of this program is the space of all orientations of the graph $G$ . The cost function is the sum over all vertices $u$ , of the out-degree squared. Consider an orientation $\overrightarrow{G}$ of $G$ that optimises the cost function. Danisch, Chan, and Sozio show that for each vertex $v$ it out-degree $g(v)$ equals the local density $\rho^{*}(v)$ . As a consequence, over all optimal solutions to $\textbf{FO}^{2}$ , the out-degree of each vertex is unique. They provide a Frank-Wolfe based algorithm to solve the quadratic program with no theoretical guarantees.

Chekuri, Harb, and Quanrud [22] study computing the local density by solving the quadratic program. They show [22, Theorem 3.4] some interesting properties of $\textbf{FO}^{2}$ . Specifically, they show that the uniqueness property by Danish, Chan and Sozio is a special case of Fujishige’s result [18] from 1980. They additionally show that the algorithm GREEDY++ by Boob, Gao, Peng, Sawlani, Tsourakakis, Wang, and Wang [5] (when applied to this quadratic program) converges to an orientation where the out-degree of each vertex $v$ is a $(1+\varepsilon)$ -approximation of $\rho^{*}(v)$ . Chekuri, Harb, and Quanrud [23] subsequently show that the more general SUPER-GREEDY++ algorithm by Chekuri, Quanrud and Torres [11] also converges to $(1+\varepsilon)$ -approximation of each $\rho^{*}(v)$ .

Borradaile, Migler, and Wilfong [7] observe that there is a correlation between the fairness of an orientation and local density. An integral orientation is any orientation of the graph where for each edge $(u,v)$ , $\textsl{g}(u\!\to\!v)\in\{0,1\}$ . They consider an egalitarian orientation which is defined as an integral orientation where “the total available out-degree is shared among the vertices as equally as allowed by the topology of the graph”. An egalitarian orientation, and other equivalent notions of “fair integral orientations”, are formally defined through an integer flow problem on the graph [6, 17, 30]. From section 2 in [6] it follows that an integral orientation is egalitarian if and only if $\textsl{g}(u\!\to\!v)=1$ implies that $\textsl{g}(u)\leq\textsl{g}(v)+1$ .

Using an egalitarian orientation, they create a decomposition of the graph that they call a density decomposition. The density decomposition by Borradaile, Migler, and Wilfong [7] is not equal to the local density. The analysis of Kopelowitz, Krauthgamer, Porat, and Solomon shows that if $\overrightarrow{G}$ is an egalitarian orientation then $\max_{v}\textsl{g}(v)\leq\rho(G)+O(\log n)$ . Their decomposition, compared to the one used for the local density, can thus be viewed as one that is coarser but similar in spirit. It can thereby be argued that Borradaile, Migler, and Wilfong [7] are the first to show a connection between the local density and fair orientations of a graph. However, we note that the integrality of their orientation prevents exact (or $(1+\varepsilon)$ -approximate) computations of the local density.

3 Results and organisation

Now we are ready to formally state our contributions. Our primary contribution is that we show a dual definition to local density, which we call the local out-degree:

Definition 8.

Given a graph $G=(V,E)$ , we define the local out-degree as:

\textsl{g}^{*}(u):=\textnormal{ the out-degree }\textsl{g}(u)\textnormal{ in % any locally fair fractional orientation of }G.

It is not immediately clear that the local out-degree is well-defined. We prove (Theorem 9) that each vertex in $G$ has the same out-degree across all locally fair orientations of $G$ (and thus, the set of all locally fair orientations of $G$ assigns to each vertex a real value). We believe that the local out-degree is conceptually simpler that the local density. Through this definition, we are able to show various algorithms to approximate the local density.

3.A Conceptual results for local density

We prove in Section 4 that these local definitions generalise the global definition of subgraph density and out-degree, as they exhibit the same dual behaviour. We show several previously unknown properties of the local density, which we consider to be of independent interest:

Theorem 9.

For any weighted graph $G$ , $\forall v\in V$ , $\textsl{g}^{*}(v)$ is well-defined and equals $\rho^{*}(v)$ .

Corollary 10.

Given a weighted graph $G$ , $\rho^{\max}(G)=\Delta^{\min}(G)=\max_{v}\textsl{g}^{*}(v)$ .

Corollary 11.

For any graph $G$ , there exists a fractional orientation $\overrightarrow{G}$ that is locally fair.

3.B Results for dynamic algorithms

We show in Section 5 that $\eta$ -fair orientations imply approximations for our local measures:

Theorem 12.

Let $G$ be a weighted graph and $\overrightarrow{G}$ be an $\eta$ -fair fractional orientation for $\eta\leq\frac{\varepsilon^{2}}{128\cdot\log n}$ . Then $\forall v\in V$ : $(1+\varepsilon)^{-1}\rho^{*}(v)\leq\textsl{g}(v)\leq(1+\varepsilon)\rho^{*}(v).$

This immediately implies the following Corollary by applying [10]:

Corollary 13.

There exists an algorithm [10] that can fractionally orient a dynamic unit-weight graph $G$ with $n$ vertices subject to edge insertions and deletions with deterministic worst-case $O(\varepsilon^{-6}\log^{4}n))$ update time such that for all $v\in V$ :

\textsl{g}(v)\in[(1+\varepsilon)^{-1}\rho^{*}(v),(1+\varepsilon)\rho^{*}(v)].

3.C Results in LOCAL

The local density as a measure is not entirely local. However, we prove in Section 6 that far-away subgraphs affect the local density of a vertex $v$ only marginally:

Theorem 14.

Let $G$ be a unit-weight graph. For any $\varepsilon>0$ and vertex $v$ , denote by $\rho^{*}(v)$ its local density and by $\rho^{*}_{k}(v)$ its local density in $H_{k}(v)$ . Then $\rho^{*}_{k}(v)\in[(1+\varepsilon)^{-1}\rho^{*}(v),(1+\varepsilon)\rho^{*}(v)]$ for $k\in\Theta(\varepsilon^{-2}\log^{2}n)$ .

This immediately implies a trivial algorithm for problem 2 in LOCAL (where each vertex $v$ collects its $k$ -hop neighbourhood $H_{k}(v)$ for $k\in\Theta(\varepsilon^{-2}\log^{2}n)$ and then solves FO on $H_{k}(v)$ ):

Corollary 15.

There exists an algorithm in LOCAL that given a unit graph $G$ and $\varepsilon>0$ computes in $O(\varepsilon^{-2}\log^{2}n)$ rounds for all $v\in V$ a value $\rho_{v}\in[(1+\varepsilon)^{-1}\rho^{*}(v),(1+\varepsilon)\rho^{*}(v)]$ .

3.D Results in CONGEST

Finally in Section 7, we solve Problem 3 in CONGEST by computing an $\eta$ -fair orientation. We use as a subroutine algorithm to compute blocking flows in an $h$ -layered DAG [21]:

Theorem 16.

Suppose one can compute a blocking flow in an $n$ -node $h$ -layered DAG in $\textnormal{Blocking}(h,n)$ rounds. There exists an algorithm in CONGEST that given a unit-weight graph $G$ and $\varepsilon>0$ computes in $O(\varepsilon^{-3}\log^{4}n\cdot(\varepsilon^{-2}\log^{2}n+\textnormal{% Blocking}(\varepsilon^{-2}\log^{2}n,n)))$ rounds an orientation $\overrightarrow{G}$ such that for all $v\in V$ : $\textsl{g}(v)\in[(1+\varepsilon)^{-1}\rho^{*}(v)),(1+\varepsilon)\rho^{*}(v)% \rho^{*}(v)]$ .

As a corollary, we obtain the first deterministic algorithm running in a sublinear number of rounds for $(1+\varepsilon)$ -approximate dense subgraph detection in the CONGEST model (Table 1).

4 Conceptual results for local density

Our primary contribution is the definition of local out-degree as a dual to local density.

Lemma 17.

The local density is well-defined. That is, for any two locally fair orientations $\overrightarrow{G}$ or $\overrightarrow{G}^{\prime}$ where a vertex $u$ has out-degree $\textsl{g}(u)$ or $\textsl{g}^{\prime}(u)$ respectively, $\textsl{g}(u)=\textsl{g}^{\prime}(u)$ .

Proof.

Suppose for the sake of contradiction that there exists two locally fair orientations $(\overrightarrow{G},\overrightarrow{G}^{\prime})$ and a vertex $u\in V$ where $\textsl{g}(u)>\textsl{g}^{\prime}(u)$ . We define their symmetric difference graph $S$ as a digraph where the vertices are $V$ and there exists an edge $\overrightarrow{ab}$ whenever $\textsl{g}(a\!\to\!b)>\textsl{g}^{\prime}(a\!\to\!b)$ . We may assume that $S$ contains no directed cycles:

Indeed if $S$ contains any directed cycle $\pi$ we change $\overrightarrow{G^{\prime}}$ , where for all $\overrightarrow{ab}\in\pi$ we slightly increase $\textsl{g}^{\prime}(a\!\to\!b)$ until $S$ loses an edge. This operation does not change the out-degree of any vertex in $\overrightarrow{G}^{\prime}$ . So, we still have two locally fair orientations $(\overrightarrow{G},\overrightarrow{G}^{\prime})$ with $\textsl{g}(u)>\textsl{g}^{\prime}(u)$ .

Since $\textsl{g}(u)>\textsl{g}^{\prime}(u)$ , the vertex $u$ must have at least one out-edge in $S$ and since $S$ has no cycles, it follows that $u$ must have some directed path $\pi_{v}$ to a sink $v$ in $S$ . Since $v$ is a sink in the symmetric difference graph it follows that $\textsl{g}(v)<\textsl{g}^{\prime}(v)$ .
However we now observe the following property of the path $\pi_{v}$ :

$\blacksquare$

$\forall\overrightarrow{ab}\in\pi_{v}$ , $\textsl{g}(a\!\to\!b)>\textsl{g}^{\prime}(a\!\to\!b)$ . Thus, $\textsl{g}(a\!\to\!b)>0$ and so there exists a directed path from $u$ to $v$ in $\overrightarrow{G}$ . Since $\overrightarrow{G}$ is locally fair this implies that $\textsl{g}(u)\leq\textsl{g}(v)$ .
$\blacksquare$

$\forall\overrightarrow{ab}\in\pi_{v}$ , $\textsl{g}(a\!\to\!b)>\textsl{g}^{\prime}(a\!\to\!b)$ . Thus, $\textsl{g}^{\prime}(a\!\to\!b)<\textsl{g}(ab)$ and so $\textsl{g}^{\prime}(b\!\to\!a)>0$ . It follows that there exists a directed path from $v$ to $u$ in $\overrightarrow{G}^{\prime}$ . Local fairness implies $\textsl{g}^{\prime}(v)\leq\textsl{g}^{\prime}(u)$ .

The 4 equations: $\textsl{g}(u)>\textsl{g}^{\prime}(u)$ , $\,\textsl{g}(v)<\textsl{g}^{\prime}(v)$ , $\,\textsl{g}(u)\leq\textsl{g}(v)$ , and $\,\textsl{g}^{\prime}(u)\geq\textsl{g}^{\prime}(v)$ give a contradiction. $\hfill\blacktriangleleft$

Lemma 17 would imply that the local out-degree is well-defined, if the set of locally fair orientations is non-empty. Bera, Bhattacharya, Choudhari and Ghosh already aim to prove this in Section 4.1 of [3] (right above Equation 9). They claim that a locally fair orientation always exist by the following argument: They consider an arbitrary orientation $\overrightarrow{G}$ that is not locally fair. They claim that for any pair $(u,v)$ where $\textsl{g}(u)>\textsl{g}(v)$ and $\textsl{g}(u\!\to\!v)>0$ it is possible to transfer some out-degree from $\textsl{g}(u)$ to $\textsl{g}(v)$ . The existence of a locally fair orientation would follow, if it can be shown that this procedure converges to a locally fair orientation. Indeed, since the space of all orientations is a compact polytope, the limit of a converging sequence over this domain must lie within the space.

It is intuitive but not clear that this procedure indeed converges. Indeed, decreasing $\textsl{g}(u)$ and increasing $\textsl{g}(v)$ may cause some other edge $(w,u)$ or $(v,w)$ to start violating local fairness. One way to show convergence is to define a potential function and to show that such a transfer always decreases the potential. We define the potential function $\sum_{v\in V}\textsl{g}^{2}(v)$ , thereby creating a quadratic program where the domain is the space of all orientations of $G$ . We prove that any optimal solution to this quadratic program must be a locally fair orientation. Any quadratic function over a compact domain has an optimum and so the existence of a locally fair orientation follows.

See 9

Proof.

We consider the following quadratic program $\textbf{FO}^{2}$ from [14, Section 4] where we compute a fractional orientation of the graph $G$ subject to a quadratic cost function:

	$\displaystyle\min\sum\textsl{g}(u)^{2}$	s.t.
	$\displaystyle\textsl{g}(u\!\to\!v)+\textsl{g}(v\!\to\!u)\geq\textsl{g}(% \overline{uv})$	$\displaystyle\forall\overline{uv}\in E$
	$\displaystyle\textsl{g}(u)\geq\sum_{v\in V}\textsl{g}(u\!\to\!v)$	$\displaystyle\forall u\in V$
	$\displaystyle\textsl{g}(u\!\to\!v),\textsl{g}(v\!\to\!u)\geq 0$	$\displaystyle\forall u,v\in V$

Consider any optimal solution to the quadratic program. It must be that $\textsl{g}(u)=\sum_{v\in V}\textsl{g}(u\!\to\!v)$ . Danisch, Chan, and Sozio [14, Corollary 4.4] prove that for any vertex $u$ , the local density $\rho^{*}(u)=\textsl{g}(u)$ .

We first note that any solution to the quadratic program is an orientation. Indeed, suppose for the sake of contradiction that there exists an edge $\overline{uv}\in E$ where $\textsl{g}(u\!\to\!v)+\textsl{g}(v\!\to\!u)>\textsl{g}(\overline{uv})$ . We may now decrease either $\textsl{g}(u\!\to\!v)$ or $\textsl{g}(v\!\to\!u)$ to obtain another viable solution to the program. Consider decreasing $\textsl{g}(u\!\to\!v)$ , then we may decrease $\textsl{g}(u)$ and maintain a viable and better solution to the program – a contradiction.

Secondly, we claim that the optimal solution to the quadratic program is a locally fair orientation. Suppose for the sake of contradiction that there exist $u, v$ with $\textsl{g}(u)=\textsl{g}(v)+\delta^{\prime}$ and $\textsl{g}(u\!\to\!v)=\delta$ for $\delta,\delta^{\prime}>0$ . We can decrease $\textsl{g}(u\!\to\!v)$ to zero by increasing $\textsl{g}(v\!\to\!u)$ by $\Delta=\min\{\delta,\delta^{\prime}\}$ and still maintain a solution to the program. This reduces the solution’s value by $(\textsl{g}(u)-\Delta)^{2}-(\textsl{g}(v)+\Delta)^{2}$ . However, we now found a solution to the quadratic program with a lower value than the optimal solution – a contradiction.

Thus, the solution to $\textbf{FO}^{2}$ gives a locally fair orientation $\overrightarrow{G}$ where each vertex $u$ has out-degree $\textsl{g}(u)$ . The local density $\textsl{g}^{*}(u)=\textsl{g}(u)$ is by Lemma 17 well-defined. Danisch, Chan and Sozio [14, Corollary 4.4] show that $\rho^{*}(u)=\textsl{g}(u)$ , which proves the theorem. $\hfill\blacktriangleleft$ Since the local density equals the local out-degree, we conclude from [14] that:

See 10

Since a quadratic program over a convex domain always has a solution, we may also note the following interesting fact:

See 11

5 Results for dynamic algorithms

We use our definition of local out-degree to show that there already exist dynamic algorithms that approximate the local density of each vertex. Recall that an orientation $\overrightarrow{G}$ is $\eta$ -fair whenever for all $\overline{uv}\in E(\overrightarrow{G})$ , $\textsl{g}(u\!\to\!v)>0$ implies that $\textsl{g}(u)\leq(1+\eta)\textsl{g}(v)$ . We show that if we choose $\eta\leq\frac{\varepsilon^{2}}{128\cdot\log n}$ , then for any $\eta$ -fair orientation, for all $v$ , the out-degree $\textsl{g}(v)$ is a $(1+\varepsilon)$ approximation of $\textsl{g}^{*}(v)=\rho^{*}(v)$ . Moreover, we prove that the maximal local out-degree (i.e. $\max_{u\in V}\textsl{g}(u)$ ) is a $(1+\varepsilon)$ approximation of $\Delta^{\min}(G)=\rho^{\max}(G)$ ; illustrating that approximating the local measures is a strictly more general problem. To this end, we prove the following helper lemma:

Lemma 18.

Let $\eta\leq\frac{\varepsilon^{2}}{128\cdot\log n}$ and $k\leq\log_{(1+\frac{1}{16}\varepsilon)}n$ . Then $(1+\eta)^{-k}\geq(1+0.5\varepsilon)^{-1}$ .

Proof.

Using $\log(1+x)\geq x/2$ whenever $x<1$ , we obtain:

-\log_{1+\frac{\varepsilon}{16}}(n)=-\frac{\log(n)}{\log 1+\frac{\varepsilon}{% 16}}\geq-\frac{\log(n)}{\frac{\varepsilon}{32}}\geq-\frac{\varepsilon}{4}\cdot% {}\frac{128\log(n)}{\varepsilon^{2}}

	$\displaystyle(1+\eta)^{-k}\geq(1+\frac{\varepsilon^{2}}{128\cdot c\cdot\log n}% )^{-c\cdot\log_{1+\frac{\varepsilon}{16}}(n)}\geq(1+\frac{\varepsilon^{2}}{128% \cdot c\log n})^{-\frac{\varepsilon}{4}\cdot{}\frac{128\cdot c\cdot\log(n)}{% \varepsilon^{2}}}$
	$\displaystyle(1+\eta)^{-k}\geq EXP\left[-\frac{\varepsilon}{4}\right]\geq EXP% \left[-\log(1+\frac{\varepsilon}{2})\right]\geq(1+\frac{\varepsilon}{2})^{-1}$

$\hfill\blacktriangleleft$

See 12

Proof.

First, we show that for all vertices $v$ , $\textsl{g}(v)\leq(1+\varepsilon)\rho^{*}(v)$ .

Suppose for the sake of contradiction that there exists a vertex $u$ with $\textsl{g}(u)>(1+\varepsilon)\rho^{*}(u)$ . We fix $\rho^{*}(u)=\textsl{g}^{*}(u)=\gamma$ and work with $\gamma$ throughout the remainder of this proof to show a contradiction. By Corollary 11, there exists at least one locally fair fractional orientation $\overrightarrow{G}_{x}$ . By Corollary 10, every vertex $v$ in this orientation has out-degree $\textsl{g}_{x}(v)=\textsl{g}^{*}(v)=\rho^{*}(v)$ . And thus, the fractional orientation $\overrightarrow{G}_{x}$ is not equal to $\overrightarrow{G}$ .

Given $\overrightarrow{G}$ and a locally fair fractional orientation $\overrightarrow{G}_{x}$ , we do three steps:

$\blacksquare$

We partition the vertices of $G$ to create two graphs $G_{1}$ and $G_{2}$ . The partition is based on the orientation $\overrightarrow{G}_{x}$ as we set: $G^{1}=G[v\in V\mid\textsl{g}_{x}(v)\leq\gamma]$ and by $G^{2}=G[v\in V\mid\textsl{g}_{x}(v)>\gamma]$ . For ease of notation, we write any edge with one endpoint $a\in V(G^{1})$ and one endpoint $b\in V(G^{2})$ as $(a,b)$ and never as $(b,a)$ .
$\blacksquare$

From $G^{1}$ , we create a family of nested subgraphs using $\overrightarrow{G}$ . We define graphs $G^{1}_{i}:=G^{1}[v\in V(G^{1})\mid\textsl{g}(v)\geq\frac{\textsl{g}(u)}{(1+% \eta)^{i}}]$ . We denote by $k$ the lowest integer such that $|V(G^{1}_{k+1})|<(1+\frac{\varepsilon}{16})|V(G^{1}_{k})|$ . We apply Lemma 18 to observe that $(1+\eta)^{-k}\geq(1+\varepsilon/2)^{-1}$ .
$\blacksquare$

Finally, we use both orientations to create three claims that contradict one another.

The first claim. We denote by $E_{\uparrow}$ the set of all edges $e=(a,b)$ with $a\in V(G^{1}_{k+1})$ and $b\in V(G^{2})$ and claim that:

\sum_{e\in E(G^{1}_{k+1})}\textsl{g}(e)+\sum_{e\in E_{\uparrow}}\textsl{g}(e)% \leq\sum_{v\in V(G_{k+1}^{1})}\textsl{g}_{x}(v).

(1)

Indeed for $\overline{ab}\in E(G^{1}_{k+1})$ , both endpoints are in $V(G_{k+1})$ . Because $\overrightarrow{G}_{x}$ is locally fair, this implies that $\textsl{g}_{x}(a\!\to\!b)+\textsl{g}_{x}(b\!\to\!a)=\textsl{g}(\overline{ab})$ . For all $\overline{ab}\in E_{\uparrow}$ , $\textsl{g}_{x}(b)>\gamma\geq\textsl{g}_{x}(a)$ per definition of $G^{1}$ and $G^{2}$ . By local fairness, $\textsl{g}_{x}(a\!\to\!b)=\textsl{g}(\overline{ab})$ and the inequality follows.
The second claim. We secondly claim that:

\sum_{v\in V(G^{1}_{k})}\textsl{g}(v)>\sum_{v\in V(G_{k+1}^{1})}\textsl{g}_{x}% (v).

(2)

This is because we can lower bound $\sum_{v\in V(G^{1}_{k})}\textsl{g}(v)$ as follows:

	$\displaystyle\sum_{v\in V(G^{1}_{k})}\textsl{g}(v)$	$\displaystyle\geq(1+\eta)^{-k}\cdot\textsl{g}(u)\cdot\|V(G^{1}_{k})\|>(1+\eta)^{% -k}\cdot\textsl{g}(u)\cdot\|V(G^{1}_{k+1})\|\cdot(1+\frac{\varepsilon}{16})^{-1}$
		$\displaystyle>(1+\frac{\varepsilon}{2})^{-1}\cdot(1+\varepsilon)\gamma\cdot\|V(% G^{1}_{k+1})\|\cdot(1+\frac{\varepsilon}{16})^{-1}\geq\gamma\cdot\|V(G^{1}_{k+1})\|$

The claim follows by noting that per definition of $G^{1}$ , for all $v\in V(G^{1}_{k+1})$ , $\textsl{g}_{x}(v)\leq\gamma$ .
The third claim. Lastly, we claim that:

\sum_{v\in V(G^{1}_{k})}\textsl{g}(v)\leq\sum_{e\in E(G^{1}_{k+1})}\textsl{g}(% e)+\sum_{e\in E_{\uparrow}}\textsl{g}(e)

(3)

Consider any $v\in V(G^{1}_{k})$ and any vertex $a$ with $\textsl{g}(v\!\to\!a)>0$ . Recall that $\overrightarrow{G}$ is an $\eta$ -fair orientation. Thus, if $a\in G^{1}$ , then $\overline{va}\in E(G^{1}_{k+1})$ . If $a\in G^{2}$ , then per definition $\overline{va}\in E_{\uparrow}$ . Per definition of a fractional orientation $\textsl{g}(v\!\to\!a)\leq\textsl{g}(\overline{va})$ and so the claim follows.
A contradiction. Equation 1, 2 and 3 contradict each other. Thus, we have proven that for all vertices $v$ , $\textsl{g}(v)\leq(1+\varepsilon)\rho^{*}(v)$ .

The full version finishes the proof by showing the other direction. $\hfill\blacktriangleleft$

If $G$ is a unit-weight graph, Chekuri et al. [10] present a dynamic algorithm to maintain an $\eta$ -fair orientation in a unit-weight graph with $\eta\in O(\varepsilon^{-2}\log n)$ . Thus, by Theorem 12, we may now conclude that they approximate the local density (and/or the local out-degree):

See 13

6 Results in LOCAL

We prove that the local out-degree of each $v\in V$ is (largely) determined by its local neighbourhood. As a result, we immediately get an algorithm to solve Problem 3 in LOCAL.

See 14

Proof.

To prove the theorem, we design a simple deletion-only algorithm to maintain an $\eta$ -fair orientation. For $\eta=\frac{\varepsilon^{2}}{128\log n}$ , this algorithm has a recursive depth of $O(\varepsilon^{-2}\log^{2}n)$ .

Specifically, we say that a directed edge $\overline{uv}$ is bad whenever $\textsl{g}(u\!\to\!v)>0$ and $\textsl{g}(u)>(1+\eta)\textsl{g}(v)$ . In an $\eta$ -fair orientation no edge is bad. Whenever we delete an edge $\overline{x_{1}x_{0}}$ , the out-degree $\textsl{g}(x_{1})$ decreases by $\textsl{g}(x_{1}\!\to\!x_{0})$ . For vertices $x_{2}$ with $\textsl{g}(x_{2}\!\to\!x_{1})>0$ , it may now be that $\textsl{g}(x_{2})>(1+\eta)\textsl{g}(x_{1})$ (and thus the edge $\overline{x_{2}x_{1}}$ becomes bad). Note if there exists such a vertex $x_{2}$ , then it must hold for the vertex $x_{2}^{*}:=\arg\max_{x_{2}\in V}\{\textsl{g}(x_{2})\mid\textsl{g}(x_{2}\!\to\!% x_{1})>0\}$ . This leads to a recursive algorithm to decrease the out-degree of a vertex (Algorithm 1).

Algorithm 1 decrease(

\textsl{g}(u\!\to\!v)

by

\Delta

– assuming that

\Delta\leq\textsl{g}(u\!\to\!v)

).

We claim that this algorithm as a recursive depth of $O(\log_{1+\eta}n)$ . Indeed any sequence of recursive calls is a path in $G$ . Denote the path belonging to the longest sequence of recursive calls by $x_{0},x_{1},\ldots x_{\ell}$ . Since $\Delta$ is always at most 1, it must hold for all $i$ that: $\textsl{g}(x_{i})>(1+\eta)(\textsl{g}(x_{i-1})-1))$ . Since a graph may have at most $n^{2}$ edges, $\textsl{g}(x_{\ell})\leq n$ and it follows that the recursive depth is at most $\ell\in O(\log_{1+\eta}n)$ . We now apply $\log(1+x)\geq x/2$ and note that: $\ell\leq\frac{\log n}{\log(1+\eta)}\leq\frac{\log n}{\eta/2}\subseteq O(\frac{% \log n}{64\varepsilon^{2}/\log n})\subseteq O(\frac{\log^{2}n}{\varepsilon^{2}})$ .

Given this theoretical algorithm, we prove the lemma. Consider any fair orientation $\overrightarrow{G}$ . Then by Theorem 9 for any vertex $v$ , $\textsl{g}(v)=\rho^{*}(v)$ . Choose some $k\in\Theta(\varepsilon^{-2}\log^{2}n)$ sufficiently large and let $H_{k}(v)$ be the $k$ -hop neighbourhood of $v$ and $E_{k}$ be all the edges in $H_{k+1}(v)$ that are not in $H_{k}$ .

Choose $\eta=\frac{\varepsilon^{2}}{128\log n}$ . The orientation $\overrightarrow{G}$ is per definition an $\eta$ -fair orientation. We run on $\overrightarrow{G}$ our deletion-only algorithm, deleting all edges in $E_{k}$ . Since our algorithm has a recursive depth of $\ell<k$ , we end up with an $\eta$ -fair orientation of $H_{k}(v)$ where $\textsl{g}(v)=\rho^{*}(v)$ . We apply Theorem 12 to conclude that $\rho^{*}(v)=\textsl{g}(v)\in[(1+\varepsilon)^{-1}\rho_{k}^{*}(v),(1+% \varepsilon)^{-1}\rho_{k}^{*}(v)]$ which concludes the theorem. $\hfill\blacktriangleleft$

See 15

7 Results in CONGEST

We now describe an algorithm in CONGEST that for any unit-weight graph $G$ , creates an $\eta$ -fair orientation (with $\eta=\frac{\varepsilon^{2}}{128\cdot\log n}$ ). Our algorithm uses as a subroutine a distributed algorithm to compute a blocking flow in an $h$ -layered DAG in $O(\textnormal{Blocking}(h,n))$ rounds.

Definition 19.

An edge-capacitated DAG $G$ is $h$ -layered if the vertices can be embedded on a grid of height $h$ , such that every directed edge $\overline{uv}$ points downwards.

Definition 20.

For an edge-capacitated DAG $G$ with sources $S$ and terminals $T$ , a flow $f$ from $S$ to $T$ is blocking if every augmenting path of $f$ contains at least one saturated edge.

Lemma 21 (Lemma 7.2 and 9.1 in [21]).

There exists an algorithm which, given an $n$ -node $h$ -layer edge-capacitated DAG $D$ with sources $S$ and terminals $T$ computes a blocking ST-flow in CONGEST in:

$\blacksquare$

$\textnormal{Blocking}(h,n)=\tilde{O}(h^{4})$ rounds with high probability,
$\blacksquare$

$\textnormal{Blocking}(h,n)=\tilde{O}(h^{6}\cdot 2^{c\sqrt{\log n}})$ deterministic rounds for some constant $c$ .

We compute an $\eta$ -fair orientation by repeatedly constructing a DAG with $h\in O(\varepsilon^{-2}\log^{2}n)$ and computing blocking flows. Theorem 12 implies in an $\eta$ -fair orientation (for our choice of $\eta$ ) the out-degree of each vertex $v$ is a $(1+\varepsilon)$ -approximation $\rho^{*}(v)$ .

The initialising step.

Before we start our algorithm, we create a starting orientation where we set for every edge $e=\overline{uv}$ , $\textsl{g}(u\!\to\!v)=\frac{1}{2}\textsl{g}(e)$ and $\textsl{g}(v\!\to\!u)=\frac{1}{2}\textsl{g}(e)$ . This gives each vertex $u$ some out-degree $\textsl{g}(u)$ which we partition:

Definition 22.

Let each vertex $u$ have out-degree $\textsl{g}(u)$ . We define level $i$ as:

L_{i}:=\left\{u\in V\mid\textsl{g}(u)\in\left[(1+\frac{\eta}{2})^{i},(1+\frac{% \eta}{2})^{i+1}\right]\right\}.

A vertex $u\in L_{i}$ is at level $i$ and $\ell^{\prime}$ denotes the highest level that is not empty.
Whenever $\textsl{g}(u)=(1+\frac{\eta}{2})^{i}$ , $u$ may decide whether $u\in L_{i}$ or $u\in L_{i-1}$ ; whenever our algorithm increases $\textsl{g}(u)$ the vertex $u$ defaults to the lowest possible level and vice versa.

Definition 23.

Consider an edge $\overline{uv}$ with $u\in L_{i}$ and $v\in L_{j}$ . We say that:

$\blacksquare$

$(u,v)$ is an out-edge from $u$ and an in-edge into $v$ whenever $i>j$ and $\textsl{g}(u\!\to\!v)>0$ , and
$\blacksquare$

$(u,v)$ is violating whenever $i>j+1$ and $\textsl{g}(u\!\to\!v)>0$

Note that the orientation is $\eta$ -fair whenever there exist no violating edges.

Figure 1: Given a graph

G

, we arbitrarily orient

G

. This allows us to partition the vertices of

G

into levels

L_{1},\ldots L_{6}

based on their current out-degree. We say that an edge

(u,v)

is violating whenever

\textsl{g}(u\!\to\!v)>0

,

u\in L_{i}

,

v\in L_{j}

and

i>j+1

. We show violating edges in red. Our algorithm iterates over an integer

h

from high to low, and tries to flip all violating edges from level

L_{h}

.

Lemma 24.

Let $\eta\leq\frac{\varepsilon^{2}}{128\cdot\log n}$ . For our orientation, let $\ell^{\prime}$ be the highest level such that $L_{\ell^{\prime}}$ is not empty then $\ell^{\prime}\leq\varepsilon^{-2}\log^{2}n$ .

Proof.

The maximal out-degree of a vertex is $n$ . Thus, $\ell^{\prime}\leq\frac{\log n}{\log(1+\frac{\eta}{2})}$ . We now apply $\log(1+x)\geq x/2$ and note that: $\ell^{\prime}\leq\frac{\log n}{\log(1+\frac{\eta}{2})}\leq\frac{\log n}{\eta/4% }=\frac{\log n}{32\varepsilon^{2}/\log n}\leq\frac{\log^{2}n}{\varepsilon^{2}}$ . $\hfill\blacktriangleleft$

7.1 Algorithm overview

Denote $\ell=\lceil\varepsilon^{-2}\log^{2}n\rceil$ . Our algorithm runs on a “clock” denoted by $(h:m:s)$ where:

$\blacksquare$

Each hour $h$ lasts $2\lceil\eta^{-1}\rceil+2$ minutes,
$\blacksquare$

Each even minute $m$ lasts $4\lceil\log_{8/7}n\rceil+2$ rounds,
$\blacksquare$

Each odd minute $m$ in hour $h$ lasts $\ell-h+1$ seconds,
$\blacksquare$

Each second $s$ lasts $\ell+\textnormal{Blocking}(\ell,n)$ rounds.

Each vertex tracks the clock to know which actions of our algorithm it should execute (if any). Our clock is special, in the sense that hours tick downwards. Minutes and seconds tick upwards, starting from zero. Each vertex $v$ in our graph keeps track of the current time, measured in the current hour $h$ , minute $m$ and second $s$ . We maintain the following:

Invariant 1.

During hour $h$ , there are no violating out-edges from level $k$ for all $k>h+1$ . At the start of each even minute in hour $h$ , there are no violating out-edges from level $k$ for all $k>h$ .

This invariant implies that we compute an $\eta$ -fair orientation when the clock reaches $(0:0:0)$ . Going from hour $h$ to hour $h-1$ we maintain this invariant by flipping directed paths:

Definition 25.

For any edge $\overline{uv}$ with $\textsl{g}(u\!\to\!v)>0$ , we say that our algorithm is flipping $\overline{uv}$ whenever it decreases $\textsl{g}(u\!\to\!v)$ (increasing $\textsl{g}(v\!\to\!u)$ ). Moreover, we say that $\overline{uv}$ is flipped whenever our algorithm has decreased $\textsl{g}(u\!\to\!v)$ such that $\textsl{g}(u\!\to\!v)=0$ .

Algorithm (see also Figure 2 and Algorithms 2 and 3 and 4 and 5).

Each time frame has a purpose:

$\blacksquare$
Each hour $h$ , the goal is to identify and “fix” all violating out-edges from vertices in $L_{h}$ ; without introducing violating out-edges from vertices in a level $L_{k}$ with $k>h$ . We do this iteratively, using two different steps:
- –
  
  Each even minute, we fix all violating out-edges from vertices in $L_{h}$ , possibly creating violating out-edges from vertices in $L_{h+1}$ to vetices in $L_{h-1}$ .
- –
  
  Each odd minute, we fix all violating out-edges from vertices in $L_{h+1}$ to vertices in $L_{h-1}$ . We do this in such a manner, that we create no new violating out-edges from vertices in $L_{k}$ for $k>h$ . However, we may create violating out-edges from level $L_{h}$ .
$\blacksquare$
Each even minute $m^{\prime}$ , we define the set $V_{m^{\prime}}\subset L_{h}$ of vertices that have at least one violating out-edge. Over $4\lceil\log_{8/7}n\rceil+2$ rounds, each $u\in V_{m^{\prime}}$ flips violating out-edges $\overline{uv}$ . Moreover:
- –
  
  The out-degree $\textsl{g}(u)$ is decreased such that $u$ drops at most one level, and
- –
  
  The out-degree $\textsl{g}(v)$ such that $v$ increases its level up to at most $h-1$ .
We prove that at the end of this minute $m^{\prime}$ , there exist no more $u\in V_{m^{\prime}}$ with a violating out-edge. Thus, for each vertex $u\in V_{m^{\prime}}$ , either $u$ decreased one level, or all $\overline{uv}$ that were violating now have that $\textsl{g}(u\!\to\!v)=0$ , or $v\in L_{h-1}$ .
$\blacksquare$

In each odd minute $m$ , we inspect the vertices $T_{m}:=\{u\in V_{m-1}\textnormal{ that dropped a level}\}$ . For each $u\in T_{m}$ , for each edge $\overline{wu}$ with $w\in L_{h+1}$ and $\textsl{g}(w\!\to\!u)>0$ the edge $(w,u)$ has become a violating in the previous minute. We want to fix these edges, whilst guaranteeing that we create no violating in-edges from vertices in level $h+2$ and above.
We obtain this, by recording at the start of the minute for every vertex $u$ its level $l_{m}(u)$ . We then invoke $\ell-h+1$ seconds. Each second $s$ , we create a DAG $D_{s}$ where the sinks are $T_{m}$ . We increase for all $u\in T_{m}$ the out-degree $\textsl{g}(u)$ by flipping a directed path from a source in $D_{s}$ to $T_{m}$ . We construct our DAG in such a manner that this procedure does not create new violating in-edges, and that for all seconds $s$ , $D_{s+1}$ is a subgraph of $D_{s}$ .
$\blacksquare$
At the start of second $s$ of each minute $m$ , we fix for every edge $\overline{uv}$ the values $\textsl{g}_{s}(u\!\to\!v)$ , and the levels $l_{s}(u)$ and $l_{s}(v)$ of $u$ and $v$ . We then define a graph $D_{s}=(V_{s},E_{s})$ as follows:
- –
  
  The edges $E_{s}$ are all violating in-edges to vertices in $T_{m}$ plus all $\overline{uv}$ with:
  $l_{s}(u)=l_{m}(u)>h+1$ , $l_{s}(u)>l_{s}(v)$ , and $\textsl{g}_{s}(u\!\to\!v)>0$ .
- –
  
  The vertices $V_{s}$ include $T_{m}$ plus all vertices in $G$ with a directed path to $T_{m}$ in $E_{s}$ .
- –
  
  The vertices $S_{s}\subset V_{s}$ are all sources in $D_{s}$ (these are not in $T_{m}$ ).
For each $v\in T_{m}$ we increase $\textsl{g}(v)$ by flipping a directed path from a vertex in $S_{s}$ to $v$ . We continue this until either $\textsl{g}(v)=(1+\frac{\eta}{2})^{h+1}$ , or, there exist no more edges $(u,v)\in E_{s}$ with $\textsl{g}(u\!\to\!v)>0$ . In both cases, $v$ has no more violating in-edges. To find these directed paths, we create a flow problem on a graph $D_{s}^{*}$ where the maximal path has length $\ell+2$ :
- –
  
  For each $u\in S_{s}$ , we define $\sigma(u)=\textsl{g}(u)-(1+\frac{\eta}{2})^{l_{m}(u)-1}$ (the maximal amount we can decrease $\textsl{g}(u)$ such that is does not arrive in level $l_{m}(u)-2$ ). We connect every $u\in S_{s}$ to a unique source $s_{u}$ where the edge $\overline{s_{u}u}$ has capacity $\sigma(u)$ .
- –
  
  For each $v\in T_{m}$ , we define $\delta(v)=(1+\frac{\eta}{2})^{h+1}-\textsl{g}(v)$ (the maximal amount we can increase $\textsl{g}(v)$ such that it does not arrive in level $h+1$ ). We connect every $v\in T_{m}$ to a unique sink $t_{v}$ where the edge $\overline{vt_{v}}$ has capacity $\delta(v)$ .
- –
  
  Each other edge $\overline{uv}\in E_{s}$ has capacity $\textsl{g}(u\!\to\!v)$ .

Figure 2:

(4:0:0)

– at the first minute start in hour

4

, we consider all violating out-edges

\overline{uv}

from level

4

(red). Per definition, these edges point to level

2

or lower.

(4:0:0)

– at the first minute end, either

u

has dropped a level (pink),

v

increased their level to

h-1

(green) or the edge

\overline{uv}

is flipped (blue). We consider violating in-edges to pink vertices (orange)

(4:1:0)

– at the first second start, we construct a DAG

D_{0}

where the edges are the orange edges plus black edges. The vertex set are all

u

with a directed path to a pink vertex (

v\in T_{1}

). The yellow vertices are

S_{0}

.

(4:1:0)

– at the first second end, edges in the DAG may have flipped (blue), vertices in

S_{0}

may have dropped a level or vertices in

T_{1}

may have increased a level (making some edges no longer violating – purple).

(4:1:1)

– at the second second start, we construct a DAG

D_{1}

. Note that

D_{1}

is a subgraph of

D_{0}

.

7.2 Formal algorithm definition

We now formalise our algorithm top-down, starting with defining variables.

Definition 26.

At the start of $(h,m^{\prime},0)$ , where $m^{\prime}$ is even, we fix the set $V_{m^{\prime}}:=\{v\in L_{h}\mid v\textnormal{ has at least one violating out-% edge}\}.$ At the start of $(h,m,0)$ where $m$ is odd, we fix:

	$\displaystyle T_{m}:=\{v\in V_{m-1}\mid\quad$	$\displaystyle v\textnormal{ decreased by one level in the previous }\textsc{% minute}\textnormal{ and }$
		$\displaystyle v\textnormal{ has at least one violating in-edge}\}.$

Finally, we denote for any vertex $u$ by $l_{m}(u)$ its level at the start of the minute $m$ .

Definition 27.

At the start of $(h:m:s)$ , where $m$ is odd, we fix the following:

$\blacksquare$

For any vertex $u$ , we denote by $l_{s}(u)$ its level at the start of the second.
$\blacksquare$

For any edge $\overline{uv}$ denote by $\textsl{g}_{s}(u\!\to\!v)$ the out-degree from $u$ to $v$ at the start of the second.
$\blacksquare$

We define the edge set $E_{s}$ as all violating in-edges to vertices in $T_{m}$ plus all $\overline{uv}$ with:
$l_{s}(u)=l_{m}(u)>h+1$ , $l_{s}(u)>l_{s}(v)$ , and $\textsl{g}_{s}(u\!\to\!v)>0$ .
$\blacksquare$

$V_{s}$ are all vertices with a directed path to a vertex in $T_{m}$ .
$\blacksquare$

$D_{s}=(V_{s},E_{s})$ is a DAG where $S_{s}$ are all the sources (per definition $S_{s}\cap T_{m}=\emptyset$ ).

Definition 28.

At the start of $(h,m,s)$ where $m$ is odd, given $T_{m}$ , $S_{s}$ and $D_{s}$ , we define the DAG $D_{s}^{*}$ by connecting all $u\in S_{s}$ to a unique sink $s_{u}$ and all $v\in T_{m}$ to a unique sink $t_{v}$ .

$\blacksquare$

For $u\in S_{s}$ , the edge $\overline{s_{u}u}$ has capacity $\sigma(u)=\textsl{g}_{s}(u)-(1+\frac{\eta}{2})^{l_{m}(u)-1}$ .
$\blacksquare$

For $v\in T_{m}$ , the edge $\overline{vt_{v}}$ has capacity $\delta(v)=(1+\frac{\eta}{2})^{h+1}-\textsl{g}_{s}(v)$ .
$\blacksquare$

Each other edge $\overline{uv}\in E_{s}$ has capacity $\textsl{g}_{s}(u\!\to\!v)$ .

Observation 29.

At the start of $(h:m:s)$ with $m$ odd, if every vertex $u$ is given $l_{m}(u)$ , whether $u\in T_{m}$ , and $h$ , then we may compute all elements of Definitions 27 and 28 in $\ell$ rounds.

Algorithm 2 hour(

h

).

Algorithm 3 evenminute(int

h

, int

m

).

Algorithm 4 oddminute(int

h

, int

m

).

Algorithm 5 second(int

h

, int

m

, int

s

).

7.3 Proving our algorithm’s correctness

Per definition, our algorithm runs in $O(\eta^{-1}\log n\cdot\ell\cdot(\ell+\textnormal{Blocking}(\ell,n))=O(% \varepsilon^{-3}\log^{4}n\cdot(\varepsilon^{-2}\log^{2}n+\textnormal{Blocking}% (\varepsilon^{-2}\log^{2}n,n)))$ rounds. What remains is to show that we maintain Invariant 1, which implies that we compute an $\eta$ -fair orientation.
We note that by the choice of our algorithm’s variables, we have the following property:

Observation 30.

For all times $(h:m:s)$ with $m$ odd:

$\blacksquare$

Vertices at level $k>h$ only decrease their level and by at most one (because afterwards, $l_{s}(u)<l_{m}(u)$ and thus $u$ has no out-edges in $E_{s}$ ),
$\blacksquare$

vertices at level $h-1$ only increase their level (by at most $1$ ), and
$\blacksquare$

vertices at level $k^{\prime}<h-1$ and level $h$ do not change their level.

We use this observation in the full version to show that we maintain Invariant 1 by induction. Trivially, Invariant 1 holds at the start of $(\ell:0:0)$ . We now assume that the invariant holds at $(h:0:0)$ , i.e. that there are no violating out-edges from level $L_{k}$ with $k>h$ . We prove that our algorithm ensures that at the start of $(h-1:0:0)$ there are no violating out-edges from level $L_{k}$ with $k\geq h$ .

Moreover, we maintain the invariant that throughout hour $(h-1)$ there are no violating out-edges from level $L_{k^{\prime}}$ with $k^{\prime}>h+1$ . We prove this in the following way:

$\blacksquare$

During $(h:m:s)$ for $m$ even, our algorithm eliminates all violating edges going from $L_{h}$ . We show that in each iteration, the number of violating edges from $L_{h}$ drops by a factor $7/8$ . The graph has at most $n^{2}$ edges. This implies that after the minute, there are no more violating edges going from $L_{h}$ . However, there may now be violating out-edges from vertices in $L_{h+1}$ to vertices in $T_{m+1}\subseteq L_{h-1}$ .
$\blacksquare$

During $(h:m:s)$ for $m$ odd, our algorithm eliminates all violating edges going from $L_{h+1}$ to $T_{m}$ . We show that for all $s$ , the DAG $D_{s}$ is a subgraph of $D_{s-1}$ where the height is one fewer. Since the height of $D_{s}$ is at most $\ell-h+1$ , this implies that after the minute $m$ , the graph $D_{s}$ is empty and there are no more violating in-edges to $T_{m}$ .
$\blacksquare$

Each minute, our algorithm alternates between having violating edges from $L_{h}$ and $L_{h+1}$ . We show that our algorithm can alternate at most $\eta$ times before there are no violating edges from both $L_{h}$ and $L_{h+1}$ , which implies Invariant 1 at the start of $(h-1:0:0)$ .

Invariant 1 implies that we compute an $\eta$ -fair orientation at time $(0:0:0)$ , thus: See 16 We plug in the runtime of Blocking $(h,n)$ of Lemma 21 by Haeupler, Hershkowitz, and Saranurak [21] to obtain the following runtime:

Corollary 31.

There is an algorithm in CONGEST that given a unit-weight graph $G$ and an $\varepsilon>0$ computes an orientation $\overrightarrow{G}$ such that $\forall v\in V$ , the out-degree $\textsl{g}(v)\in[(1+\varepsilon)^{-1}\rho^{*}(v),(1+\varepsilon)\rho^{*}(v)]$ in:

$\blacksquare$

$\tilde{O}(\varepsilon^{-11}\log^{12}n)$ rounds with high probability, or
$\blacksquare$

$\tilde{O}(\varepsilon^{-15}\log^{16}n\cdot 2^{O(\sqrt{\log n})})$ deterministic rounds.

Finally, we apply Corollary 10 which states that $\rho^{\max}(G)=\Delta^{\min}(G)=\max_{v}\textsl{g}^{*}(v)$ to conclude:

Corollary 32.

There is a deterministic algorithm in CONGEST that given a unit-weight graph $G$ and an $\varepsilon>0$ , that computes an orientation $\overrightarrow{G}$ such that:

\max_{v\in V}\textsl{g}(v)\in[(1+\varepsilon)^{-1}\rho^{\max}(G),(1+% \varepsilon)\rho^{\max}(G)],

in a number of rounds that is sublinear in $n$ .

This is the first deterministic sublinear algorithm that solves Problem 2.2.

References

[1] Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. Densest subgraph in streaming and mapreduce. Proc. VLDB Endow., 5(5):454–465, 2012. doi:10.14778/2140436.2140442.
[2] Soheil Behnezhad, Mahsa Derakhshan, Alireza Farhadi, MohammadTaghi Hajiaghayi, and Nima Reyhani. Stochastic matching on uniformly sparse graphs. In Algorithmic Game Theory: 12th International Symposium, SAGT 2019, Athens, Greece, September 30 – October 3, 2019, Proceedings, pages 357–373, Berlin, Heidelberg, 2019. Springer-Verlag. doi:10.1007/978-3-030-30473-7_24.
[3] Suman K. Bera, Sayan Bhattacharya, Jayesh Choudhari, and Prantar Ghosh. A new dynamic algorithm for densest subhypergraphs. In Frédérique Laforest, Raphaël Troncy, Elena Simperl, Deepak Agarwal, Aristides Gionis, Ivan Herman, and Lionel Médini, editors, WWW ’22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 - 29, 2022, pages 1093–1103. ACM, 2022. doi:10.1145/3485447.3512158.
[4] Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos E. Tsourakakis. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 173–182. ACM, 2015. doi:10.1145/2746539.2746592.
[5] Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos Tsourakakis, Di Wang, and Junxing Wang. Flowless: Extracting densest subgraphs without flow computations. In Proceedings of The Web Conference 2020, 2020.
[6] Glencora Borradaile, Jennifer Iglesias, Theresa Migler, Antonio Ochoa, Gordon Wilfong, and Lisa Zhang. Egalitarian graph orientations. Journal of Graph Algorithms and Applications, 2017.
[7] Glencora Borradaile, Theresa Migler, and Gordon Wilfong. Density decompositions of networks. In Conference on Complex Networks (CompleNet). Springer, 2018.
[8] Gerth Stølting Brodal and Rolf Fagerberg. Dynamic representations of sparse graphs. In In Proc. 6th International Workshop on Algorithms and Data Structures (WADS), pages 342–351. Springer-Verlag, 1999. doi:10.1007/3-540-48447-7_34.
[9] Moses Charikar. Greedy approximation algorithms for finding dense components in a graph. In Approximation Algorithms for Combinatorial Optimization (APPROX). Springer, 2003.
[10] Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quanrud, Eva Rotenberg, and Chris Schwiegelshohn. Adaptive out-orientations with applications. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3062–3088. SIAM, 2024.
[11] Chandra Chekuri, Kent Quanrud, and Manuel R Torres. Densest subgraph: Supermodularity, iterative peeling, and flow. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2022.
[12] Aleksander Bjørn Grodt Christiansen, Krzysztof Nowicki, and Eva Rotenberg. Improved dynamic colouring of sparse graphs. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 1201–1214. ACM, 2023. doi:10.1145/3564246.3585111.
[13] Aleksander Bjørn Grodt Christiansen and Eva Rotenberg. Fully-Dynamic $\alpha+2$ Arboricity Decompositions and Implicit Colouring. In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1–42:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2022.42.
[14] Maximilien Danisch, T.-H. Hubert Chan, and Mauro Sozio. Large scale density-friendly graph decomposition via convex programming. In Proceedings of the 26th International Conference on World Wide Web, WWW ’17, pages 233–242, Republic and Canton of Geneva, CHE, 2017. International World Wide Web Conferences Steering Committee. doi:10.1145/3038912.3052619.
[15] Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, and Amitabh Trehan. Dense subgraphs on dynamic networks. In Marcos K. Aguilera, editor, Distributed Computing - 26th International Symposium, DISC 2012, Salvador, Brazil, October 16-18, 2012. Proceedings, volume 7611 of Lecture Notes in Computer Science, pages 151–165. Springer, 2012. doi:10.1007/978-3-642-33651-5_11.
[16] Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn. Deterministic distributed edge-coloring via hypergraph maximal matching. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 180–191. IEEE, 2017. doi:10.1109/FOCS.2017.25.
[17] András Frank and Kazuo Murota. Fair integral network flows. Mathematics of Operations Research, 2023.
[18] Satoru Fujishige. Lexicographically optimal base of a polymatroid with respect to a weight vector. Mathematics of Operations Research, 5(2):186–196, 1980. doi:10.1287/MOOR.5.2.186.
[19] Mohsen Ghaffari, David G Harris, and Fabian Kuhn. On derandomizing local distributed algorithms. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 662–673. IEEE, 2018. doi:10.1109/FOCS.2018.00069.
[20] Mohsen Ghaffari and Hsin-Hao Su. Distributed degree splitting, edge coloring, and orientations. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2505–2523. SIAM, 2017. doi:10.1137/1.9781611974782.166.
[21] Bernhard Haeupler, D Ellis Hershkowitz, and Thatchaphol Saranurak. Maximum length-constrained flows and disjoint paths: Distributed, deterministic, and fast. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1371–1383, 2023. doi:10.1145/3564246.3585202.
[22] Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. Faster and scalable algorithms for densest subgraph and decomposition. Advances in Neural Information Processing Systems, 35:26966–26979, 2022.
[23] Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. Convergence to lexicographically optimal base in a (contra) polymatroid and applications to densest subgraph and tree packing. In European Symposium on Algorithms (ESA). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.ESA.2023.56.
[24] David G Harris. Distributed local approximation algorithms for maximum matching in graphs and hypergraphs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 700–724. IEEE, 2019. doi:10.1109/FOCS.2019.00048.
[25] Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein. Fully dynamic mis in uniformly sparse graphs. ACM Trans. Algorithms, 16(2), March 2020. doi:10.1145/3378025.
[26] Lu Qin, Rong-Hua Li, Lijun Chang, and Chengqi Zhang. Locally densest subgraph discovery. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’15, pages 965–974, New York, NY, USA, 2015. Association for Computing Machinery. doi:10.1145/2783258.2783299.
[27] Saurabh Sawlani and Junxing Wang. Near-optimal fully dynamic densest subgraph. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 181–193, 2020. doi:10.1145/3357713.3384327.
[28] Hsin-Hao Su and Hoa T. Vu. Distributed dense subgraph detection and low outdegree orientation. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, volume 179 of LIPIcs, pages 15:1–15:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.DISC.2020.15.
[29] Nikolaj Tatti and Aristides Gionis. Density-friendly graph decomposition. In Proceedings of the 24th International Conference on World Wide Web, WWW ’15, pages 1089–1099, Republic and Canton of Geneva, CHE, 2015. International World Wide Web Conferences Steering Committee. doi:10.1145/2736277.2741119.
[30] Yalong Zhang, Rong-Hua Li, Qi Zhang, Hongchao Qin, and Guoren Wang. Efficient algorithms for density decomposition on large static and dynamic graphs. Proceedings of the VLDB Endowment, 2024.

[bib.bib1] [1] Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. Densest subgraph in streaming and mapreduce. Proc. VLDB Endow., 5(5):454–465, 2012. doi:10.14778/2140436.2140442.

[bib.bib2] [2] Soheil Behnezhad, Mahsa Derakhshan, Alireza Farhadi, MohammadTaghi Hajiaghayi, and Nima Reyhani. Stochastic matching on uniformly sparse graphs. In Algorithmic Game Theory: 12th International Symposium, SAGT 2019, Athens, Greece, September 30 – October 3, 2019, Proceedings, pages 357–373, Berlin, Heidelberg, 2019. Springer-Verlag. doi:10.1007/978-3-030-30473-7_24.

[bib.bib3] [3] Suman K. Bera, Sayan Bhattacharya, Jayesh Choudhari, and Prantar Ghosh. A new dynamic algorithm for densest subhypergraphs. In Frédérique Laforest, Raphaël Troncy, Elena Simperl, Deepak Agarwal, Aristides Gionis, Ivan Herman, and Lionel Médini, editors, WWW ’22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 - 29, 2022, pages 1093–1103. ACM, 2022. doi:10.1145/3485447.3512158.

[bib.bib4] [4] Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos E. Tsourakakis. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 173–182. ACM, 2015. doi:10.1145/2746539.2746592.

[bib.bib5] [5] Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos Tsourakakis, Di Wang, and Junxing Wang. Flowless: Extracting densest subgraphs without flow computations. In Proceedings of The Web Conference 2020, 2020.

[bib.bib6] [6] Glencora Borradaile, Jennifer Iglesias, Theresa Migler, Antonio Ochoa, Gordon Wilfong, and Lisa Zhang. Egalitarian graph orientations. Journal of Graph Algorithms and Applications, 2017.

[bib.bib7] [7] Glencora Borradaile, Theresa Migler, and Gordon Wilfong. Density decompositions of networks. In Conference on Complex Networks (CompleNet). Springer, 2018.

[bib.bib8] [8] Gerth Stølting Brodal and Rolf Fagerberg. Dynamic representations of sparse graphs. In In Proc. 6th International Workshop on Algorithms and Data Structures (WADS), pages 342–351. Springer-Verlag, 1999. doi:10.1007/3-540-48447-7_34.

[bib.bib9] [9] Moses Charikar. Greedy approximation algorithms for finding dense components in a graph. In Approximation Algorithms for Combinatorial Optimization (APPROX). Springer, 2003.

[bib.bib10] [10] Chandra Chekuri, Aleksander Bjørn Christiansen, Jacob Holm, Ivor van der Hoog, Kent Quanrud, Eva Rotenberg, and Chris Schwiegelshohn. Adaptive out-orientations with applications. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3062–3088. SIAM, 2024.

[bib.bib11] [11] Chandra Chekuri, Kent Quanrud, and Manuel R Torres. Densest subgraph: Supermodularity, iterative peeling, and flow. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2022.

[bib.bib12] [12] Aleksander Bjørn Grodt Christiansen, Krzysztof Nowicki, and Eva Rotenberg. Improved dynamic colouring of sparse graphs. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 1201–1214. ACM, 2023. doi:10.1145/3564246.3585111.

[bib.bib13] [13] Aleksander Bjørn Grodt Christiansen and Eva Rotenberg. Fully-Dynamic $\alpha+2$ Arboricity Decompositions and Implicit Colouring. In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42:1–42:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2022.42.

[bib.bib14] [14] Maximilien Danisch, T.-H. Hubert Chan, and Mauro Sozio. Large scale density-friendly graph decomposition via convex programming. In Proceedings of the 26th International Conference on World Wide Web, WWW ’17, pages 233–242, Republic and Canton of Geneva, CHE, 2017. International World Wide Web Conferences Steering Committee. doi:10.1145/3038912.3052619.

[bib.bib15] [15] Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, and Amitabh Trehan. Dense subgraphs on dynamic networks. In Marcos K. Aguilera, editor, Distributed Computing - 26th International Symposium, DISC 2012, Salvador, Brazil, October 16-18, 2012. Proceedings, volume 7611 of Lecture Notes in Computer Science, pages 151–165. Springer, 2012. doi:10.1007/978-3-642-33651-5_11.

[bib.bib16] [16] Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn. Deterministic distributed edge-coloring via hypergraph maximal matching. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 180–191. IEEE, 2017. doi:10.1109/FOCS.2017.25.

[bib.bib17] [17] András Frank and Kazuo Murota. Fair integral network flows. Mathematics of Operations Research, 2023.

[bib.bib18] [18] Satoru Fujishige. Lexicographically optimal base of a polymatroid with respect to a weight vector. Mathematics of Operations Research, 5(2):186–196, 1980. doi:10.1287/MOOR.5.2.186.

[bib.bib19] [19] Mohsen Ghaffari, David G Harris, and Fabian Kuhn. On derandomizing local distributed algorithms. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 662–673. IEEE, 2018. doi:10.1109/FOCS.2018.00069.

[bib.bib20] [20] Mohsen Ghaffari and Hsin-Hao Su. Distributed degree splitting, edge coloring, and orientations. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2505–2523. SIAM, 2017. doi:10.1137/1.9781611974782.166.

[bib.bib21] [21] Bernhard Haeupler, D Ellis Hershkowitz, and Thatchaphol Saranurak. Maximum length-constrained flows and disjoint paths: Distributed, deterministic, and fast. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1371–1383, 2023. doi:10.1145/3564246.3585202.

[bib.bib22] [22] Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. Faster and scalable algorithms for densest subgraph and decomposition. Advances in Neural Information Processing Systems, 35:26966–26979, 2022.

[bib.bib23] [23] Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. Convergence to lexicographically optimal base in a (contra) polymatroid and applications to densest subgraph and tree packing. In European Symposium on Algorithms (ESA). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.ESA.2023.56.

[bib.bib24] [24] David G Harris. Distributed local approximation algorithms for maximum matching in graphs and hypergraphs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 700–724. IEEE, 2019. doi:10.1109/FOCS.2019.00048.

[bib.bib25] [25] Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein. Fully dynamic mis in uniformly sparse graphs. ACM Trans. Algorithms, 16(2), March 2020. doi:10.1145/3378025.

[bib.bib26] [26] Lu Qin, Rong-Hua Li, Lijun Chang, and Chengqi Zhang. Locally densest subgraph discovery. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’15, pages 965–974, New York, NY, USA, 2015. Association for Computing Machinery. doi:10.1145/2783258.2783299.

[bib.bib27] [27] Saurabh Sawlani and Junxing Wang. Near-optimal fully dynamic densest subgraph. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 181–193, 2020. doi:10.1145/3357713.3384327.

[bib.bib28] [28] Hsin-Hao Su and Hoa T. Vu. Distributed dense subgraph detection and low outdegree orientation. In Hagit Attiya, editor, 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, volume 179 of LIPIcs, pages 15:1–15:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.DISC.2020.15.

[bib.bib29] [29] Nikolaj Tatti and Aristides Gionis. Density-friendly graph decomposition. In Proceedings of the 24th International Conference on World Wide Web, WWW ’15, pages 1089–1099, Republic and Canton of Geneva, CHE, 2015. International World Wide Web Conferences Steering Committee. doi:10.1145/2736277.2741119.

[bib.bib30] [30] Yalong Zhang, Rong-Hua Li, Qi Zhang, Hongchao Qin, and Guoren Wang. Efficient algorithms for density decomposition on large static and dynamic graphs. Proceedings of the VLDB Endowment, 2024.