Author name cluster

Toni Böhnlein

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

2 author rows

TCS Journal 2026 Journal Article

Minimum Surgical Probing with convexity constraints

Toni Böhnlein
Niccolò Di Marco
Andrea Frosini

We consider a tomographic problem on graphs, called Minimum Surgical Probing, introduced by Bar-Noy et al. [4]. Each vertex v ∈ V of a graph G = ( V, E ) is associated with an (unknown) label ℓ v. The outcome of probing a vertex v is P v = ∑ u ∈ N [ v ] ℓ u, where N[v] denotes the closed neighborhood of v. The goal is to uncover the labels given probes P v for all v ∈ V. For some graphs, the labels cannot be determined (uniquely), and the use of surgical probes is permitted but must be minimized. A surgical probe at vertex v returns ℓ v. In this paper, we introduce convexity constraints to Minimum Surgical Probing. For binary labels, convexity imposes constraints such as if ℓ u = ℓ v = 1, then for all vertices w on a shortest path between u and v, we must have that ℓ w = 1. We show that convexity constraints reduce the number of required surgical probes for several graph families. Specifically, they allow us to recover the labels without using surgical probes for trees and bipartite graphs where otherwise ⌊|V|/2⌋ surgical probes might be needed. Our analysis is based on restricting the size of cliques in a graph using the concept of Kh -free graphs (forbidden induced subgraphs). Utilizing this approach, we analyze grid graphs, the King’s graph, and (maximal-) outerplanar graphs.

Details DOI

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.

Details DOI

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.

Details

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.

Details

TCS Journal 2023 Journal Article

Stackelberg packing games

Toni Böhnlein
Oliver Schaudt
Joachim Schauer

Stackelberg pricing games are pricing problems over a set of items. One player, the leader, sets prices for the items and the second player, the follower, buys a subset of items at minimal total cost subject to feasibility constraints. The constraints are determined by an optimization problem. For example, the Stackelberg shortest path game is used to optimize the income from road tolls (cf. [21]). The items are edges in a network graph and the follower buys a subset of edges forming a path. The Stackelberg pricing games studied in the literature are formulated on top of covering problems. In this paper, we introduce pricing games based on packing problems. We are interested in the complexity of computing leader-optimal prices depending on different types of follower-constraints. We show that optimal prices can be computed in polynomial time if the follower-constraints are determined by the well-known interval scheduling problem. This problem is equivalent to the independent set problem on interval graphs. In case the follower-constraints are based on the independent set problem on perfect graphs or on the bipartite matching problem, we prove APX-hardness for the pricing problem. On a more general note, we prove Σ 2 p -completeness if the follower-constraints are given by a packing problem that is NP-complete, i. e. , the leader's pricing problem is hard even if she has an NP-oracle at hand.

Details DOI

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.

Details

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.

Details DOI

ECAI Conference 2016 Conference Paper

Minisum and Minimax Committee Election Rules for General Preference Types

Dorothea Baumeister
Toni Böhnlein
Lisa Rey
Oliver Schaudt
Ann-Kathrin Selker

In committee elections it is often assumed that voters only (dis)approve of each candidate or that they rank all candidates, as it is common for single-winner elections. We suggest an intermediate approach, where the voters rank the candidates into a fixed number of groups. This allows more diverse votes than approval votes, but leaves more freedom than in a linear order. A committee is then elected by applying the minisum or minimax approach to minimize the voters' dissatisfaction. We study the axiomatic properties of these committee election rules as well as the complexity of winner determination and show fixed-parameter tractability for our minimax rules.

Details