Search Results

Documents authored by Böhnlein, Toni

Document
Invited Paper
DOI: 10.4230/LIPIcs.MFCS.2024.1
On Key Parameters Affecting the Realizability of Degree Sequences (Invited Paper)

Authors: Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, and Dror Rawitz

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
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.
Cite as

Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, and Dror Rawitz. On Key Parameters Affecting the Realizability of Degree Sequences (Invited Paper). In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.MFCS.2024.1,
  author =	{Bar-Noy, Amotz and B\"{o}hnlein, Toni and Peleg, David and Ran, Yingli and Rawitz, Dror},
  title =	{{On Key Parameters Affecting the Realizability of Degree Sequences}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{1:1--1:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.1},
  URN =		{urn:nbn:de:0030-drops-205573},
  doi =		{10.4230/LIPIcs.MFCS.2024.1},
  annote =	{Keywords: Degree Sequences, Graph Algorithms, Graph Realization, Outer-planar Graphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.18
Sparse Graphic Degree Sequences Have Planar Realizations

Authors: Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, and Dror Rawitz

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
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.
Cite as

Amotz Bar-Noy, Toni Böhnlein, David Peleg, Yingli Ran, and Dror Rawitz. Sparse Graphic Degree Sequences Have Planar Realizations. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.MFCS.2024.18,
  author =	{Bar-Noy, Amotz and B\"{o}hnlein, Toni and Peleg, David and Ran, Yingli and Rawitz, Dror},
  title =	{{Sparse Graphic Degree Sequences Have Planar Realizations}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.18},
  URN =		{urn:nbn:de:0030-drops-205745},
  doi =		{10.4230/LIPIcs.MFCS.2024.18},
  annote =	{Keywords: Degree Sequences, Graph Algorithms, Graph Realization, Planar Graphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.14
On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph

Authors: Amotz Bar-Noy, Toni Böhnlein, David Peleg, and Dror Rawitz

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.SWAT.2022.1
On Realizing a Single Degree Sequence by a Bipartite Graph (Invited Paper)

Authors: Amotz Bar-Noy, Toni Böhnlein, David Peleg, and Dror Rawitz

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.ISAAC.2019.42
The Generalized Microscopic Image Reconstruction Problem

Authors: Amotz Bar-Noy, Toni Böhnlein, Zvi Lotker, David Peleg, and Dror Rawitz

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.ICALP.2017.46
Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting

Authors: Toni Böhnlein, Stefan Kratsch, and Oliver Schaudt

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
In a Stackelberg Pricing Game a distinguished player, the leader, chooses prices for a set of items, and the other players, the followers, each seeks to buy a minimum cost feasible subset of the items. The goal of the leader is to maximize her revenue, which is determined by the sold items and their prices. Most previously studied cases of such games can be captured by a combinatorial model where we have a base set of items, some with fixed prices, some priceable, and constraints on the subsets that are feasible for each follower. In this combinatorial setting, Briest et al. and Balcan et al. independently showed that the maximum revenue can be approximated to a factor of H_k ~ log(k), where k is the number of priceable items. Our results are twofold. First, we strongly generalize the model by letting the follower minimize any continuous function plus a linear term over any compact subset of R_(n>=0); the coefficients (or prices) in the linear term are chosen by the leader and determine her revenue. In particular, this includes the fundamental case of linear programs. We give a tight lower bound on the revenue of the leader, generalizing the results of Briest et al. and Balcan et al. Besides, we prove that it is strongly NP-hard to decide whether the optimum revenue exceeds the lower bound by an arbitrarily small factor. Second, we study the parameterized complexity of computing the optimal revenue with respect to the number k of priceable items. In the combinatorial setting, given an efficient algorithm for optimal follower solutions, the maximum revenue can be found by enumerating the 2^k subsets of priceable items and computing optimal prices via a result of Briest et al., giving time O(2^k|I|^c ) where |I| is the input size. Our main result here is a W[1]-hardness proof for the case where the followers minimize a linear program, ruling out running time f(k)|I|^c unless FPT = W[1] and ruling out time |I|^o(k) under the Exponential-Time Hypothesis.
Cite as

Toni Böhnlein, Stefan Kratsch, and Oliver Schaudt. Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bohnlein_et_al:LIPIcs.ICALP.2017.46,
  author =	{B\"{o}hnlein, Toni and Kratsch, Stefan and Schaudt, Oliver},
  title =	{{Revenue Maximization in Stackelberg Pricing Games: Beyond the Combinatorial Setting}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{46:1--46:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.46},
  URN =		{urn:nbn:de:0030-drops-73771},
  doi =		{10.4230/LIPIcs.ICALP.2017.46},
  annote =	{Keywords: Algorithmic pricing, Stackelberg games, Approximation algorithms, Rev- enue maximization, Parameterized complexity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact