A common approach used to efficiently solve problems is to develop sequential greedy algorithms. Such algorithms are easily implemented and provide polynomial-time solutions. A natural next step towards building more efficient algorithms is to develop parallel algorithms. However, sequential greedy algorithms seldom lead to parallel algorithms; computing the output of sequential greedy algorithms is often shown to be P-complete and thus "inherently sequential" under the commonly believed assumption that P ≠ NC, where NC is the class of efficiently parallelizable problems. Greedy edge-induced (resp., vertex-induced) subgraph building algorithms for a property π operate like so. For given graph G, a subgraph of G is built by adding edges (resp., vertices) in a given order unless the inclusion of said edge (resp., vertex) would contradict property π within the subgraph. For vertex-induced greedy subgraph building algorithms, Miyano (1989) provided a comprehensive result: computing the subgraph output by such algorithms is typically P-complete. In contrast, little is known about its edge-induced counterpart. In this work, we analyze the complexity of the Lexicographically First Maximal H-free edge-induced subgraph problem, which is concerned with computing the output of greedy edge-induced subgraph building algorithms where the property π is that the subgraph is H-free. This gives us insight into the largely overlooked edge-induced versions of greedy subgraph building algorithms and into how graph structure influences the complexity of such algorithms. Our primary contribution is a trichotomy theorem for the cases where H is a tree: we show that the problem is either P-complete, CC-complete, or in L, where CC is the class of problems solvable using comparator circuits - or, equivalently, problems reducible to the lexicographically first maximal matching problem. In contrast, the vertex-induced version is either P-complete or in L, and such dichotomy theorems are much more common. Our additional technical contributions include: (1) an iterative approach to hardness proofs by focusing on a set of "smaller" problems and extending hardness via simple constructions, and (2) expanding on the scarce set of problems known to be CC-complete.

Formal methods in computer science aim to increase reliability and robustness of software or hardware designs. Unfortunately, formal methods are typically only accessible to specialized professionals. One of the reasons of this limited accessibility is the lack of exposure to formal methods in undergraduate education, even for computer science majors. We aim to rectify this by developing self-contained, turnkey Jupyter notebooks that will introduce students to SMT solvers, an important tool in formal methods, to solve problems related to their courses. This allows students to explore formal methods while not distracting from their coursework. In this work, we report on four Jupyter notebooks that we developed and deployed for this purpose.

In graph Ramsey theory, the arrowing operator is used to describe the appearance of unavoidable substructures within colored graphs; for graphs G, F, and H, we say G → (F,H) (read, G arrows F, H) if every red/blue coloring of G’s edges contains a red F or a blue H. For fixed F and H, the (F,H)-Arrowing problem asks whether G → (F,H) for some given graph G. (F,H)-Arrowing has been shown to be in P or coNP-complete for different pairs (F,H). However, categorizing the complexity for all pairs still remains wide open. In general, categorizing the complexity of problems whose nature depends on some underlying graph - or, in our case, pair of graphs - is a daunting task, and (F,H)-Arrowing is no exception. Hardness proofs typically rely on ad-hoc, laborious constructions of special graphs known as "gadgets." In this work, we present a simple, computational approach to find these gadgets for small (F,H)-Arrowing problems and show how these can be extended to other (F,H)-Arrowing problems. Our main focus is on the simplest case for which the complexity remains uncategorized: F = P₃. We showcase the efficacy of our computational approach by presenting hardness proofs for (P₃, H)-Arrowing problems previously not known to be coNP-hard. Moreover, we show how to generalize hardness to other (P₃,H)-Arrowing problems by either: (1) carefully inspecting and modifying our found gadgets, or (2) coming up with intuitive constructions to reduce (P₃, H')-Arrowing to (P₃, H)-Arrowing, where H' is a subgraph of H. We also discuss how our methodology can be extended to work for other (F,H)-Arrowing problems by showing new results for F = P₄ and K_{1,3}. We see our work as an important step towards categorizing the complexity of (F,H)-Arrowing for all pairs (F,H). (F,H)-Arrowing is thought to be hard when (F',H')-Arrowing is hard where F' and H' are subgraphs of F and H, respectively. Under this assumption, our results narrow down the only uncategorized family of problems for which the problem may lie in P. Beyond the complexity of (F,H)-Arrowing, we believe that the broader impact of our work is showing how computational methodologies can be adopted for proving hardness, and we hope our approach will be adopted to find gadgets for other open graph problems as well.

Approval-Based Committee (ABC) rules are an important tool for choosing a fair set of candidates when given the preferences of a collection of voters. Though finding a winning committee for many ABC rules is NP-hard, natural variations for these rules with polynomial-time algorithms exist. The recently introduced Method of Equal Shares, an important ABC rule with desirable properties, is also computable in polynomial time. However, when working with very large elections, polynomial time is not enough and parallelization may be necessary. We show that computing a winning committee using these polynomial-time ABC rules (including the Method of Equal Shares) is P-hard, thus showing they cannot be parallelized. In contrast, we show that finding a winning committee can be parallelized when the votes are single-peaked or single-crossing for the important ABC rule Chamberlin-Courant.

Feature extraction is an essential task in graph analytics. These feature vectors, called graph descriptors, are used in downstream vector-space-based graph analysis models. This idea has proved fruitful in the past, with spectral-based graph descriptors providing state-of-the-art classification accuracy. However, known algorithms to compute meaningful descriptors do not scale to large graphs since: (1) they require storing the entire graph in memory, and (2) the end-user has no control over the algorithm’s runtime. In this article, we present streaming algorithms to approximately compute three different graph descriptors capturing the essential structure of graphs. Operating on edge streams allows us to avoid storing the entire graph in memory, and controlling the sample size enables us to keep the runtime of our algorithms within desired bounds. We demonstrate the efficacy of the proposed descriptors by analyzing the approximation error and classification accuracy. Our scalable algorithms compute descriptors of graphs with millions of edges within minutes. Moreover, these descriptors yield predictive accuracy comparable to the state-of-the-art methods but can be computed using only 25% as much memory.