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 K h -free graphs (forbidden induced subgraphs). Utilizing this approach, we analyze grid graphs , the King’s graph , and (maximal-) outerplanar graphs .

We study the problem of scheduling a general computational DAG on multiple processors in a 2-level memory hierarchy. This setting is a natural generalization of several prominent models in the literature, and it simultaneously captures workload balancing, communication, and data movement due to cache size limitations. We first analyze the fundamental properties of this problem from a theoretical perspective, such as its computational complexity. We also prove that optimizing parallelization and memory management separately, as done in many applications, can result in a solution that is a linear factor away from the optimum.

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 there is a complete characterization that was established more than 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, analyzing 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.

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 .

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.

The well-studied red-blue pebble game models the execution of an arbitrary computational DAG by a single processor over a two-level memory hierarchy. We present a natural generalization to a multiprocessor setting where each processor has its own limited fast memory, and all processors share unlimited slow memory. To our knowledge, this is the first thorough study that combines pebbling and DAG scheduling problems, capturing the computation of general workloads on multiple processors with memory constraints and communication costs. Our pebbling model enables us to analyze trade-offs between workload balancing, communication and memory limitations, and it captures real-world factors such as superlinear speedups due to parallelization. Our results include upper and lower bounds on the pebbling cost, an analysis of a greedy pebbling strategy, and an extension of NP-hardness results for specific DAG classes from simpler models. For our main technical contribution, we show two inapproximability results that already hold for the long-standing problem of standard red-blue pebbling: (i) the optimal I/O cost cannot be approximated to any finite factor, and (ii) the optimal total cost (I/O+computation) can only be approximated to a limited constant factor, i.e., it does not allow for a polynomial-time approximation scheme. These results also carry over naturally to our multiprocessor pebbling model.

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.

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.

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.