Flavia Bonomo

Flavia Bonomo-Braberman, Min Chih Lin, Ignacio Maqueda

A graph is a $(k,\ell)$-graph if its vertex set can be partitioned into $k$ independent sets and $\ell$ cliques. This family simultaneously generalizes split, bipartite, and co-bipartite graphs. While the recognition problem is NP-complete whenever $k\geq 3$ or $\ell\geq 3$, the remaining small cases are polynomial-time solvable. In this paper we revisit the known recognition algorithms for the first nontrivial polynomial cases, namely $(2,1)$-, $(1,2)$-, and $(2,2)$-graphs, and show how to remove specific bottlenecks in their existing recognition procedures. For $(2,1)$-graphs, we show that the extra quadratic enumeration in the algorithm of Brandstädt, Le and Szymczak can be avoided by exploiting the structure of a shortest odd cycle in the relevant residual graph, reducing the running time from $O((n+m)^2)$ to $O(n(n+m))$. By complementation, this yields an $O(n(n+\overline m))$-time recognition algorithm for $(1,2)$-graphs, where $\overline m$ denotes the number of edges of the complement graph. For $(2,2)$-graphs, we refine the sparse-dense partition framework of Feder, Hell, Klein and Motwani by restricting the local-search enumeration to sets that are simultaneously bipartite and co-bipartite, and by using the improved algorithms for $(2,1)$- and $(1,2)$-graphs as preprocessing tools. This gives an $O(n^4(n+\min\{m,\overline m\})^3)$-time recognition algorithm for $(2,2)$-graphs.

Víctor A. Braberman, Flavia Bonomo-Braberman, Yiannis Charalambous et al.

The emergence of prompting as the dominant paradigm for leveraging Large Language Models (LLMs) has led to a proliferation of LLM-native software, where application behavior arises from complex, stochastic data transformations. However, the engineering of such systems remains largely exploratory and ad-hoc, hampered by the absence of conceptual frameworks, ex-ante methodologies, design guidelines, and specialized benchmarks. We argue that a foundational step towards a more disciplined engineering practice is a systematic understanding of the core functional units--generative transformations--and their compositional patterns within LLM-native applications. Focusing on the rich domain of software verification and falsification, we conduct a secondary study of over 100 research proposals to address this gap. We first present a fine-grained taxonomy of generative transformations, abstracting prompt-based interactions into conceptual signatures. This taxonomy serves as a scaffolding to identify recurrent transformation relationship patterns--analogous to software design patterns--that characterize solution approaches in the literature. Our analysis not only validates the utility of the taxonomy but also surfaces strategic gaps and cross-dimensional relationships, offering a structured foundation for future research in modular and compositional LLM application design, benchmarking, and the development of reliable LLM-native systems.