In the Graph Reconstruction (GR) problem, a player initially only knows the vertex set V of an input graph G = (V, E) and is required to learn its set of edges E. To this end, the player submits queries to an oracle and must deduce E from the oracle’s answers. Angluin and Chen [Journal of Computer and System Sciences, 2008] resolved the number of Independent Set (IS) queries necessary and sufficient for GR on m-edge graphs. In this setting, each query consists of a subset of vertices U ⊆ V, and the oracle responds with a boolean, indicating whether U is an independent set in G. They gave algorithms that use O(m ⋅ log n) IS queries, which is best possible. In this paper, we initiate the study of GR via Maximal Independent Set (MIS) queries, a more powerful variant of IS queries. Given a query U ⊆ V, the oracle responds with any, potentially adversarially chosen, maximal independent set I ⊆ U in the induced subgraph G[U]. We show that, for GR, MIS queries are strictly more powerful than IS queries when parametrized by the maximum degree Δ of the input graph. We give tight (up to poly-logarithmic factors) upper and lower bounds for this problem: 1) We observe that the simple strategy of taking uniform independent random samples of V and submitting those to the oracle yields a non-adaptive randomized algorithm that executes O(Δ² ⋅ log n) queries and succeeds with high probability. This should be contrasted with the fact that Ω(Δ ⋅ n ⋅ log(n/Δ)) IS queries are required for such graphs, which shows that MIS queries are strictly more powerful than IS queries. Interestingly, combining the strategy of taking uniform random samples of V with the probabilistic method, we show the existence of a deterministic non-adaptive algorithm that executes O(Δ³ ⋅ log(n/Δ)) queries. 2) Regarding lower bounds, we prove that the additional Δ factor when going from randomized non-adaptive algorithms to deterministic non-adaptive algorithms is necessary. We show that every non-adaptive deterministic algorithm requires Ω(Δ³ / log² Δ) queries. For arbitrary randomized adaptive algorithms, we show that Ω(Δ²) queries are necessary in graphs of maximum degree Δ, and that Ω(log n) queries are necessary, even when the input graph is an n-vertex cycle.

We analyse the effectiveness of edge detection algorithms for the purpose of automatically extracting coastlines from satellite images. Four algorithms - Canny, Sobel, Scharr and Prewitt are compared visually and using metrics. With an average SSIM of 0.8, Canny detected edges that were closest to the reference edges. However, the algorithm had difficulty distinguishing noisy edges, e.g. due to development, from coastline edges. In addition, histogram equalization and Gaussian blur were shown to improve the effectiveness of the edge detection algorithms by up to 1.5 and 1.6 times respectively.

Reducing industrial greenhouse gas (GHG) emissions has become imperative for mitigating the adverse effects of climate change. Accurate measurement and monitoring of industrial smoke plumes, which are a significant source of GHG emissions, are crucial for effective emission control strategies. This paper addresses the prospect of utilizing satellite images to measure industrial smoke plumes and explores the effectiveness of various computer vision (CV) technologies in this context. The study focuses on examining both modern deep learning and traditional machine learning models for detecting and segmenting industrial smoke plumes in satellite images. While deep learning models have shown remarkable performance in various CV tasks, their ability to accurately segment smoke plumes in satellite images remains limited, with an average intersection over union (IOU) of no more than 60%. However, certain deep learning models, such as U-Net and AttU-Net, exhibit promising capabilities in identifying challenging types of noise, including clouds, white building surfaces, and snow, which traditional machine learning models struggle with. Employing deep learning models for industrial smoke plume detection proves advantageous, as all models achieve an approximate detection accuracy and F1-Score of 90%. The findings from this research serve as a valuable foundation for further advancements in developing advanced deep learning models specifically tailored to handle the identified types of noise.