Dror Rawitz

TCS Journal 2025 Journal Article

On the role of the equal partition in degree realization by a bipartite graph

• Amotz Bar-Noy
• Toni Böhnlein
• David Peleg
• Dror Rawitz

Necessary and sufficient conditions for a pair of integer sequences to be the degree sequences of the two sides of a bipartite graph were established more than six decades ago by Gale and Ryser. In contrast, the general question of deciding whether a single sequence is bigraphic, namely, can be realized by a bipartite graph, is still open. We consider even sequences, in which the multiplicity of any integer in the degree sequence is even. One can always partition an even sequence into two identical sequences, resulting in an equal partition. We show that if a given even sequence d is graphic, then there are only two options: either d is bigraphic, or d is 2-bigraphic, namely, can be realized by a bipartite multigraph with maximum multiplicity 2. For an r -graphic sequence we show that it is t -bigraphic for some t ≤ 2 r, and we also show that the analysis is tight, namely that t = 2 r is possible. In addition, we show that given an r -graphic sequence d, there exists an even sequence d ′ which is similar to d in a well-defined sense such that d ′ is even and r -graphic, and therefore t -bigraphic for some t ≤ 2 r.

TCS Journal 2024 Journal Article

Graph realization of distance sets

• Amotz Bar-Noy
• David Peleg
• Mor Perry
• Dror Rawitz

The Distance Realization problem is defined as follows. Given an n × n matrix D of nonnegative integers, interpreted as inter-vertex distances, find an n-vertex weighted or unweighted graph G realizing D, i. e. , whose inter-vertex distances satisfy d i s t G ( i, j ) = D i, j for every 1 ≤ i < j ≤ n, or decide that no such realizing graph exists. The problem was studied for general weighted and unweighted graphs, as well as for cases where the realizing graph is restricted to a specific family of graphs (e. g. , trees or bipartite graphs). An extension of Distance Realization that was studied in the past is where each entry in the matrix D may contain a range of consecutive permissible values. We refer to this extension as Range Distance Realization (or Range-DR). Restricting each range to at most k values yields the problem k-Range Distance Realization (or k-Range-DR). The current paper introduces a new extension of Distance Realization, in which each entry D i, j of the matrix may contain an arbitrary set of acceptable values for the distance between i and j, for every 1 ≤ i < j ≤ n. We refer to this extension as Set Distance Realization (Set-DR), and to the restricted problem where each entry may contain at most k values as k-Set Distance Realization (or k-Set-DR). We first show that 2-Range-DR is NP-hard for unweighted graphs (implying the same for 2-Set-DR). Next we prove that 2-Set-DR is NP-hard for unweighted and weighted trees. Finally, we explore Set-DR where the realization is restricted to the families of stars, paths, cycles, or caterpillars. For the weighted case, our positive results are that there exist polynomial time algorithms for the 2-Set-DR problem on stars, paths and cycles, and for the 1-Set-DR problem on caterpillars. On the hardness side, we prove that 6-Set-DR is NP-hard for stars and 5-Set-DR is NP-hard for paths, cycles and caterpillars. For the unweighted case, our results are the same, except for the case of unweighted stars, for which k-Set-DR is polynomially solvable for any k.

MFCS Conference 2024 Conference Paper

On Key Parameters Affecting the Realizability of Degree Sequences (Invited Paper)

• Amotz Bar-Noy
• Toni Böhnlein
• David Peleg
• Yingli Ran
• Dror Rawitz

Call a sequence d = (d_1, d_2, …, d_n) of positive integers graphic, planaric, outer-planaric, or forestic if it is the degree sequence of some arbitrary, planar, outer-planar, or cycle-free graph G, respectively. The two extreme classes of graphic and forestic sequences were given full characterizations. (The latter has a particularly simple criterion: d is forestic if and only if its volume, ∑ d ≡ ∑_i d_i, satisfies ∑ d ≤ 2n - 2.) In contrast, the problems of fully characterizing planaric and outer-planaric degree sequences are still open. In this paper, we discuss the parameters affecting the realizability of degree sequences by restricted classes of sparse graph, including planar graphs, outerplanar graphs, and some of their subclasses (e. g. , 2-trees and cactus graphs). A key parameter is the volume of the sequence d, namely, ∑ d which is twice the number of edges in the realizing graph. For planar graphs, for example, an obvious consequence of Euler’s theorem is that an n-element sequence d satisfying ∑ d > 4n-6 cannot be planaric. Hence, ∑ d ≤ 4n-6 is a necessary condition for d to be planaric. What about the opposite direction? Is there an upper bound on ∑ d that guarantees that if d is graphic then it is also planaric. Does the answer depend on additional parameters? The same questions apply also to sub-classes of the planar graphs. A concrete example that is illustrated in the technical part of the paper is the class of outer-planaric degree sequences. Denoting the number of 1’s in d by ω₁, we show that for a graphic sequence d, if ω₁ = 0 then d is outer-planaric when ∑ d ≤ 3n-3, and if ω₁ > 0 then d is outer-planaric when ∑ d ≤ 3n-ω₁-2. Conversely, we show that there are graphic sequences that are not outer-planaric with ω₁ = 0 and ∑ d = 3n-2, as well as ones with ω₁ > 0 and ∑ d = 3n-ω₁-1.

MFCS Conference 2024 Conference Paper

Sparse Graphic Degree Sequences Have Planar Realizations

• Amotz Bar-Noy
• Toni Böhnlein
• David Peleg
• Yingli Ran
• Dror Rawitz

A sequence d = (d_1, d_2, …, d_n) of positive integers is graphic if it is the degree sequence of some simple graph G, and planaric if it is the degree sequence of some simple planar graph G. It is known that if ∑ d ≤ 2n - 2, then d has a realization by a forest, hence it is trivially planaric. In this paper, we seek bounds on ∑ d that guarantee that if d is graphic then it is also planaric. We show that this holds true when ∑ d ≤ 4n-4-2ω₁, where ω₁ is the number of 1’s in d. Conversely, we show that there are graphic sequences with ∑ d = 4n-2ω₁ that are non-planaric. For the case ω₁ = 0, we show that d is planaric when ∑ d ≤ 4n-4. Conversely, we show that there is a graphic sequence with ∑ d = 4n-2 that is non-planaric. In fact, when ∑ d ≤ 4n-6-2ω₁, d can be realized by a graph with a 2-page book embedding.

TCS Journal 2023 Journal Article

Overflow management with self-eliminations

• Assaf Rabinowitz
• Dror Rawitz

We study admission control with packet redundancy, where large data items, called superpackets, exceed some Maximum Transmission Unit (MTU) and therefore are broken into several smaller packets. It is assumed that each superpacket is comprised of k packets, and that a superpacket is considered useful if at least ( 1 − β ) k of its packets arrive at the receiving end, for some redundancy parameter β ∈ [ 0, 1 ). Our goal is to maximize the total profit of useful superpackets, under an overloaded network, where we are forced to drop packets. Our starting point is an algorithm, called priority, which is based on assigning a random priority to each superpacket. This algorithm was shown to perform well when β = 0, with and without a buffer. However, the performance of priority deteriorates with the increase of β, since it delivers too many packets for high priority superpackets. To tackle this issue, we propose an online algorithm which introduces randomized self-elimination of packets, called pse. When there is no buffer, we show that the competitive ratio of pse is better than the competitive ratio of priority, for the case where ( 1 − β ) 3 ⋅ ρ max ≤ 1, where ρ max is the maximal burst size-router capacity ratio. For real-world values ( ρ max ≤ 1. 5 ), pse outperforms priority for β ≥ 0. 14. We also present simulation results, with a buffer, that demonstrate the behavior of pse in comparison with priority and tail-drop. It is shown that pse performs much better than priority when β is large. In fact, it is shown that pse behaves at least as good as both algorithms.

MFCS Conference 2022 Conference Paper

Graph Realization of Distance Sets

• Amotz Bar-Noy
• David Peleg
• Mor Perry
• Dror Rawitz

The Distance Realization problem is defined as follows. Given an n × n matrix D of nonnegative integers, interpreted as inter-vertex distances, find an n-vertex weighted or unweighted graph G realizing D, i. e. , whose inter-vertex distances satisfy dist_G(i, j) = D_{i, j} for every 1 ≤ i < j ≤ n, or decide that no such realizing graph exists. The problem was studied for general weighted and unweighted graphs, as well as for cases where the realizing graph is restricted to a specific family of graphs (e. g. , trees or bipartite graphs). An extension of Distance Realization that was studied in the past is where each entry in the matrix D may contain a range of consecutive permissible values. We refer to this extension as Range Distance Realization (or Range-DR). Restricting each range to at most k values yields the problem k-Range Distance Realization (or k-Range-DR). The current paper introduces a new extension of Distance Realization, in which each entry D_{i, j} of the matrix may contain an arbitrary set of acceptable values for the distance between i and j, for every 1 ≤ i < j ≤ n. We refer to this extension as Set Distance Realization (Set-DR), and to the restricted problem where each entry may contain at most k values as k-Set Distance Realization (or k-Set-DR). We first show that 2-Range-DR is NP-hard for unweighted graphs (implying the same for 2-Set-DR). Next we prove that 2-Set-DR is NP-hard for unweighted and weighted trees. We then explore Set-DR where the realization is restricted to the families of stars, paths, or cycles. For the weighted case, our positive results are that for each of these families there exists a polynomial time algorithm for 2-Set-DR. On the hardness side, we prove that 6-Set-DR is NP-hard for stars and 5-Set-DR is NP-hard for paths and cycles. For the unweighted case, our results are the same, except for the case of unweighted stars, for which k-Set-DR is polynomially solvable for any k.

MFCS Conference 2022 Conference Paper

On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph

• Amotz Bar-Noy
• Toni Böhnlein
• David Peleg
• Dror Rawitz

We consider the problem of characterizing degree sequences that can be realized by a bipartite graph. If a partition of the sequence into the two sides of the bipartite graph is given as part of the input, then a complete characterization has been established over 60 years ago. However, the general question, in which a partition and a realizing graph need to be determined, is still open. We investigate the role of an important class of special partitions, called High-Low partitions, which separate the degrees of a sequence into two groups, the high degrees and the low degrees. We show that when the High-Low partition exists and satisfies some natural properties, analysing the High-Low partition resolves the bigraphic realization problem. For sequences that are known to be not realizable by a bipartite graph or that are undecided, we provide approximate realizations based on the High-Low partition.

TCS Journal 2022 Journal Article

On vertex-weighted realizations of acyclic and general graphs

• Amotz Bar-Noy
• Toni Böhnlein
• David Peleg
• Dror Rawitz

Consider the following natural variation of the degree realization problem. Let G = ( V, E ) be a simple undirected graph of order n. Let f ∈ R ≥ 0 n be a vector of vertex requirements, and let w ∈ R ≥ 0 n be a vector of provided services at the vertices. Then w satisfies f on G if the constraints ∑ j ∈ N ( i ) w j = f i are satisfied for all i ∈ V, where N ( i ) denotes the neighbourhood of vector i. Given a requirements vector f, the Vertex-Weighted Graph Realization problem asks for a suitable graph G and a vector w of provided services that satisfy f on G. In this paper, we consider two avenues. We initiate a study that focuses on weighted realizations where the graph is required to be of a specific class by providing a full characterization of realizable requirement vectors for paths and acyclic graphs. However, checking the respective criteria is shown to be NP-hard. In the second part, we advance the study in general graphs which was started in [2]. For the unsolved cases, the question of whether a vector f is realizable can be formulated as whether its largest requirement lies within certain intervals. We describe several new, realizable intervals and show the existence of an interval that cannot be realized. The complete classification for general graphs is an open problem.

TCS Journal 2021 Journal Article

“Green” barrier coverage with mobile sensors

• Amotz Bar-Noy
• Thomas Erlebach
• Dror Rawitz
• Peter Terlecky

Mobile sensors are located on a barrier represented by a line segment. Each sensor has a single energy source that can be used for both moving and sensing. A sensor consumes energy in movement in proportion to distance traveled, and it expends energy per time unit for sensing in direct proportion to its radius raised to a constant exponent. We address the problem of energy efficient coverage. The input consists of the initial locations of the sensors and a coverage time requirement t. A feasible solution consists of an assignment of destinations and coverage radii to all sensors such that the barrier is covered. We consider two variants of the problem that are distinguished by whether the radii are given as part of the input. In the fixed radii case, we are also given a radii vector ρ, and the radii assignment r must satisfy r i ∈ { 0, ρ i }, for every i, while in the variable radii case the radii assignment is unrestricted. The goal is to cover the barrier for t time in an energy efficient manner. More specifically, we consider two objective functions. In the first the goal is to minimize the sum of the energy spent by all sensors and in the second the goal is to minimize the maximum energy used by any sensor. We present fully polynomial time approximation schemes for the problem of minimizing the energy sum with variable radii and for the problem of minimizing the maximum energy with variable radii. We also show that the latter can be approximated within any additive constant ε > 0. We present a 2-approximation algorithm for the problem of minimizing the maximum energy with fixed radii which also is shown to be strongly NP-hard. We show that the problem of minimizing the energy sum with fixed radii cannot be approximated within a factor of O ( n c ), for any constant c, unless P = NP. Additional results are given for three special cases: (i) sensors are stationary, (ii) free movement, and (iii) uniform fixed radii.

TCS Journal 2020 Journal Article

Simple and local independent set approximation

• Ravi B. Boppana
• Magnús M. Halldórsson
• Dror Rawitz

We study the worst-case behavior of Turán-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, we revisit a randomized approach of Boppana that forms a simple 1-round distributed algorithm, as well as a streaming algorithm and a preemptive online algorithm. We show that it gives a tight ( Δ + 1 ) / 2 -approximation in unweighted graphs of maximum degree Δ, which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a ( Δ + 1 ) -approximation, but a simple modification results in an asymptotic expected 0. 529 ( Δ + 1 ) -approximation.

TCS Journal 2020 Journal Article

Vertex-weighted realizations of graphs

• Amotz Bar-Noy
• David Peleg
• Dror Rawitz

Given a degree sequence d ¯ of length n, the degree realization problem is to decide if d ¯ has a realization, namely, an n-vertex graph whose degree sequence is d ¯, and if so, to construct one such realization. The problem was well researched over the recent decades and plays an important role in the field of Social Networks. In this paper, we consider the following natural generalization of the problem: Let G = ( V, E ) be a simple undirected graph on V = { 1, 2, …, n }. Let f ¯ ∈ R + n be a vector of requirements of the vertices, and let w ¯ ∈ R + n be a vector of provided services at the vertices. The provided services vector w ¯ satisfies the requirements vector f ¯ on G if the constraints ∑ j ∈ Γ ( i ) w j = f i are satisfied for all i ∈ V, where Γ ( i ) denotes the neighborhood of i. We study the following weighted graph realization problem. Given a requirements vector f ¯, the goal is to find a suitable graph G and a vector w ¯ of provided services that satisfy f ¯ on G. In the original degree realization problem, all the provided services must be equal to one. For even n, we show that every requirement vector is realizable. For odd n, the picture is more complicated, as certain requirement vectors are non-realizable. We provide a complete characterization for n = 3 and n = 5, and give (non-matching but close) necessary and sufficient conditions for realizability for odd n ≥ 7. We provide a complete characterization for the variant in which the constraints that should be satisfied are: max j ∈ Γ ( i ) ⁡ w j = f i, for all i ∈ V. As before, we show that every requirement vector can be realized if n is even. For odd n, we show that a vector is realizable if and only if not all requirements are distinct.

TCS Journal 2016 Journal Article

Changing of the guards: Strip cover with duty cycling

• Amotz Bar-Noy
• Ben Baumer
• Dror Rawitz

The notion of duty cycling is common in problems which seek to maximize the lifetime of a wireless sensor network. In the duty cycling model, sensors are grouped into shifts that take turns covering the region in question, and each sensor can belong to at most one shift. We consider the imposition of the duty cycling model upon the Strip Cover problem, where we are given n sensors on a one-dimensional region, and each shift can contain at most k ≤ n sensors. We call the problem of finding the optimal set of shifts so as to maximize the length of time that the entire region can be covered by a wireless sensor network, k-Duty Cycle Strip Cover (k-DutySC). In this paper, we present a polynomial-time algorithm for 2-DutySC. Furthermore, we show that this algorithm is a 35 24 -approximation algorithm for k-DutySC. We also give two lower bounds on the performance of our algorithm: 15 11, for k ≥ 4, and 6 5, for k = 3, and provide experimental evidence suggesting that these lower bounds are tight. Finally, we propose a fault tolerance model and find thresholds on the sensor failure rate over which our algorithm has the highest expected performance.

TCS Journal 2014 Journal Article

Competitive router scheduling with structured data

• Yishay Mansour
• Boaz Patt-Shamir
• Dror Rawitz

We consider the task of transmitting structured information over bounded-capacity links. Our information model is a stream of basic units called superpackets that are broken into k packets each. To model the possible structure and redundancy of the superpackets, we assume that for each superpacket there is a collection of minimal subsets of packets whose delivery makes the superpacket useful. This very general model encompasses, for example, MPEG streams, where one can think of a group of pictures (GoP) as a superpacket. The fundamental difficulty is that networks can forward only the primitive packets, but applications can use only superpackets, and thus if no minimal subset is delivered, the whole superpacket becomes useless. Our aim is to maximize goodput (number of useful superpackets) in the face of overloaded communication links, where we are forced to drop some packets. Specifically, we assume that an arbitrary stream of packets arrives at a router with multiple bounded-capacity outgoing links. An online algorithm needs to decide, for each superpacket, which outgoing link to use (all packets of the same superpacket must use the same link) and, in case of an overload at a link, which packets to drop and which to transmit so as to maximize goodput. We analyze a simple randomized competitive algorithm for the general case and provide a nearly matching lower bound on the competitive ratio of any randomized online algorithm.

TCS Journal 2011 Journal Article

Video distribution under multiple constraints

• Boaz Patt-Shamir
• Dror Rawitz

We consider the optimization problem of providing a set of video streams to a set of clients, where each stream has costs in m possible measures (such as communication bandwidth, processing bandwidth, etc.), and each client has its own utility function for each stream. We assume that the server has a budget cap on each of the m cost measures; each client has an upper bound on the utility that can be derived from it, and potentially also upper bounds in each of the m cost measures. The task is to choose which streams the server will provide, and out of this set, which streams each client will receive. The goal is to maximize the overall utility subject to the budget constraints. We give an efficient approximation algorithm with approximation factor of O ( m ) with respect to the optimal possible utility for any input, assuming that clients have only a bound on their maximal utility. If, in addition, each client has at most m c capacity constraints, then the approximation factor increases by another factor of O ( m c log n ), where n is the input length. We also consider the special case of “small” streams, namely where each stream has cost of at most O ( 1 / log n ) fraction of the budget cap, in each measure. For this case we present an algorithm whose approximation ratio is O ( log n ).

TCS Journal 2008 Journal Article

Approximating the 2-interval pattern problem

• Maxime Crochemore
• Danny Hermelin
• Gad M. Landau
• Dror Rawitz
• Stéphane Vialette

We address the issue of approximating the 2-Interval Pattern problem over its various models and restrictions. This problem, motivated by RNA secondary structure prediction, asks to find a maximum cardinality subset of a 2-interval set with respect to some prespecified geometric constraints. We present several constant factor approximation algorithms whose performance guarantee depends on the different possible restrictions imposed on the input 2-interval set. In addition, we show that our results extend to the weighted variant of the problem.

SODA Conference 2007 Conference Paper

Optimization problems in multiple-interval graphs

• Ayelet Butman
• Danny Hermelin
• Moshe Lewenstein
• Dror Rawitz