Source author record

Akanksha Agrawal

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 Discrete Mathematics math.CO Computational Complexity Computational Geometry Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

11works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2024arXiv

A Polynomial Kernel for Proper Helly Circular-arc Vertex Deletion

A proper Helly circular-arc graph is an intersection graph of a set of arcs on a circle such that none of the arcs properly contains any other arc and every set of pairwise intersecting arcs has a common intersection. The Proper Helly Circular-arc Vertex Deletion problem takes as input a graph $G$ and an integer $k$ , and the goal is to check if we can remove at most $k$ vertices from the graph to obtain a proper Helly circular-arc graph; the parameter is $k$ . Recently, Cao et al.~[MFCS 2023] obtained an FPT algorithm for this (and related) problem. In this work, we obtain a polynomial kernel for the problem.

preprint2022arXiv

Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent

For a graph class ${\cal H}$ , the graph parameters elimination distance to ${\cal H}$ (denoted by ${\bf ed}_{\cal H}$ ) [Bulian and Dawar, Algorithmica, 2016], and ${\cal H}$ -treewidth (denoted by ${\bf tw}_{\cal H}$ ) [Eiben et al. JCSS, 2021] aim to minimize the treedepth and treewidth, respectively, of the "torso" of the graph induced on a modulator to the graph class ${\cal H}$ . Here, the torso of a vertex set $S$ in a graph $G$ is the graph with vertex set $S$ and an edge between two vertices $u, v \in S$ if there is a path between $u$ and $v$ in $G$ whose internal vertices all lie outside $S$ . In this paper, we show that from the perspective of (non-uniform) fixed-parameter tractability (FPT), the three parameters described above give equally powerful parameterizations for every hereditary graph class ${\cal H}$ that satisfies mild additional conditions. In fact, we show that for every hereditary graph class ${\cal H}$ satisfying mild additional conditions, with the exception of ${\bf tw}_{\cal H}$ parameterized by ${\bf ed}_{\cal H}$ , for every pair of these parameters, computing one parameterized by itself or any of the others is FPT-equivalent to the standard vertex-deletion (to ${\cal H}$ ) problem. As an example, we prove that an FPT algorithm for the vertex-deletion problem implies a non-uniform FPT algorithm for computing ${\bf ed}_{\cal H}$ and ${\bf tw}_{\cal H}$ . The conclusions of non-uniform FPT algorithms being somewhat unsatisfactory, we essentially prove that if ${\cal H}$ is hereditary, union-closed, CMSO-definable, and (a) the canonical equivalence relation (or any refinement thereof) for membership in the class can be efficiently computed, or (b) the class admits a "strong irrelevant vertex rule", then there exists a uniform FPT algorithm for ${\bf ed}_{\cal H}$ .

preprint2022arXiv

On finding short reconfiguration sequences between independent sets

Assume we are given a graph $G$ , two independent sets $S$ and $T$ in $G$ of size $k \geq 1$ , and a positive integer $\ell \geq 1$ . The goal is to decide whether there exists a sequence $\langle I_0, I_1, ..., I_\ell \rangle$ of independent sets such that for all $j \in \{0,\ldots,\ell-1\}$ the set $I_j$ is an independent set of size $k$ , $I_0 = S$ , $I_\ell = T$ , and $I_{j+1}$ is obtained from $I_j$ by a predetermined reconfiguration rule. We consider two reconfiguration rules. Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the Token Sliding Optimization (TSO) problem asks whether there exists a sequence of at most $\ell$ steps that transforms $S$ into $T$ , where at each step we are allowed to slide one token from a vertex to an unoccupied neighboring vertex. In the Token Jumping Optimization (TJO) problem, at each step, we are allowed to jump one token from a vertex to any other unoccupied vertex of the graph. Both TSO and TJO are known to be fixed-parameter tractable when parameterized by $\ell$ on nowhere dense classes of graphs. In this work, we show that both problems are fixed-parameter tractable for parameter $k + \ell + d$ on $d$ -degenerate graphs as well as for parameter $|M| + \ell + Δ$ on graphs having a modulator $M$ whose deletion leaves a graph of maximum degree $Δ$ . We complement these result by showing that for parameter $\ell$ alone both problems become W[1]-hard already on $2$ -degenerate graphs. Our positive result makes use of the notion of independence covering families introduced by Lokshtanov et al. Finally, we show that using such families one can obtain a simpler and unified algorithm for the standard Token Jumping Reachability problem parameterized by $k$ on both degenerate and nowhere dense classes of graphs.

preprint2022arXiv

Recognizing well-dominated graphs is coNP-complete

A graph $G$ is well-covered if every minimal vertex cover of $G$ is minimum, and a graph $G$ is well-dominated if every minimal dominating set of $G$ is minimum. Studies on well-covered graphs were initiated in [Plummer, JCT 1970], and well-dominated graphs were first introduced in [Finbow, Hartnell and Nowakow, AC 1988]. Well-dominated graphs are well-covered, and both classes have been widely studied in the literature. The recognition of well-covered graphs was proved coNP-complete by [Chvátal and Slater, AODM 1993] and by [Sankaranarayana and Stewart, Networks 1992], but the complexity of recognizing well-dominated graphs has been left open since their introduction. We close this complexity gap by proving that recognizing well-dominated graphs is coNP-complete. This solves a well-known open question (c.f. [Levit and Tankus, DM 2017] and [Gözüpek, Hujdurovic and Milanič, DMTCS 2017]), which was first asked in [Caro, Sebő and Tarsi, JAlg 1996]. Surprisingly, our proof is quite simple, although it was a long-standing open problem. Finally, we show that recognizing well-totally-dominated graphs is coNP-complete, answering a question of [Bahad\ir, Ekim, and Gözüpek, AMC 2021].

preprint2022arXiv

Recurrent Problems in the LOCAL model

The paper considers the SUPPORTED model of distributed computing introduced by Schmid and Suomela [HotSDN'13], generalizing the LOCAL and CONGEST models. In this framework, multiple instances of the same problem, differing from each other by the subnetwork to which they apply, recur over time, and need to be solved efficiently online. To do that, one may rely on an initial preprocessing phase for computing some useful information. This preprocessing phase makes it possible, in some cases, to overcome locality-based time lower bounds. A first contribution of the current paper is expanding the spectrum of problem types to which the SUPPORTED model applies. In addition to subnetwork-defined recurrent problems, we introduce also recurrent problems of two additional types: (i) instances defined by partial client sets, and (ii) instances defined by partially fixed outputs. Our second contribution is illustrating the versatility of the SUPPORTED framework by examining recurrent variants of three classical graph problems. The first problem is Minimum Client Dominating Set (CDS), a recurrent version of the classical dominating set problem with each recurrent instance requiring us to dominate a partial client set. We provide a constant time approximation scheme for CDS on trees and planar graphs. The second problem is Color Completion (CC), a recurrent version of the coloring problem in which each recurrent instance comes with a partially fixed coloring (of some of the vertices) that must be completed. We study the minimum number of new colors and the minimum total number of colors necessary for completing this task. The third problem we study is a recurrent version of Locally Checkable Labellings (LCL) on paths of length $n$ . We show that such problems have complexities that are either $Θ(1)$ or $Θ(n)$ , extending the results of Foerster et al. [INFOCOM'19].

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$.

preprint2020arXiv

The Parameterized Complexity of Guarding Almost Convex Polygons

Art Gallery is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of Art Gallery, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries were made: the above mentioned variants of Art Gallery are all W[1]-hard with respect to k [Bonnet and Miltzow, ESA'16], the classic variant has an O(log k)-approximation algorithm [Bonnet and Miltzow, SoCG'17], and it may require irrational guards [Abrahamsen et al., SoCG'17]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be \exists R-complete~[Abrahamsen et al., STOC'18]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP. Given the first discovery, the following question was posed by Giannopoulos [Lorentz Center Workshop, 2016]: Is Art Gallery FPT with respect to r, the number of reflex vertices? We focus on the variant where G and C are all the vertices of P, called Vertex-Vertex Art Gallery. We show that Vertex-Vertex Art Gallery is solvable in time r^{O(r^2)}n^{O(1)}. Our approach also extends to assert that Vertex-Boundary Art Gallery and Boundary-Vertex Art Gallery are both FPT. We utilize structural properties of "almost convex polygons" to present a two-stage reduction from Vertex-Vertex Art Gallery to a new constraint satisfaction problem (whose solution is also provided in this paper) where constraints have arity 2 and involve monotone functions.

preprint2016arXiv

Simultaneous Feedback Edge Set: A Parameterized Perspective

In this paper we consider Simultaneous Feedback Edge Set (Sim-FES) problem. In this problem, the input is an $n$ -vertex graph $G$ , an integer $k$ and a coloring function ${\sf col}: E(G) \rightarrow 2^{[α]}$ and the objective is to check whether there is an edge subset $S$ of cardinality at most $k$ in $G$ such that for all $i \in [α]$ , $G_i - S$ is acyclic. Here, $G_i=(V(G), \{e\in E(G) \mid i \in {\sf col}(e)\})$ and $[α]=\{1,\ldots,α\}$ . When $α=1$ , the problem is polynomial time solvable. We show that for $α=3$ Sim-FES is NP-hard by giving a reduction from Vertex Cover on cubic graphs. The same reduction shows that the problem does not admit an algorithm of running time $O(2^{o(k)}n^{O(1)})$ unless ETH fails. This hardness result is complimented by an FPT algorithm for Sim-FES running in time $O(2^{ωkα+α\log k} n^{O(1)})$ , where $ω$ is the exponent in the running time of matrix multiplication. The same algorithm gives a polynomial time algorithm for the case when $α=2$ . We also give a kernel for Sim-FES with $(kα)^{O(α)}$ vertices. Finally, we consider the problem Maximum Simultaneous Acyclic Subgraph. Here, the input is a graph $G$ , an integer $q$ and, a coloring function ${\sf col}: E(G) \rightarrow 2^{[α]}$ . The question is whether there is a edge subset $F$ of cardinality at least $q$ in $G$ such that for all $i\in [α]$ , $G[F_i]$ is acyclic. Here, $F_i=\{e \in F \mid i \in \textsf{col}(e)\}$ . We give an FPT algorithm for running in time $O(2^{ωq α}n^{O(1)})$ .

preprint2015arXiv

A faster FPT Algorithm and a smaller Kernel for Block Graph Vertex Deletion

A graph $G$ is called a \emph{block graph} if each maximal $2$ -connected component of $G$ is a clique. In this paper we study the Block Graph Vertex Deletion from the perspective of fixed parameter tractable (FPT) and kernelization algorithm. In particular, an input to Block Graph Vertex Deletion consists of a graph $G$ and a positive integer $k$ and the objective to check whether there exists a subset $S \subseteq V(G)$ of size at most $k$ such that the graph induced on $V(G)\setminus S$ is a block graph. In this paper we give an FPT algorithm with running time $4^kn^{O(1)}$ and a polynomial kernel of size $O(k^4)$ for Block Graph Vertex Deletion. The running time of our FPT algorithm improves over the previous best algorithm for the problem that ran in time $10^kn^{O(1)}$ and the size of our kernel reduces over the previously known kernel of size $O(k^9)$ . Our results are based on a novel connection between Block Graph Vertex Deletion and the classical {\sc Feedback Vertex Set} problem in graphs without induced $C_4$ and $K_4-e$ . To achieve our results we also obtain an algorithm for {\sc Weighted Feedback Vertex Set} running in time $3.618^kn^{O(1)}$ and improving over the running time of previously known algorithm with running time $5^kn^{O(1)}$ .

preprint2015arXiv

Simultaneous Feedback Vertex Set: A Parameterized Perspective

Given a family of graphs $\mathcal{F}$ , a graph $G$ , and a positive integer $k$ , the $\mathcal{F}$ -Deletion problem asks whether we can delete at most $k$ vertices from $G$ to obtain a graph in $\mathcal{F}$ . $\mathcal{F}$ -Deletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. A graph $G = (V, \cup_{i=1}^α E_{i})$ , where the edge set of $G$ is partitioned into $α$ color classes, is called an $α$ -edge-colored graph. A natural extension of the $\mathcal{F}$ -Deletion problem to edge-colored graphs is the $α$ -Simultaneous $\mathcal{F}$ -Deletion problem. In the latter problem, we are given an $α$ -edge-colored graph $G$ and the goal is to find a set $S$ of at most $k$ vertices such that each graph $G_i \setminus S$ , where $G_i = (V, E_i)$ and $1 \leq i \leq α$ , is in $\mathcal{F}$ . In this work, we study $α$ -Simultaneous $\mathcal{F}$ -Deletion for $\mathcal{F}$ being the family of forests. In other words, we focus on the $α$ -Simultaneous Feedback Vertex Set ( $α$ -SimFVS) problem. Algorithmically, we show that, like its classical counterpart, $α$ -SimFVS parameterized by $k$ is fixed-parameter tractable (FPT) and admits a polynomial kernel, for any fixed constant $α$ . In particular, we give an algorithm running in $2^{O(αk)}n^{O(1)}$ time and a kernel with $O(αk^{3(α+ 1)})$ vertices. The running time of our algorithm implies that $α$ -SimFVS is FPT even when $α\in o(\log n)$ . We complement this positive result by showing that for $α\in O(\log n)$ , where $n$ is the number of vertices in the input graph, $α$ -SimFVS becomes W[1]-hard. Our positive results answer one of the open problems posed by Cai and Ye (MFCS 2014).

preprint2014arXiv

Vertex Cover Gets Faster and Harder on Low Degree Graphs

The problem of finding an optimal vertex cover in a graph is a classic NP-complete problem, and is a special case of the hitting set question. On the other hand, the hitting set problem, when asked in the context of induced geometric objects, often turns out to be exactly the vertex cover problem on restricted classes of graphs. In this work we explore a particular instance of such a phenomenon. We consider the problem of hitting all axis-parallel slabs induced by a point set P, and show that it is equivalent to the problem of finding a vertex cover on a graph whose edge set is the union of two Hamiltonian Paths. We show the latter problem to be NP-complete, and we also give an algorithm to find a vertex cover of size at most k, on graphs of maximum degree four, whose running time is 1.2637^k n^O(1).

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.

Akanksha Agrawal

Research overview

Is this your work?

11 publications

A Polynomial Kernel for Proper Helly Circular-arc Vertex Deletion

Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent

On finding short reconfiguration sequences between independent sets

Recognizing well-dominated graphs is coNP-complete

Recurrent Problems in the LOCAL model

Parameterized Complexity of Maximum Edge Colorable Subgraph

The Parameterized Complexity of Guarding Almost Convex Polygons

Simultaneous Feedback Edge Set: A Parameterized Perspective

A faster FPT Algorithm and a smaller Kernel for Block Graph Vertex Deletion

Simultaneous Feedback Vertex Set: A Parameterized Perspective

Vertex Cover Gets Faster and Harder on Low Degree Graphs

See the researcher in context

Building this map preview