Graph Decomposition and Weisfeiler Leman algorithm Prof. Bireswar Das
Weisfeiler and Leman Algorithm is a well-known combinatorial algorithm for checking the isomorphism of graphs. It has various theoretical and practical applications. It has been shown that GNN is as powerful as 1-WL to decide graph(subgraph) isomorphism. Increasing the dimension of WL increases its power but at cost of the increase in runtime and space requirement. In this project, we are trying to decompose the graphs and run higher dimensional WL that can easily be executed. We have shown it is at least as powerful as WL. This will help in the implementation of the Weisfeiler kernel(GNN model) efficiently on large graphs.
Graphs on groups Prof. Bireswar Das
Group Theory is a core subject of mathematics in which we study algebraic structure, which holds some property called groups. Group has been studied as it has various applications in other areas. Also, Group theory helps to study symmetry. Here, group elements are represented as nodes, and edges represent their relation. Various kinds of graphs are defined to study group properties using graph theory. We mainly focus on the commuting graph, non-commuting graph, Power graph, and enhanced power graph to study group structure. We try to study similarity in graph structure using WL. We also try to solve problems that are NP-hard on general graphs.
Linear Rank width one graph Prof. Bireswar Das
We designed a linear time algorithm to recognise whether the linear rank width of a given graph is one. Earlier it was polynomial time. The linear time recognition help to get a linear time isomorphism check for linear rank width one graphs. We also designed a linear time algorithm for many problems, which are NP-Hard on general graphs. The algorithm presented here has fewer constant factors and can efficiently be executed using linear space. Thus, it can be easily applied.
Pebbling Reachability Prof. Neeldhara Mishra
Pebble reachability is known to be NP-hard on the general graph. Recently, it has been shown that it is also NP-hard on diameter two graphs. We introduce different parameters and gave FPT algorithm on these parameters. Also, the kernel size that we got is optimal.
Rank Reduction by Graph Modification Prof. Neeldhara Mishra
We studied the previous vertex and edge deletion kernel and algorithm to reduce the rank of the matrix over $F_2$ and $\mathcal{R}$. We have also studied oriented graphs. We design a technique that is different and can give a better bound in some cases.