Bhyravarapu, Sriram; Jana, Satyabrata; Panolan, Fahad; Saurabh, Saket; Verma, Shaily List Homomorphism: Beyond the Known BoundariesTheoretical Informatics: Latin American Symposium (LATIN) 2022 2022: 593–609
Given two graphs \(G\) and \(H\), and a list \(L(u)V(H)\) associated with each \(uV(G)\), a list homomorphism from \(G\) to \(H\) is a mapping \(f:V(G)V(H)\) such that (i) for all \(uV(G)\), \(f(u) L(u)\), and (ii) for all \(u,vV(G)\), if \(uvE(G)\) then \(f(u)f(v)E(H)\). The List Homomorphism problem asks whether there exists a list homomorphism from \(G\) to \(H\). Enright, Stewart and Tardos SIAM J. Discret. Math., 2014 showed that the List Homomorphism problem can be solved in \( \mathcal{O(n^{k^2}-3k+4) \) time on graphs where every connected induced subgraph of \(G\) admits ``a multichain ordering'' that includes permutation graphs, biconvex graphs, and interval graphs, where \(n=|V(G)|\) and \(k=|V(H)|\). We prove that List Homomorphism parameterized by \(k\) even when \(G\) is a bipartite permutation graph is W1-hard. In fact, our reduction implies that it is not solvable in time \(n^o(k)\), unless the Exponential Time Hypothesis (ETH) fails. We complement this result with a matching upper bound and another positive result. We design a \(O(n^8k+3)\) time algorithm for List Homomorphism on bipartite graphs that admit a multichain ordering that includes the class of bipartite permutation graphs and biconvex graphs. Moreover, we show that for bipartite graph \(G\) that admits a multichain ordering, List Homomorphism is fixed parameter tractable when parameterized by \(k\) and the number of layers in the multichain ordering of \(G\). In addition, we study a variant of List Homomorphism called List Locally Surjective Homomorphism. We prove that List Locally Surjective Homomorphism parameterized by the number of vertices in \(H\) is wh, even when \(G\) is a chordal graph and \(H\) is a split graph.
Verma, Shaily; Fu, Hung-Lin; Panda, B. S. Adjacent vertex distinguishing total coloring in split graphsDiscret. Math. 2022: 113061
An adjacent vertex distinguishing (AVD)-total coloring of a graph \(G\) is a total coloring such that any two adjacent vertices \(u\) and \(v\) have the distinct set of colors, that is, \(C(u)neq C(v)\), where \(C(v)\) is the set of colors of the edges incident on \(v\) and the color of \(v\). The adjacent vertex distinguishing (AVD)-total chromatic number of a graph \(G\), \(\chi_a''(G)\) is the minimum integer \(k\) such that there exists an AVD-total coloring of \(G\) using \(k\) colors. It is known that \(\chi_a''(G)\geq \Delta+1\), where \(\Delta\) is the maximum degree of the graph. The AVD-total coloring conjecture states that for any graph \(G\), \(\chi_a''(G)\leq \Delta+3\). In this paper, we study the AVD-total coloring in split graphs. We prove the AVD-total coloring conjecture for split graphs and classify certain classes of split graphs according to their AVD-total chromatic number.
Derbisz, Jan; Kanesh, Lawqueen; Madathil, Jayakrishnan; Sahu, Abhishek; Saurabh, Saket; Verma, Shaily A Polynomial Kernel for Bipartite Permutation Vertex DeletionAlgorithmica 2022: 3246–3275
In a permutation graph, vertices represent the elements of a permutation, and edges represent pairs of elements that are reversed by the permutation. In the sc Permutation Vertex Deletion problem, given an undirected graph \(G\) and an integer \(k\), the objective is to test whether there exists a vertex subset \(S subseteq V(G)\) such that \(|S| \leq k\) and \(G-S\) is a permutation graph. The parameterized complexity of Permutation Vertex Deletion is a well-known open problem. Bożyk et al. [IPEC 2020] initiated a study on this problem by requiring that \(G-S\) be a bipartite permutation graph (a permutation graph that is bipartite). They called this the Bipartite Permutation Vertex Deletion (BPVD) problem. They showed that the problem admits a factor 9-approximation algorithm as well as a fixed parameter tractable (FPT) algorithm running in time \(\mathcal{O(9^k |V(G)|^{9})\). Moreover, they posed the question whether BPVD admits a polynomial kernel. We resolve this question in the affirmative by designing a polynomial kernel for BPVD. In particular, we obtain the following: Given an instance \((G,k)\) of BPVD, in polynomial time we obtain an equivalent instance \((G',k')\) of BPVD such that \(k'\leq k\), and \(|V(G')|+|E(G')| leq k^\mathcal{O(1)}\).
Ramanujan, M. S.; Sahu, Abhishek; Saurabh, Saket; Verma, Shaily An Exact Algorithm for Knot-Free Vertex DeletionMathematical Foundations of Computer Science (MFCS) 2022: 78:1–78:15
The study of the Knot-Free Vertex Deletion problem emerges from its application in the resolution of deadlocks called knots, detected in a classical distributed computation model, that is, the OR-model. A strongly connected subgraph \(Q\) of a digraph \(D\) with at least two vertices is said to be a knot if there is no arc \((u,v)\) of \(D\) with \(u in V(Q)\) and \(v notin V(Q)\) (no-out neighbors of the vertices in \(Q\)). Given a directed graph \(D\), the Knot-Free Vertex Deletion problem asks to compute a minimum-size subset \(Ssubset V(D)\) such that \(D[V\setminus S]\) contains no knots. There is no exact algorithm known for the problem in the literature that is faster than the trivial \(\mathcal{O^\star(2^n)\) brute-force algorithm. In this paper, we obtain the first non-trivial upper bound for the problem by designing an exact algorithm running in time \(\mathcal{O^\star(1.576^n)\), where \(n\) is the size of the vertex set in \(D\).