Author name cluster

Prafullkumar Tale

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

2 author rows

TCS Journal 2025 Journal Article

Telephone Broadcast on graphs of treewidth two

Prafullkumar Tale

Consider the Telephone Broadcast problem in which an input is a connected graph G on n vertices, a source vertex s ∈ V ( G ), and a positive integer t. The objective is to decide whether there is a broadcast protocol from s that ensures that all the vertices of G get the message in at most t rounds. We consider the broadcast protocol where, in a round, any node aware of the message can forward it to at most one of its neighbors. Fomin, Fraigniaud, and Golovach [WG 2023; TCS 2024] asked whether the problem is Image 1 when parameterized by the feedback vertex set number of the graph. We answer this question in the negative. • Telephone Broadcast, when restricted to graphs of the feedback vertex number one, and hence treewidth of two, is Image 2 -complete. We find this a relatively rare example of problems that admit a polynomial-time algorithm on trees but is Image 2 -complete on graphs of treewidth two.

Details DOI

NeurIPS Conference 2025 Conference Paper

The Parameterized Complexity of Computing the VC-Dimension

Florent Foucaud
Harmender Gahlawat
Fionn Mc Inerney
Prafullkumar Tale

The VC-dimension is a well-studied and fundamental complexity measure of a set system (or hypergraph) that is central to many areas of machine learning. We establish several new results on the complexity of computing the VC-dimension. In particular, given a hypergraph $\mathcal{H}=(\mathcal{V}, \mathcal{E})$, we prove that the naive $2^{\mathcal{O}(|\mathcal{V}|)}$-time algorithm is asymptotically tight under the Exponential Time Hypothesis (ETH). We then prove that the problem admits a $1$-additive fixed-parameter approximation algorithm when parameterized by the maximum degree of $\mathcal{H}$ and a fixed-parameter algorithm when parameterized by its dimension, and that these are essentially the only such exploitable structural parameters. Lastly, we consider a generalization of the problem, formulated using graphs, which captures the VC-dimension of both set systems and graphs. We design a $2^{\mathcal{O}(\texttt{tw}\cdot \log \texttt{tw})}\cdot |V|$-time algorithm for any graph $G=(V, E)$ of treewidth $\texttt{tw}$ (which, for a set system, applies to the treewidth of its incidence graph). This is in contrast with closely related problems that require a double-exponential dependency on the treewidth (assuming the ETH).

PDF Details

TCS Journal 2023 Journal Article

A single exponential-time FPT algorithm for cactus contraction

R. Krithika
Pranabendu Misra
Prafullkumar Tale

For a collection F of graphs, the F -Contraction problem takes a graph G and an integer k as input and decides if G can be modified to some graph in F using at most k edge contractions. The F -Contraction problem is NP-Complete for several graph classes F. Heggernes et al. (2014) [4] initiated the study of F -Contraction in the realm of parameterized complexity. They showed that it is FPT if F is the set of all trees or the set of all paths. In this paper, we study F -Contraction where F is the set of all cactus graphs and show that we can solve it in 2 O ( k ) ⋅ | V ( G ) | O ( 1 ) time.

Details DOI

TCS Journal 2023 Journal Article

Parameterized complexity of multicut in weighted trees

Esther Galby
Dániel Marx
Philipp Schepper
Roohani Sharma
Prafullkumar Tale

In the Multicut problem, 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 ) ∈ P, the graph G − S has no path from s to t. In this article we first study the parameterized complexity of a variant of this problem, where the input graph is edge-weighted with arbitrary weights and the goal is to find a solution of minimum weight. Since weights are arbitrarily large, the weight of the solution is not a good choice for a parameter. The weighted problem is non-trivial even on trees and we study this problem on trees parameterized by structural parameters like the number of leaves and the request degree of every vertex. The studied parameters naturally interpolate the known polynomial time and NP -hardness results for this problem. We also give an FPT algorithm for another variant called Weighted Multicut, where given an edge-weighted tree, the goal is to find a solution of size at most k edges that minimizes the weight.

Details DOI

SODA Conference 2022 Conference Paper

A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs

Dániel Marx
Pranabendu Misra
Daniel Neuen
Prafullkumar Tale

Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. The goal of this paper is to introduce a framework for obtaining time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems. Our starting point is the Node U nique L abel C over problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2-connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2-connected component of the solution). We show that there is an time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of well-studied problems, for example, O dd C ycle T ransversal, S ubset F eedback V ertex S et, G roup F eedback V ertex S et, S ubset G roup F eedback V ertex S et, V ertex M ultiway C ut, and C omponent O rder C onnectivity. For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain time (randomized) algorithms for V ertex M ultiway C ut, G roup F eedback V ertex S et, and S ubset F eedback V ertex S et. Our algorithms are designed with possible generalization to H -minor free graphs in mind. To obtain the same time algorithms on H -minor free graphs, the only missing piece is the vertex version of a contraction decomposition theorem that we currently have only for planar graphs.

Details

MFCS Conference 2022 Conference Paper

Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters

Esther Galby
Liana Khazaliya
Fionn Mc Inerney
Roohani Sharma
Prafullkumar Tale

For a graph G, a subset S ⊆ V(G) is called a resolving set if for any two vertices u, v ∈ V(G), there exists a vertex w ∈ S such that d(w, u) ≠ d(w, v). The Metric Dimension problem takes as input a graph G and a positive integer k, and asks whether there exists a resolving set of size at most k. This problem was introduced in the 1970s and is known to be NP-hard [GT 61 in Garey and Johnson’s book]. In the realm of parameterized complexity, Hartung and Nichterlein [CCC 2013] proved that the problem is W[2]-hard when parameterized by the natural parameter k. They also observed that it is FPT when parameterized by the vertex cover number and asked about its complexity under smaller parameters, in particular the feedback vertex set number. We answer this question by proving that Metric Dimension is W[1]-hard when parameterized by the feedback vertex set number. This also improves the result of Bonnet and Purohit [IPEC 2019] which states that the problem is W[1]-hard parameterized by the treewidth. Regarding the parameterization by the vertex cover number, we prove that Metric Dimension does not admit a polynomial kernel under this parameterization unless NP ⊆ coNP/poly. We observe that a similar result holds when the parameter is the distance to clique. On the positive side, we show that Metric Dimension is FPT when parameterized by either the distance to cluster or the distance to co-cluster, both of which are smaller parameters than the vertex cover number.

Details

MFCS Conference 2022 Conference Paper

Reducing the Vertex Cover Number via Edge Contractions

Paloma T. Lima
Vinícius Fernandes dos Santos
Ignasi Sau
Uéverton S. Souza
Prafullkumar Tale

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. [MFCS 2020, JCSS 2021] proved, among other results, that unlike most of the so-called blocker problems, Contraction(vc) admits an XP algorithm running in time f(d) ⋅ n^O(d). They left open the question of whether this problem is FPT under this parameterization. In this article, we continue this line of research and prove the following results: - Contraction(vc) is W[1]-hard parameterized by k + d. Moreover, unless the ETH fails, the problem does not admit an algorithm running in time f(k + d) ⋅ n^o(k + d) for any function f. In particular, this answers the open question stated in Lima et al. [MFCS 2020] in the negative. - It is NP-hard to decide whether an instance (G, k, d) of {Contraction(vc)} is a Yes-instance even when k = d, hence enhancing our understanding of the classical complexity of the problem. - Contraction(vc) can be solved in time 2^O(d) ⋅ n^{k - d + O(1)}. This XP algorithm improves the one of Lima et al. [MFCS 2020], which uses Courcelle’s theorem as a subroutine and hence, the f(d)-factor in the running time is non-explicit and probably very large. On the other hand, this shows that when k = d, the problem is FPT parameterized by d (or by k).

Details

TCS Journal 2022 Journal Article

Sparsification lower bound for linear spanners in directed graphs

Prafullkumar Tale

For α ≥ 1, β ≥ 0, and a graph G, a spanning subgraph H of G is said to be an ( α, β ) -spanner if dist ( u, v, H ) ≤ α ⋅ dist ( u, v, G ) + β holds for any pair of vertices u and v. These type of spanners, called linear spanners, generalizes additive spanners and multiplicative spanners. Recently, Fomin, Golovach, Lochet, Misra, Saurabh, and Sharma initiated the study of additive and multiplicative spanners for directed graphs (IPEC 2020). In this article, we continue this line of research and prove that Directed Linear Spanner parameterized by the number of vertices n admits no polynomial compression of size O ( n 2 − ϵ ) for any ϵ > 0 unless NP ⊆ coNP / p o l y. We show that similar results hold for Directed Additive Spanner and Directed Multiplicative Spanner problems. This sparsification lower bound holds even when the input is a directed acyclic graph and α, β are any computable functions of the distance being approximated.

Details DOI

TCS Journal 2021 Journal Article

Paths to trees and cacti

Akanksha Agrawal
Lawqueen Kanesh
Saket Saurabh
Prafullkumar Tale

We know that Tree Contraction does not admit a polynomial kernel unless NP ⊆ coNP/poly, while Path Contraction admits a kernel with O ( k ) vertices. The starting point of this article is the following natural questions: What is the structure of the family of paths that allows Path Contraction to admit a polynomial kernel? Apart from the size of the solution, what other additional parameters should we consider so we can design polynomial kernels for these basic contraction problems? To design polynomial kernels, we consider the family of trees with the bounded number of leaves (note that the family of paths are trees with at most two leaves). In particular, we study Bounded Tree Contraction. Here, an input is a graph G, integers k and ℓ, and the goal is to decide whether, there is a subset F ⊆ E ( G ) of size at most k such that G / F is a tree with at most ℓ leaves. We design a kernel with O ( k ℓ ) vertices and O ( k 2 + k ℓ ) edges for this problem. We complement this result by giving kernelization lower bound. We also prove similar results for Bounded Out-Tree Contraction and Bounded Cactus Contraction.

Details DOI

TCS Journal 2019 Journal Article

Harmonious coloring: Parameterized algorithms and upper bounds

Sudeshna Kolay
Ragukumar Pandurangan
Fahad Panolan
Venkatesh Raman
Prafullkumar Tale

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. We consider various parameterizations like by solution size, by above or below known guaranteed bounds and by the vertex cover number of the graph. While the problem has a simple quadratic kernel when parameterized by the solution size, our main result is that the problem is fixed-parameter tractable when parameterized by the size of a vertex cover of the graph. This is shown by reducing the problem to multiple instances of fixed variable integer linear programming. We also observe that it is W [ 1 ] -hard to determine whether at most n − k or Δ + 1 + k colors are sufficient in a harmonious coloring of an n-vertex graph G, where Δ is the maximum degree of G and k is the parameter. Concerning exact exponential time algorithms, we develop a 2 n n O ( 1 ) algorithm for finding a minimum harmonious coloring in split graphs improving on the naive 2 O ( n log ⁡ n ) algorithm.

Details DOI