Eshwar Srinivasan

Eshwar Srinivasan, Ramesh Hariharasubramanian

In this work, we investigate the algorithmic aspects of two natural extensions of hereditary classes: the edge-apex class and the edge-add class, recently introduced by Singh and Sivaraman. These are defined as the graph classes obtained by at most one edge deletion or one non-edge addition, respectively, from a hereditary class $\mathcal{G}$. Building on earlier results showing that both classes remain hereditary and admit finite forbidden induced subgraph characterizations whenever $\mathcal{G}$ does, we focus on the Weighted Maximum Clique Problem (WMCP) and the Weighted Maximum Independent Set Problem (WMISP). We first present algorithms for WMCP and WMISP on both the edge-apex and edge-add classes of hereditary graph classes. Extending this framework, we introduce the notion of the $\mathcal{G}$-edge distance of a graph $G$, denoted by $ξ_{\mathcal{G}}(G)$, which quantifies how far $G$ is from the class $\mathcal{G}$ in terms of the minimum number of edge deletions or non-edge additions needed to transform it into a member of $\mathcal{G}$. By parameterizing with respect to this distance, we show that both WMCP and WMISP can be solved in $O^*(2^k)$ time on graphs whose $\mathcal{G}$-edge distance is $k$, provided these problems admit polynomial-time algorithms within the class $\mathcal{G}$. This result extends earlier algorithmic characterizations of the single edge-apex and edge-add classes to the more general setting of $k$-edge-distant graphs. By combining our general results with known properties of transitive graphs, we show that WMCP and WMISP can be solved in $O^*(2^k)$ time for graphs with transitive-edge distance $k$.

Eshwar Srinivasan, Ramesh Hariharasubramanian

A graph $G$ with vertex set $V(G)$ and edge set $E(G)$ is said to be word-representable if there exists a word $w$ over the alphabet $V(G)$ such that, for any two distinct letters $x,y \in V(G)$, the letters $x$ and $y$ alternate in $w$ if and only if $(x,y) \in E(G)$. Equivalently, a graph is word-representable if and only if it admits a semi-transitive orientation, that is, an acyclic orientation in which, for every directed path $v_0 \rightarrow v_1 \rightarrow \cdots \rightarrow v_m$ with $m \ge 2$, either there is no arc between $v_0$ and $v_m$, or, for all $1 \le i < j \le m$, there exists an arc from $v_i$ to $v_j$. In this work, we provide a comprehensive structural and algorithmic characterization of word-representable co-bipartite graphs, a class of graphs whose vertex set can be partitioned into two cliques. This work unifies graph-theoretic and matrix-theoretic perspectives. We first establish that a co-bipartite graph is a circle graph if and only if it is a permutation graph, thereby deriving a minimal forbidden induced subgraph characterization for co-bipartite circle graphs. The central contribution then connects semi-transitivity with the circularly compatible ones property of binary matrices. In addition to the structural characterization, the paper introduces a linear-time recognition algorithm for semi-transitive co-bipartite graphs, utilizing Safe's matrix recognition framework.