Source author record

Prafullkumar Tale

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics math.CO

Catalog footprint

Research overview

9works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction

In this work, we initiate the complexity study of Biclique Contraction and Balanced Biclique Contraction. In these problems, given as input a graph G and an integer k, the objective is to determine whether one can contract at most k edges in G to obtain a biclique and a balanced biclique, respectively. We first prove that these problems are NP-complete even when the input graph is bipartite. Next, we study the parameterized complexity of these problems and show that they admit single exponential-time FPT algorithms when parameterized by the number k of edge contractions. Then, we show that Balanced Biclique Contraction admits a quadratic vertex kernel while Biclique Contraction does not admit any polynomial compression (or kernel) under standard complexity-theoretic assumptions. We also give faster FPT algorithms for contraction to restricted bicliques.

preprint2022arXiv

Domination and Cut Problems on Chordal Graphs with Bounded Leafage

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 domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018, Algorithmica 2020] proved, among other things, that Dominating Set on chordal graphs admits an algorithm running in time $2^{O(l^2)} n^{O(1)}$ . We present a conceptually much simpler algorithm that runs in time $2^{O(l)} n^{O(1)}$ . We extend our approach to obtain similar results for Connected Dominating Set and Steiner Tree. We then consider the two classical cut problems MultiCut with Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove that the former is W[1]-hard when parameterized by the leafage and complement this result by presenting a simple $n^{O(l)}$ -time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals on chordal graphs can be solved, in contrast, in $n^{O(1)}$ -time.

preprint2022arXiv

Parameterized and Exact Algorithms for Class Domination Coloring

A class domination coloring (also called cd-Coloring or dominated coloring) of a graph is a proper coloring in which every color class is contained in the neighbourhood of some vertex. The minimum number of colors required for any cd-coloring of $G$ , denoted by $χ_{cd}(G)$ , is called the class domination chromatic number (cd-chromatic number) of $G$ . 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. (1) Given a graph $G$ on $n$ vertices, find its cd-chromatic number. (2) Given a graph $G$ and integers $k$ and $q$ , can we delete at most $k$ vertices such that the cd-chromatic number of the resulting graph is at most $q$ ? For the first problem, we give an exact algorithm with running time $\Oh(2^n n^4 \log n)$. Also, we show that the problem is \FPT\ with respect to the number $q$ of colors as the parameter on chordal graphs. On graphs of girth at least 5, we show that the problem also admits a kernel with $\Oh(q^3)$ vertices. For the second (deletion) problem, we show \NP-hardness for each $q \geq 2$ . Further, on split graphs, we show that the problem is \NP-hard if $q$ is a part of the input and \FPT\ with respect to $k$ and $q$ as combined parameters. As recognizing graphs with cd-chromatic number at most $q$ is \NP-hard in general for $q \geq 4$ , the deletion problem is unlikely to be \FPT\ when parameterized by the size of the deletion set on general graphs. We show fixed parameter tractability for $q \in \{2,3\}$ using the known algorithms for finding a vertex cover and an odd cycle transversal as subroutines.

preprint2022arXiv

Parameterized Complexity of Weighted Multicut in Trees

The Edge Multicut problem is a classical cut problem where given an undirected graph $G$ , a set of pairs of vertices $\mathcal{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 \mathcal{P}$ , $G-S$ has no path from $s$ to $t$ . Edge Multicut has been relatively recently shown to be fixed-parameter tractable (FPT), parameterized by $k$ , by Marx and Razgon [SICOMP 2014], and independently by Bousquet et al. [SICOMP 2018]. In the weighted version of the problem, called Weighted Edge Multicut one is additionally given a weight function $\mathtt{wt} : E(G) \to \mathbb{N}$ and a weight bound $w$ , and the goal is to determine if there is a solution of size at most $k$ and weight at most $w$ . Both the FPT algorithms for Edge Multicut by Marx et al. and Bousquet et al. fail to generalize to the weighted setting. In fact, the weighted problem is non-trivial even on trees and determining whether Weighted Edge Multicut on trees is FPT was explicitly posed as an open problem by Bousquet et al. [STACS 2009]. In this article, we answer this question positively by designing an algorithm which uses a very recent result by Kim et al. [STOC 2022] about directed flow augmentation as subroutine. We also study a variant of this problem where there is no bound on the size of the solution, but the parameter is a structural property of the input, for example, the number of leaves of the tree. We strengthen our results by stating them for the more general vertex deletion version.

preprint2022arXiv

Reducing the Vertex Cover Number via Edge Contractions

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, among other results, that unlike most of the so-called blocker problems, CONTRACTION(vc) admits an XP algorithm running in time $f(d) \cdot 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: 1. 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) \cdot n^{o(k + d)}$ for any function $f$ . In particular, this answers the open question stated in Lima et al. [JCSS 2021] in the negative. 2. 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. 3. CONTRACTION(vc) can be solved in time $2^{O(d)} \cdot n^{k - d + O(1)}$ . This XP algorithm improves the one of Lima et al. [JCSS 2021], 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 hard, it shows that when $k=d$ , the problem is FPT parameterized by $d$ (or by $k$ ).

preprint2022arXiv

Sparsification Lower Bound for Linear Spanners in Directed Graphs

For $α\ge 1$ , $β\ge 0$ , and a graph $G$ , a spanning subgraph $H$ of $G$ is said to be an $(α, β)$ -spanner if $\dist(u, v, H) \le α\cdot \dist(u, v, G) + β$ holds for any pair of vertices $u$ and $v$ . These type of spanners, called \emph{linear spanners}, generalizes \emph{additive spanners} and \emph{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 \textsc{Directed Linear Spanner} parameterized by the number of vertices $n$ admits no polynomial compression of size $\calO(n^{2 - ε})$ for any $ε> 0$ unless $\NP \subseteq \coNP/poly$. We show that similar results hold for \textsc{Directed Additive Spanner} and \textsc{Directed Multiplicative Spanner} problems. This sparsification lower bound holds even when the input is a directed acyclic graph and $α, β$ are \emph{any} computable functions of the distance being approximated.

preprint2020arXiv

On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

A graph operation that {\em contracts edges} is one of the fundamental operations in the theory of graph minors. Parameterized Complexity of editing to a family of graphs by contracting $k$ edges has recently gained substantial scientific attention, and several new results have been obtained. Some important families of graphs, namely the subfamilies of chordal graphs, in the context of edge contractions, have proven to be significantly difficult than one might expect. In this paper, we study the \textsc{ $\cal F$ -Contraction} problem, where $\cal F$ is a subfamily of chordal graphs, in the realm of parameterized approximation. Formally, given a graph $G$ and an integer $k$ , \textsc{ $\cal F$ -Contraction} asks whether there exists $X \subseteq E(G)$ such that $G/X \in \cal F$ and $|X| \leq k$ . Here, $G/X$ is the graph obtained from $G$ by contracting edges in $X$ . We obtain the following results for the \textsc{ $\cal F$ -Contraction} problem. $(1)$ We show that \textsc{Clique Contraction} admits a polynomial-size approximate kernelization scheme (\textsf{PSAKS}). $(2)$ We give a $(2+ε)$ -approximate polynomial kernel for \textsc{Split Contraction} (which also implies a factor $(2+ε)$ -\FPT-approximation algorithm for \textsc{ Split Contraction}). Furthermore, we show that, assuming \textsf{ Gap-ETH}, there is no $\left(\frac{5}{4}-δ\right)$ -\FPT-approximation algorithm for \textsc{Split Contraction}. Here, $ε, δ>0$ are fixed constants. $(3)$ \textsc{Chordal Contraction} is known to be \WTH. We complement this result by observing that the existing \textsf{W[2]-hardness} reduction can be adapted to show that, assuming \FPT $\neq$ \textsf{W[1]}, there is no $F(k)$ -\FPT-approximation algorithm for \textsc{Chordal Contraction}. Here, $F(k)$ is an arbitrary function depending on $k$ alone.

preprint2020arXiv

On the Parameterized Complexity Of Grid Contraction

For a family of graphs $\mathcal{G}$ , the $\mathcal{G}$ -\textsc{Contraction} problem takes as an input a graph $G$ and an integer $k$ , and the goal is to decide if there exists $F \subseteq E(G)$ of size at most $k$ such that $G/F$ belongs to $\mathcal{G}$ . Here, $G/F$ is the graph obtained from $G$ by contracting all the edges in $F$ . In this article, we initiate the study of \textsc{Grid Contraction} from the parameterized complexity point of view. We present a fixed parameter tractable algorithm, running in time $c^k \cdot |V(G)|^{\mathcal{O}(1)}$ , for this problem. We complement this result by proving that unless Ð fails, there is no algorithm for \textsc{Grid Contraction} with running time $c^{o(k)} \cdot |V(G)|^{\mathcal{O}(1)}$ . We also present a polynomial kernel for this problem.

preprint2020arXiv

Parameterized Complexity of Maximum Edge Colorable Subgraph

A graph $H$ is {\em $p$ -edge colorable} if there is a coloring $ψ: E(H) \rightarrow \{1,2,\dots,p\}$ , such that for distinct $uv, vw \in E(H)$ , we have $ψ(uv) \neq ψ(vw)$ . The {\sc 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)| \geq l$ . We study the above problem from the viewpoint of Parameterized Complexity. We obtain \FPT\ algorithms when parameterized by: $(1)$ the vertex cover number of $G$ , by using {\sc Integer Linear Programming}, and $(2)$ $l$ , a randomized algorithm via a reduction to \textsc{Rainbow Matching}, and a deterministic algorithm by using color coding, and divide and color. With respect to the parameters $p+k$ , where $k$ is one of the following: $(1)$ the solution size, $l$ , $(2)$ the vertex cover number of $G$ , and $(3)$ $l - {\mm}(G)$, where ${\mm}(G)$ is the size of a maximum matching in $G$ ; we show that the (decision version of the) problem admits a kernel with $\mathcal{O}(k \cdot p)$ vertices. Furthermore, we show that there is no kernel of size $\mathcal{O}(k^{1-ε} \cdot f(p))$ , for any $ε> 0$ and computable function $f$ , unless $\NP \subseteq \CONPpoly$.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Prafullkumar Tale

Research overview

Is this your work?

9 publications

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction

Domination and Cut Problems on Chordal Graphs with Bounded Leafage

Parameterized and Exact Algorithms for Class Domination Coloring

Parameterized Complexity of Weighted Multicut in Trees

Reducing the Vertex Cover Number via Edge Contractions

Sparsification Lower Bound for Linear Spanners in Directed Graphs

On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

On the Parameterized Complexity Of Grid Contraction

Parameterized Complexity of Maximum Edge Colorable Subgraph

See the researcher in context

Building this map preview