BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Ignasi Sau

Ignasi Sau contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational ComplexityData Structures and Algorithmsmath.CO

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
7works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

7 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Hitting forbidden induced subgraphs on bounded treewidth graphs

For a fixed graph $H$, the $H$-IS-Deletion problem asks, given a graph $G$, for the minimum size of a set $S \subseteq V(G)$ such that $G\setminus S$ does not contain $H$ as an induced subgraph. Motivated by previous work about hitting (topological) minors and subgraphs on bounded treewidth graphs, we are interested in determining, for a fixed graph $H$, the smallest function $f_H(t)$ such that $H$-IS-Deletion can be solved in time $f_H(t) \cdot n^{O(1)}$ assuming the Exponential Time Hypothesis (ETH), where $t$ and $n$ denote the treewidth and the number of vertices of the input graph, respectively. We show that $f_H(t) = 2^{O(t^{h-2})}$ for every graph $H$ on $h \geq 3$ vertices, and that $f_H(t) = 2^{O(t)}$ if $H$ is a clique or an independent set. We present a number of lower bounds by generalizing a reduction of Cygan et al. [MFCS 2014] for the subgraph version. In particular, we show that when $H$ deviates slightly from a clique, the function $f_H(t)$ suffers a sharp jump: if $H$ is obtained from a clique of size $h$ by removing one edge, then $f_H(t) = 2^{Θ(t^{h-2})}$. We also show that $f_H(t) = 2^{Ω(t^{h})}$ when $H=K_{h,h}$, and this reduction answers an open question of Mi. Pilipczuk [MFCS 2011] about the function $f_{C_4}(t)$ for the subgraph version. Motivated by Cygan et al. [MFCS 2014], we also consider the colorful variant of the problem, where each vertex of $G$ is colored with some color from $V(H)$ and we require to hit only induced copies of $H$ with matching colors. In this case, we determine, under the ETH, the function $f_H(t)$ for every connected graph $H$ on $h$ vertices: if $h\leq 2$ the problem can be solved in polynomial time; if $h\geq 3$, $f_H(t) = 2^{Θ(t)}$ if $H$ is a clique, and $f_H(t) = 2^{Θ(t^{h-2})}$ otherwise.

0 citations0 reviewsNo code linkedOpen access
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$).

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

k-apices of minor-closed graph classes. II. Parameterized algorithms

Let ${\cal G}$ be a minor-closed graph class. We say that a graph $G$ is a $k$-apex of ${\cal G}$ if $G$ contains a set $S$ of at most $k$ vertices such that $G\setminus S$ belongs to ${\cal G}$. We denote by ${\cal A}_k ({\cal G})$ the set of all graphs that are $k$-apices of ${\cal G}.$ In the first paper of this series we obtained upper bounds on the size of the graphs in the minor-obstruction set of ${\cal A}_k ({\cal G})$, i.e., the minor-minimal set of graphs not belonging to ${\cal A}_k ({\cal G}).$ In this article we provide an algorithm that, given a graph $G$ on $n$ vertices, runs in $2^{{\sf poly}(k)}\cdot n^3$-time and either returns a set $S$ certifying that $G \in {\cal A}_k ({\cal G})$, or reports that $G \notin {\cal A}_k ({\cal G})$. Here ${\sf poly}$ is a polynomial function whose degree depends on the maximum size of a minor-obstruction of ${\cal G}.$ In the special case where ${\cal G}$ excludes some apex graph as a minor, we give an alternative algorithm running in $2^{{\sf poly}(k)}\cdot n^2$-time.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Parameterized complexity of computing maximum minimal blocking and hitting sets

A blocking set in a graph $G$ is a subset of vertices that intersects every maximum independent set of $G$. Let ${\sf mmbs}(G)$ be the size of a maximum (inclusion-wise) minimal blocking set of $G$. This parameter has recently played an important role in the kernelization of Vertex Cover parameterized by the distance to a graph class ${\cal F}$. Indeed, it turns out that the existence of a polynomial kernel for this problem is closely related to the property that ${\sf mmbs}({\cal F})=\sup_{G \in {\cal F}}{\sf mmbs}(G)$ is bounded by a constant, and thus several recent results focused on determining ${\sf mmbs}({\cal F})$ for different classes ${\cal F}$. We consider the parameterized complexity of computing ${\sf mmbs}$ under various parameterizations, such as the size of a maximum independent set of the input graph and the natural parameter. We provide a panorama of the complexity of computing both ${\sf mmbs}$ and ${\sf mmhs}$, which is the size of a maximum minimal hitting set of a hypergraph, a closely related parameter. Finally, we consider the problem of computing ${\sf mmbs}$ parameterized by treewidth, especially relevant in the context of kernelization. Given the "counting" nature of ${\sf mmbs}$, it does not seem to be expressible in monadic second-order logic, hence its tractability does not follow from Courcelle's theorem. Our main technical contribution is a fixed-parameter tractable algorithm for this problem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Unifying Model for Locally Constrained Spanning Tree Problems

Given a graph $G$ and a digraph $D$ whose vertices are the edges of $G$, we investigate the problem of finding a spanning tree of $G$ that satisfies the constraints imposed by $D$. The restrictions to add an edge in the tree depend on its neighborhood in $D$. Here, we generalize previously investigated problems by also considering as input functions $\ell$ and $u$ on $E(G)$ that give a lower and an upper bound, respectively, on the number of constraints that must be satisfied by each edge. The produced feasibility problem is denoted by \texttt{G-DCST}, while the optimization problem is denoted by \texttt{G-DCMST}. We show that \texttt{G-DCST} is NP-complete even under strong assumptions on the structures of $G$ and $D$, as well as on functions $\ell$ and $u$. On the positive side, we prove two polynomial results, one for \texttt{G-DCST} and another for \texttt{G-DCMST}, and also give a simple exponential-time algorithm along with a proof that it is asymptotically optimal under the Ð. Finally, we prove that other previously studied constrained spanning tree (\textsc{CST}) problems can be modeled within our framework, namely, the \textsc{Conflict CST}, the \textsc{Forcing CS, the \textsc{At Least One/All Dependency CST}, the \textsc{Maximum Degree CST}, the \textsc{Minimum Degree CST}, and the \textsc{Fixed-Leaves Minimum Degree CST}.

0 citations0 reviewsNo code linkedOpen access
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)$.

0 citations0 reviewsNo code linkedOpen access