BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Zeev Nutov

Zeev Nutov contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and Algorithms

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
1topics
2close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2026arXiv

On $k$-connectivity oracles in $k$-connected graphs

A $k$-connectivity oracle for a graph $G=(V,E)$ is a data structure that given $s,t \in V$ determines whether there are at least $k+1$ internally disjoint $st$-paths in $G$. For undirected graphs, Pettie, Saranurak & Yin [STOC 2022, pp. 151-161] proved that any $k$-connectivity oracle requires $Ω(kn)$ bits of space. They asked whether $Ω(kn)$ bits are still necessary if $G$ is $k$-connected. We will show by a very simple proof that this is so even if $G$ is $k$-connected, answering this open question.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

$2$-node-connectivity network design

We consider network design problems in which we are given a graph and seek a min-size $2$-connected subgraph that satisfies a prescribed property. $\bullet$ In the 1-Connectivity Augmentation problem the goal is to augment a connected graph by a min-size edge subset of a specified edge set such that the augmented graph is $2$-connected. We breach the natural ratio of $2$ for this problem and also for the more general Crossing Family Cover problem. $\bullet$ In the $2$-Connected Dominating Set problem we seek a minimum size $2$-connected subgraph that dominates all nodes. We give the first non-trivial approximation algorithm for this problem, with expected ratio $O(σ\log^3 n)$, where $σ=O(\log n \cdot\log\log n\cdot(\log\log\log n)^{3})$. The unifying technique of both results is a reduction to the Subset Steiner Connected Dominating Set problem. Such a reduction was known for edge-connectivity, and we extend it to $2$-node connectivity problems. We show that the same method can be used to obtain easily polylogarithmic approximation ratios that are not too far from the best known ones for several other problems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

$k$ disjoint $st$-paths activation in polynomial time

In activation network design problems we are given an undirected graph $G=(V,E)$ and a pair of activation costs $\{c_e^u,c_e^v\}$ for each $e=uv \in E$. The goal is to find an edge set $F \subseteq E$ that satisfies a prescribed property of minimum activation cost $τ(F)=\sum_{v \in V} \max \{c_e^v: e \in F \mbox{ is incident to } v\}$. In the Activation $k$ Disjoint Paths problem we are given $s,t \in V$ and an integer $k$, and seek an edge set $F \subseteq E$ of $k$ internally disjoint $st$-paths of minimum activation cost. The problem admits an easy $2$-approximation algorithm. However, it was an open question whether the problem is in P even for $k=2$ and power activation costs, when $c_e^u=c_e^v$ for all $e=uv \in E$. Here we will answer this question by giving a polynomial time algorithm using linear programing. We will also mention several consequences, among them a polynomial time algorithm for the Activation 2 Edge Disjoint Paths problem, and improved approximation ratios for the Min-Power $k$-Connected Subgraph problem.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Parameterized algorithms for node connectivity augmentation problems

A graph $G$ is $k$-out-connected from its node $s$ if it contains $k$ internally disjoint $sv$-paths to every node $v$; $G$ is $k$-connected if it is $k$-out-connected from every node. In connectivity augmentation problems the goal is to augment a graph $G_0=(V,E_0)$ by a minimum costs edge set $J$ such that $G_0 \cup J$ has higher connectivity than $G_0$. In the $k$-Out-Connectivity Augmentation ($k$-OCA) problem, $G_0$ is $(k-1)$-out-connected from $s$ and $G_0 \cup J$ should be $k$-out-connected from $s$; in the $k$-Connectivity Augmentation ($k$-CA) problem $G_0$ is $(k-1)$-connected and $G_0 \cup J$ should be $k$-connected. The parameterized complexity status of these problems was open even for $k=3$ and unit costs. We will show that $k$-OCA and $3$-CA can be solved in time $9^p \cdot n^{O(1)}$, where $p$ is the size of an optimal solution. Our paper is the first that shows fixed parameter tractability of a $k$-node-connectivity augmentation problem with high values of $k$. We will also consider the $(2,k)$-Connectivity Augmentation problem where $G_0$ is $(k-1)$-edge-connected and $G_0 \cup J$ should be both $k$-edge-connected and $2$-connected. We will show that this problem can be solved in time $9^p \cdot n^{O(1)}$, and for unit costs approximated within $1.892$.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Practical Budgeted Submodular Maximization

We consider the problem of maximizing a non-negative monotone submodular function subject to a knapsack constraint, which is also known as the Budgeted Submodular Maximization (BSM) problem. Sviridenko (2004) showed that by guessing 3 appropriate elements of an optimal solution, and then executing a greedy algorithm, one can obtain the optimal approximation ratio of $α=1-1/e\approx 0.632$ for BSM. However, the need to guess (by enumeration) 3 elements makes the algorithm of Sviridenko impractical as it leads to a time complexity of $O(n^5)$ (which can be slightly improved using the thresholding technique of Badanidiyuru & Vondrak (2014), but only to roughly $O(n^4)$). Our main results in this paper show that fewer guesses suffice. Specifically, by making only 2 guesses, we get the same optimal approximation ratio of $α$ with an improved time complexity of roughly $O(n^3)$. Furthermore, by making only a single guess, we get an almost as good approximation ratio of $0.6174>0.9767α$ in roughly $O(n^2)$ time. Prior to our work, the only algorithms that were known to obtain an approximation ratio close to $α$ for BSM were the algorithm of Sviridenko and an algorithm of Ene & Nguyen (2019) that achieves $(α-ε)$-approximation. However, the algorithm of Ene & Nguyen requires ${(1/ε)}^{O(1/ε^4)}n\log^2 n$ time, and hence, is of theoretical interest only as ${(1/ε)}^{O(1/ε^4)}$ is huge even for moderate values of $ε$. In contrast, all the algorithms we analyze are simple and parallelizable, which makes them good candidates for practical use. Recently, Tang et al. (2020) studied a simple greedy algorithm that already has a long research history, and proved that its approximation ratio is at least 0.405. We improve over this result, and show that the approximation ratio of this algorithm is within the range [0.427, 0.462].

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Small $\ell$-edge-covers in $k$-connected graphs

Let $G=(V,E)$ be a $k$-edge-connected graph with edge costs $\{c(e):e \in E\}$ and let $1 \leq \ell \leq k-1$. We show by a simple and short proof, that $G$ contains an $\ell$-edge cover $I$ such that: $c(I) \leq \frac{\ell}{k}c(E)$ if $G$ is bipartite, or if $\ell |V|$ is even, or if $|E| \geq \frac{k|V|}{2} +\frac{k}{2\ell}$; otherwise, $c(I) \leq (\frac{\ell}{k}+\frac{1}{k|V|})c(E)$. The particular case $\ell=k-1$ and unit costs already includes a result of Cheriyan and Thurimella, that $G$ contains a $(k-1)$-edge-cover of size $|E|-\lfloor |V|/2 \rfloor$. Using our result, we slightly improve the approximation ratios for the {\sf $k$-Connected Subgraph} problem (the node-connectivity version) with uniform and $β$-metric costs. We then consider the dual problem of finding a spanning subgraph of maximum connectivity $k^*$ with a prescribed number of edges. We give an algorithm that computes a $(k^*-1)$-connected subgraph, which is tight, since the problem is NP-hard.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Approximating subset $k$-connectivity problems

A subset $T \subseteq V$ of terminals is $k$-connected to a root $s$ in a directed/undirected graph $J$ if $J$ has $k$ internally-disjoint $vs$-paths for every $v \in T$; $T$ is $k$-connected in $J$ if $T$ is $k$-connected to every $s \in T$. We consider the {\sf Subset $k$-Connectivity Augmentation} problem: given a graph $G=(V,E)$ with edge/node-costs, node subset $T \subseteq V$, and a subgraph $J=(V,E_J)$ of $G$ such that $T$ is $k$-connected in $J$, find a minimum-cost augmenting edge-set $F \subseteq E \setminus E_J$ such that $T$ is $(k+1)$-connected in $J \cup F$. The problem admits trivial ratio $O(|T|^2)$. We consider the case $|T|>k$ and prove that for directed/undirected graphs and edge/node-costs, a $ρ$-approximation for {\sf Rooted Subset $k$-Connectivity Augmentation} implies the following ratios for {\sf Subset $k$-Connectivity Augmentation}: (i) $b(ρ+k) + {(\frac{3|T|}{|T|-k})}^2 H(\frac{3|T|}{|T|-k})$; (ii) $ρ\cdot O(\frac{|T|}{|T|-k} \log k)$, where b=1 for undirected graphs and b=2 for directed graphs, and $H(k)$ is the $k$th harmonic number. The best known values of $ρ$ on undirected graphs are $\min\{|T|,O(k)\}$ for edge-costs and $\min\{|T|,O(k \log |T|)\}$ for node-costs; for directed graphs $ρ=|T|$ for both versions. Our results imply that unless $k=|T|-o(|T|)$, {\sf Subset $k$-Connectivity Augmentation} admits the same ratios as the best known ones for the rooted version. This improves the ratios in \cite{N-focs,L}.

0 citations0 reviewsNo code linkedOpen access