Source author record

Ana Karolinna Maia

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

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms math.CO Discrete Mathematics

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Adapting the Directed Grid Theorem into an FPT Algorithm

The Grid Theorem of Robertson and Seymour [JCTB, 1986], is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem in digraphs was conjectured by Johnson et al. [JCTB, 2001], and proved by Kawarabayashi and Kreutzer [STOC, 2015]. Namely, they showed that there is a function $f(k)$ such that every digraph of directed tree-width at least $f(k)$ contains a cylindrical grid of size $k$ as a butterfly minor and stated that their proof can be turned into an XP algorithm, with parameter $k$ , that either constructs a decomposition of the appropriate width, or finds the claimed large cylindrical grid as a butterfly minor. In this paper, we adapt some of the steps of the proof of Kawarabayashi and Kreutzer to improve this XP algorithm into an FPT algorithm. Towards this, our main technical contributions are two FPT algorithms with parameter $k$ . The first one either produces an arboreal decomposition of width $3k-2$ or finds a haven of order $k$ in a digraph $D$ , improving on the original result for arboreal decompositions by Johnson et al. The second algorithm finds a well-linked set of order $k$ in a digraph $D$ of large directed tree-width. As tools to prove these results, we show how to solve a generalized version of the problem of finding balanced separators for a given set of vertices $T$ in FPT time with parameter $|T|$ , a result that we consider to be of its own interest.

preprint2020arXiv

Target set selection with maximum activation time

A target set selection model is a graph $G$ with a threshold function $τ:V\to \mathbb{N}$ upper-bounded by the vertex degree. For a given model, a set $S_0\subseteq V(G)$ is a target set if $V(G)$ can be partitioned into non-empty subsets $S_0,S_1,\dotsc,S_t$ such that, for $i \in \{1, \ldots, t\}$ , $S_i$ contains exactly every vertex $v$ having at least $τ(v)$ neighbors in $S_0\cup\dots\cup S_{i-1}$ . We say that $t$ is the activation time $t_τ(S_0)$ of the target set $S_0$ . The problem of, given such a model, finding a target set of minimum size has been extensively studied in the literature. In this article, we investigate its variant, which we call TSS-time, in which the goal is to find a target set $S_0$ that maximizes $t_τ(S_0)$ . That is, given a graph $G$ , a threshold function $τ$ in $G$ , and an integer $k$ , the objective of the TSS-time problem is to decide whether $G$ contains a target set $S_0$ such that $t_τ(S_0)\geq k$ . Let $τ^* = \max_{v \in V(G)} τ(v)$ . Our main result is the following dichotomy about the complexity of TSS-time when $G$ belongs to a minor-closed graph class ${\cal C}$ : if ${\cal C}$ has bounded local treewidth, the problem is FPT parameterized by $k$ and $τ^{\star}$ ; otherwise, it is NP-complete even for fixed $k=4$ and $τ^{\star}=2$ . We also prove that, with $τ^*=2$ , the problem is NP-hard in bipartite graphs for fixed $k=5$ , and from previous results we observe that TSS-time is NP-hard in planar graphs and W[1]-hard parameterized by treewidth. Finally, we present a linear-time algorithm to find a target set $S_0$ in a given tree maximizing $t_τ(S_0)$ .

preprint2011arXiv

Fixed parameter algorithms for restricted coloring problems

In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number, the Thue chromatic number, the harmonious chromatic number and the clique chromatic number of $P_4$ -tidy graphs and $(q,q-4)$ -graphs, for every fixed $q$ . These classes include cographs, $P_4$ -sparse and $P_4$ -lite graphs. All these coloring problems are known to be NP-hard for general graphs. These algorithms are fixed parameter tractable on the parameter $q(G)$ , which is the minimum $q$ such that $G$ is a $(q,q-4)$ -graph. We also prove that every connected $(q,q-4)$ -graph with at least $q$ vertices is 2-clique-colorable and that every acyclic coloring of a cograph is also nonrepetitive.

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.