Research Projects

A graph G and two different solutions to a graph problem can be transformed into each other using a step-by-step modification process. The reconfiguration problem is the decision problem of determining if a graph G and two configurations C and C' can be iteratively modified according to specified rules, ensuring each intermediate configuration corresponds to a valid solution of the problem. The Independent Set reconfiguration problem is a well-studied problem where tokens are placed on vertices in the initial configuration and determined to slide from one vertex to another along an edge in the graph. The problem can be solved in polynomial time for interval graphs and claw-free graphs, bipartite permutation graphs, chordal graphs, and even-hole-free graphs. The eternal vertex cover problem is a multi-round attacker-defender game where guards are placed on vertices and an attacker identifies an edge to be attacked. The minimum number of guards required to protect a graph G from infinite attacks is called the eternal vertex cover number of G. It is proved that the problem is NP-hard for any general graph, but polynomial time is solved for graphs like cycles, paths, some generalized trees, chordal graphs, and cactus graphs. For bipartite graphs, the problem is NP-hard. Attempting a polynomial time algorithm for the problem for outerplanar graphs is an interesting direction, and characterizing the class of bipartite graphs for which the eternal vertex cover number and vertex cover coincide is also an interesting problem.

0