Prafullkumar Tale

The game of rendezvous with adversaries is a game on a graph played by two players: Facilitator and Divider. Facilitator has two agents and Divider has a team of k agents. While the initial positions of Facilitator’s agents are fixed, Divider gets to select the initial positions of his agents. Then, they take turns to move their agents to adjacent vertices (or stay put) with Facilitator’s goal to bring both her agents at same vertex and Divider’s goal to prevent it. The computational question of interest is to determine if Facilitator has a winning strategy against Divider with k agents. In this work, we prove that this problem is hard even when the graph is very close to a forest.

The leafage of a chordal graph G is the minimum integer l such that G can be realized as an intersection graph of subtrees of a tree with l leaves. We consider structural parameterization by the leafage of classical problems like DOMINATING SET, MULTI-CUT, STEINER-TREE on chordal graphs. We also prove that MULTIWAY CUT with Undeletable Terminals on chordal graphs can be solved in polynomial time.

For a graph G, a subset S of V (G) is called a resolving set if for any two vertices u, v in V(G), there is a vertex w in S such that dist(u, w) is not equal to dist(v, w). The METRIC DIMENSTION problem ask whether there exists a resolving set of size at most k in the given graph. In this article, we advance our understanding of structural parameterization of the problem.

The CONTRACTION(vc) problem takes as input a graph G on n vertices and two integers k and d, and asks whether one can contract at most k edges to reduce the size of a minimum vertex cover of G by at least d. Recently, Lima et al. [JCSS 2021] proved that unlike most of the so-called blocker problems, CONTRACTION(vc) admits an XP algorithm. They left open the question of whether this problem is FPT under the standard parameterization. We answer this question in negative and prove some othe results.

The Multicut problem is a classical cut problem where given an undirected graph G, a set of pairs of vertices P, and a budget k. The goal is to determine if there is a set S of at most k edges such that for each (s,t) in P, G - S has no path from s to t. In the weighted version of the problem, one is additionally given a weight function, the goal is to determine if there is a solution of size at most k and weight at most w. Bousquet et al. [STACS 2009] asked whether Weighted Multicut on trees is FPT. In this article, we answer this question positively by designing an algorithm using a very recent technique of directed flow augmentation by Kim et al. [STOC 2022].

For a graph or a digraph, a spanner is its subgraph that preserves lengths of shortest paths between any two vertices in it up to some additive and/or multiplicative error. For undirected graphs, there are algorithms that find a spanner of non-trivial size in polynomial time. We prove that such algorithms are unlikely for directed graphs unless a widely believed conjecture fails.

In this article, we present an FPT-approximation algorithm for contraction to the three graph classes viz cliques, split graphs, and chordal graphs. We present (1 + eps) algorithm for Clique Contraction, (2 + eps) algorithm for Split Contraction. We prove that such algorithm is not possible for Chordal Contraction. Moreover, for Split Contraction the algorithm can not be imporved to (5/4 - eps) for any eps > 0, unless the Randomized-ETH fails.

A graph H is p-edge colorable if there is a coloring f from E(H) to {1, 2, ... , p}, such that for distinct edges uv, vw in E(H), we have f(uv) is not equal to f(vw). The Maximum Edge-Colorable Subgraph problem takes as input a graph G and integers l and p, and the objective is to find a subgraph H of G and a p-edge-coloring of H, such that |E(H)| is at least l. We study the above problem from the viewpoint of Parameterized Complexity.

In the Maximum Degree Contraction problem, input is a graph G on n vertices, and integers k, d, and the objective is to check whether G can be transformed into a graph of maximum degree at most d, using at most k edge contractions. As our first result, we prove that a simple brute-force algorithm is asymptotically optimal under Exponential Time Hypothesis (ETH). We present a different FPT algorithm for this problem and resolve an open equation stated in the literature.

In this article, we initiate the study of Grid Contraction from the parameterized complexity point of view. In this problem, an input is a graph G and an integer k, and the goal is to decide whether one can convert G into a grid by at most k edge contractions. We present a single exponential fixed-parameter tractable algorithm for this problem. We complement this result by proving that this Algorithm can not be improved significantly unless ETH fails. We also present a polynomial kernel for this problem.

In the Subset Feedback Vertex Set (Subset-FVS) problem the input is a graph G, a subset T of vertices of G called the “terminal” vertices, and an integer k. The task is to determine whether there exists a subset of vertices of cardinality at most k which together intersect all cycles which pass through the terminals. In this work we improve kernelization, fixed parameter tractable, and exact algorithms for Subset-FVS on Split graph. Our algorithm works even for chordal graphs.

The problem Path Contraction admits a simple algorithm running in time 2^n poly(n). In spite of the deceptive simplicity of the problem, beating the 2^n bound for Path Contraction seems quite challenging. In this paper, we design an exact exponential time algorithm for Path Contraction that runs in time 1.99987^n poly(n).

For a collection FF of graphs, given a graph G and an integer k, the FF-Contraction problem asks whether we can contract k edges in G to obtain a graph in FF. Heggerners et al. [Algorithmica (2014)] presented FPT algorithms for Tree-Contraction and Path-Contraction. In this paper, we study contraction to a class larger than trees, namely, cactus graphs and present a single exponential FPT algorithm for Cactus- Contraction.

Path-Contraction and Tree-Contraction are FPT but Tree-Contraction does not admit a polynomial kernel while Path-Contraction does. In light of these mixed results, two natural questions are:
1. What additional parameter can we associate with Tree-Contraction such that it admits a polynomial kernel?
2. What additional parameter can we associate with Tree-Contraction such that an FPT algorithm with combination of these parameterizations leads to an algorithm that generalizes the FPT algorithm on trees?
In this paper we focus on the second question. We addressed the first question [ P-5 ].

Path-Contraction and Tree-Contraction are FPT but Tree-Contraction does not admit a polynomial kernel while Path-Contraction does. In light of these mixed results, two natural questions are:
1. What additional parameter can we associate with Tree-Contraction such that it admits a polynomial kernel?
2. What additional parameter can we associate with Tree-Contraction such that an FPT algorithm with combination of these parameterizations leads to an algorithm that generalizes the FPT algorithm on trees?
In this paper we focus on the second question. We addressed the first question [ P-6 ].

A class domination coloring of a graph is a proper coloring such that for every color class, there is a vertex that dominates it. In this work, we consider two problems associated with the cd-coloring of a graph in the context of exact exponential-time algorithms and parameterized complexity.

The goal in the area of dynamic graph algorithms is to efficiently maintain a solution under edge additions and deletions. We study the Dynamic \Pi-Deletion problem which is the dynamic variant of the classical \Pi-Deletion problem and show NP-hardness, fixed-parameter tractability and kernelization results.

A harmonious coloring of a graph is a partitioning of its vertex set into parts such that, there are no edges inside each part, and there is at most one edge between any pair of parts. It is known that finding a minimum harmonious coloring number is NP-hard even in special classes of graphs like trees and split graphs. We initiate a study of parameterized and exact exponential time complexity of harmonious coloring.