R Sandeep

Satyabrata Jana, Shivesh K. Roy, R. B. Sandeep

Vertex splitting replaces a vertex (v) by two nonadjacent vertices whose neighborhoods together equal (N(v)). A split is \emph{exclusive} if these neighborhoods are disjoint and \emph{shallow} if no newly created vertex is split again. For a graph property (Π), \textsc{(Π)-Vertex Splitting} asks whether at most (k) splits can transform a graph (G) into one satisfying (Π). We continue the systematic study of this operation and settle several open problems. First, we prove that \textsc{Cograph Vertex Splitting} is \textsf{NP}-complete, even on graphs of girth at least 5, resolving a question of Firbas and Sorge (ISAAC 2024). More generally, \textsc{(P_t)-free Vertex Splitting} is \textsf{NP}-complete for every fixed (t\geq 4). We also prove that \textsc{Chordal Vertex Splitting} and \textsc{Unit-Interval Vertex Splitting} are \textsf{NP}-complete, resolving two questions of Abu-Khzam, Chakraborty, Isenmann, and Oijid (IWOCA 2026). Our hardness results extend to the exclusive and shallow variants. Assuming the Exponential Time Hypothesis, none of these problems admits an algorithm running in (2^{o(k)}n^{O(1)}) time; moreover, except for the unit-interval cases, none admits an algorithm running in (2^{o(n)}) time.

Arpan Sadhukhan, R. B. Sandeep, Sagnik Sen

We prove Seymour's second neighborhood conjecture on oriented graphs whose minimum out-degree is equal to $7$. This gives, to our knowledge, the first improvement of the minimum out-degree threshold in two decades, since the work of Kaneko and Locke in 2001, who resolved the conjecture for oriented graphs whose minimum out-degree is at most $6$. The proof is partially computer-assisted: after a sequence of local reductions, the remaining finite obstruction models are eliminated by reproducible OR-Tools CP-SAT infeasibility checks.

Sreekanth Vempati, Korah T Malayil, Sruthi V et al.

Homepage is the first touch point in the customer's journey and is one of the prominent channels of revenue for many e-commerce companies. A user's attention is mostly captured by homepage banner images (also called Ads/Creatives). The set of banners shown and their design, influence the customer's interest and plays a key role in optimizing the click through rates of the banners. Presently, massive and repetitive effort is put in, to manually create aesthetically pleasing banner images. Due to the large amount of time and effort involved in this process, only a small set of banners are made live at any point. This reduces the number of banners created as well as the degree of personalization that can be achieved. This paper thus presents a method to generate creatives automatically on a large scale in a short duration. The availability of diverse banners generated helps in improving personalization as they can cater to the taste of larger audience. The focus of our paper is on generating wide variety of homepage banners that can be made as an input for user level personalization engine. Following are the main contributions of this paper: 1) We introduce and explain the need for large scale banner generation for e-commerce 2) We present on how we utilize existing deep learning based detectors which can automatically annotate the required objects/tags from the image. 3) We also propose a Genetic Algorithm based method to generate an optimal banner layout for the given image content, input components and other design constraints. 4) Further, to aid the process of picking the right set of banners, we designed a ranking method and evaluated multiple models. All our experiments have been performed on data from Myntra (http://www.myntra.com), one of the top fashion e-commerce players in India.