Document

**Published in:** LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

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.

Amotz Bar-Noy, David Peleg, Mor Perry, and Dror Rawitz. Graph Realization of Distance Sets. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.MFCS.2022.13, author = {Bar-Noy, Amotz and Peleg, David and Perry, Mor and Rawitz, Dror}, title = {{Graph Realization of Distance Sets}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {13:1--13:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.13}, URN = {urn:nbn:de:0030-drops-168119}, doi = {10.4230/LIPIcs.MFCS.2022.13}, annote = {Keywords: Graph Realization, distance realization, network design} }

Document

**Published in:** LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

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.

Amotz Bar-Noy, Toni Böhnlein, David Peleg, and Dror Rawitz. On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.MFCS.2022.14, author = {Bar-Noy, Amotz and B\"{o}hnlein, Toni and Peleg, David and Rawitz, Dror}, title = {{On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {14:1--14:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.14}, URN = {urn:nbn:de:0030-drops-168121}, doi = {10.4230/LIPIcs.MFCS.2022.14}, annote = {Keywords: Graph Realization, Bipartite Graphs, Degree Sequences, Graphic Sequences, Bigraphic Sequences, Approximate Realization, Multigraph Realization} }

Document

Invited Paper

**Published in:** LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

This paper addresses the classical problem of characterizing degree sequences that can be realized by a bipartite graph. For the simpler variant of the problem, where a partition of the sequence into the two sides of the bipartite graph is given as part of the input, a complete characterization was given by Gale and Ryser over 60 years ago. However, the general question, in which both the partition and the realizing graph need to be determined, is still open. This paper provides an overview of some of the known results on this problem in interesting special cases, including realizations by bipartite graphs and bipartite multigraphs.

Amotz Bar-Noy, Toni Böhnlein, David Peleg, and Dror Rawitz. On Realizing a Single Degree Sequence by a Bipartite Graph (Invited Paper). In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.SWAT.2022.1, author = {Bar-Noy, Amotz and B\"{o}hnlein, Toni and Peleg, David and Rawitz, Dror}, title = {{On Realizing a Single Degree Sequence by a Bipartite Graph}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {1:1--1:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.1}, URN = {urn:nbn:de:0030-drops-161618}, doi = {10.4230/LIPIcs.SWAT.2022.1}, annote = {Keywords: Degree Sequences, Graph Realization, Bipartite Graphs, Graphic Sequences, Bigraphic Sequences, Multigraph Realization} }

Document

**Published in:** LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

The classical degree realization problem is defined as follows: Given a sequence d̄ = (d_1,…,d_n) of positive integers, construct an n-vertex graph in which each vertex u_i has degree d_i (or decide that no such graph exists). In this article, we present and study the related selected neighbor degree realization problem, which requires that each vertex u_i of G has a neighbor of degree d_i. We solve the problem when G is required to be acyclic (i.e., a forest), and present a sufficient and necessary condition for a given sequence to be realizable.

Amotz Bar-Noy, David Peleg, Dror Rawitz, and Elad Yehezkel. Selected Neighbor Degree Forest Realization. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.ISAAC.2021.27, author = {Bar-Noy, Amotz and Peleg, David and Rawitz, Dror and Yehezkel, Elad}, title = {{Selected Neighbor Degree Forest Realization}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {27:1--27:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.27}, URN = {urn:nbn:de:0030-drops-154609}, doi = {10.4230/LIPIcs.ISAAC.2021.27}, annote = {Keywords: network realization, graph algorithms, lower bound} }

Document

**Published in:** LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

We study a graph realization problem that pertains to degrees in vertex neighborhoods. The classical problem of degree sequence realizability asks whether or not a given sequence of n positive integers is equal to the degree sequence of some n-vertex undirected simple graph. While the realizability problem of degree sequences has been well studied for different classes of graphs, there has been relatively little work concerning the realizability of other types of information profiles, such as the vertex neighborhood profiles.
In this paper we introduce and explore the minimum degrees in vertex neighborhood profile as it is one of the most natural extensions of the classical degree profile to vertex neighboring degree profiles. Given a graph G = (V,E), the min-degree of a vertex v ∈ V, namely MinND(v), is given by min{deg(w) ∣ w ∈ N[v]}. Our input is a sequence σ = (d_𝓁^{n_𝓁}, ⋯ , d₁^{n₁}), where d_{i+1} > d_i and each n_i is a positive integer. We provide some necessary and sufficient conditions for σ to be realizable. Furthermore, under the restriction that the realization is acyclic, i.e., a tree or a forest, we provide a full characterization of realizable sequences, along with a corresponding constructive algorithm.
We believe our results are a crucial step towards understanding extremal neighborhood degree relations in graphs.

Amotz Bar-Noy, Keerti Choudhary, Avi Cohen, David Peleg, and Dror Rawitz. Minimum Neighboring Degree Realization in Graphs and Trees. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.ESA.2020.10, author = {Bar-Noy, Amotz and Choudhary, Keerti and Cohen, Avi and Peleg, David and Rawitz, Dror}, title = {{Minimum Neighboring Degree Realization in Graphs and Trees}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {10:1--10:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.10}, URN = {urn:nbn:de:0030-drops-128765}, doi = {10.4230/LIPIcs.ESA.2020.10}, annote = {Keywords: Graph realization, neighborhood profile, graph algorithms, degree sequences} }

Document

**Published in:** LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

The classical problem of degree sequence realizability asks whether or not a given sequence of n positive integers is equal to the degree sequence of some n-vertex undirected simple graph. While the realizability problem of degree sequences has been well studied for different classes of graphs, there has been relatively little work concerning the realizability of other types of information profiles, such as the vertex neighborhood profiles.
In this paper, we initiate the study of neighborhood degree profiles, wherein, our focus is on the natural problem of realizing maximum neighborhood degrees. More specifically, we ask the following question: "Given a sequence D of n non-negative integers 0≤ d₁≤ ⋯ ≤ d_n, does there exist a simple graph with vertices v₁,…, v_n such that for every 1≤ i ≤ n, the maximum degree in the neighborhood of v_i is exactly d_i?"
We provide in this work various results for maximum-neighborhood-degree for general n vertex graphs. Our results are first of its kind that studies extremal neighborhood degree profiles. For closed as well as open neighborhood degree profiles, we provide a complete realizability criteria. We also provide tight bounds for the number of maximum neighbouring degree profiles of length n that are realizable. Our conditions are verifiable in linear time and our realizations can be constructed in polynomial time.

Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Graph Realizations: Maximum Degree in Vertex Neighborhoods. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.SWAT.2020.10, author = {Bar-Noy, Amotz and Choudhary, Keerti and Peleg, David and Rawitz, Dror}, title = {{Graph Realizations: Maximum Degree in Vertex Neighborhoods}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {10:1--10:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-150-4}, ISSN = {1868-8969}, year = {2020}, volume = {162}, editor = {Albers, Susanne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.10}, URN = {urn:nbn:de:0030-drops-122572}, doi = {10.4230/LIPIcs.SWAT.2020.10}, annote = {Keywords: Graph realization, neighborhood profile, extremum-degree} }

Document

**Published in:** LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

This paper presents and studies a generalization of the microscopic image reconstruction problem (MIR) introduced by Frosini and Nivat [Andrea Frosini and Maurice Nivat, 2007; Nivat, 2002]. Consider a specimen for inspection, represented as a collection of points typically organized on a grid in the plane. Assume each point x has an associated physical value l_x, which we would like to determine. However, it might be that obtaining these values precisely (by a surgical probe) is difficult, risky, or impossible. The alternative is to employ aggregate measuring techniques (such as EM, CT, US or MRI), whereby each measurement is taken over a larger window, and the exact values at each point are subsequently extracted by computational methods.
In this paper we extend the MIR framework in a number of ways. First, we consider a generalized setting where the inspected object is represented by an arbitrary graph G, and the vector l in R^n assigns a value l_v to each node v. A probe centered at a vertex v will capture a window encompassing its entire neighborhood N[v], i.e., the outcome of a probe centered at v is P_v = sum_{w in N[v]} l_w. We give a criterion for the graphs for which the extended MIR problem can be solved by extracting the vector l from the collection of probes, P^- = {P_v | v in V}.
We then consider cases where such reconstruction is impossible (namely, graphs G for which the probe vector P is inconclusive, in the sense that there may be more than one vector l yielding P). Let us assume that surgical probes (whose outcome at vertex v is the exact value of l_v) are technically available to us (yet are expensive or risky, and must be used sparingly). We show that in such cases, it may still be possible to achieve reconstruction based on a combination of a collection of standard probes together with a suitable set of surgical probes. We aim at identifying the minimum number of surgical probes necessary for a unique reconstruction, depending on the graph topology. This is referred to as the Minimum Surgical Probing problem (MSP).
Besides providing a solution for the above problems for arbitrary graphs, we also explore the range of possible behaviors of the Minimum Surgical Probing problem by determining the number of surgical probes necessary in certain specific graph families, such as perfect k-ary trees, paths, cycles, grids, tori and tubes.

Amotz Bar-Noy, Toni Böhnlein, Zvi Lotker, David Peleg, and Dror Rawitz. The Generalized Microscopic Image Reconstruction Problem. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.ISAAC.2019.42, author = {Bar-Noy, Amotz and B\"{o}hnlein, Toni and Lotker, Zvi and Peleg, David and Rawitz, Dror}, title = {{The Generalized Microscopic Image Reconstruction Problem}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {42:1--42:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.42}, URN = {urn:nbn:de:0030-drops-115382}, doi = {10.4230/LIPIcs.ISAAC.2019.42}, annote = {Keywords: Discrete mathematics, Combinatorics, Reconstruction algorithm, Image reconstruction, Graph spectra, Grid graphs} }

Document

**Published in:** LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

We consider the problem of realizable interval-sequences. An interval sequence comprises of n integer intervals [a_i,b_i] such that 0 <= a_i <= b_i <= n-1, and is said to be graphic/realizable if there exists a graph with degree sequence, say, D=(d_1,...,d_n) satisfying the condition a_i <= d_i <= b_i, for each i in [1,n]. There is a characterisation (also implying an O(n) verifying algorithm) known for realizability of interval-sequences, which is a generalization of the Erdös-Gallai characterisation for graphic sequences. However, given any realizable interval-sequence, there is no known algorithm for computing a corresponding graphic certificate in o(n^2) time.
In this paper, we provide an O(n log n) time algorithm for computing a graphic sequence for any realizable interval sequence. In addition, when the interval sequence is non-realizable, we show how to find a graphic sequence having minimum deviation with respect to the given interval sequence, in the same time. Finally, we consider variants of the problem such as computing the most regular graphic sequence, and computing a minimum extension of a length p non-graphic sequence to a graphic one.

Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Efficiently Realizing Interval Sequences. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.ISAAC.2019.47, author = {Bar-Noy, Amotz and Choudhary, Keerti and Peleg, David and Rawitz, Dror}, title = {{Efficiently Realizing Interval Sequences}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {47:1--47:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.47}, URN = {urn:nbn:de:0030-drops-115430}, doi = {10.4230/LIPIcs.ISAAC.2019.47}, annote = {Keywords: Graph realization, graphic sequence, interval sequence} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail