BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ignasi Sau

Ignasi Sau appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and Algorithmsmath.CODiscrete MathematicsComputational Complexity

Catalog footprint

What is connected

26works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

26 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
preprint2016arXiv

Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees

In phylogenetics, a central problem is to infer the evolutionary relationships between a set of species $X$; these relationships are often depicted via a phylogenetic tree -- a tree having its leaves univocally labeled by elements of $X$ and without degree-2 nodes -- called the "species tree". One common approach for reconstructing a species tree consists in first constructing several phylogenetic trees from primary data (e.g. DNA sequences originating from some species in $X$), and then constructing a single phylogenetic tree maximizing the "concordance" with the input trees. The so-obtained tree is our estimation of the species tree and, when the input trees are defined on overlapping -- but not identical -- sets of labels, is called "supertree". In this paper, we focus on two problems that are central when combining phylogenetic trees into a supertree: the compatibility and the strict compatibility problems for unrooted phylogenetic trees. These problems are strongly related, respectively, to the notions of "containing as a minor" and "containing as a topological minor" in the graph community. Both problems are known to be fixed-parameter tractable in the number of input trees $k$, by using their expressibility in Monadic Second Order Logic and a reduction to graphs of bounded treewidth. Motivated by the fact that the dependency on $k$ of these algorithms is prohibitively large, we give the first explicit dynamic programming algorithms for solving these problems, both running in time $2^{O(k^2)} \cdot n$, where $n$ is the total size of the input.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Explicit linear kernels for packing problems

During the last years, several algorithmic meta-theorems have appeared (Bodlaender et al. [FOCS 2009], Fomin et al. [SODA 2010], Kim et al. [ICALP 2013]) guaranteeing the existence of linear kernels on sparse graphs for problems satisfying some generic conditions. The drawback of such general results is that it is usually not clear how to derive from them constructive kernels with reasonably low explicit constants. To fill this gap, we recently presented [STACS 2014] a framework to obtain explicit linear kernels for some families of problems whose solutions can be certified by a subset of vertices. In this article we enhance our framework to deal with packing problems, that is, problems whose solutions can be certified by collections of subgraphs of the input graph satisfying certain properties. ${\mathcal F}$-Packing is a typical example: for a family ${\mathcal F}$ of connected graphs that we assume to contain at least one planar graph, the task is to decide whether a graph $G$ contains $k$ vertex-disjoint subgraphs such that each of them contains a graph in ${\mathcal F}$ as a minor. We provide explicit linear kernels on sparse graphs for the following two orthogonal generalizations of ${\mathcal F}$-Packing: for an integer $\ell \geq 1$, one aims at finding either minor-models that are pairwise at distance at least $\ell$ in $G$ ($\ell$-${\mathcal F}$-Packing), or such that each vertex in $G$ belongs to at most $\ell$ minors-models (${\mathcal F}$-Packing with $\ell$-Membership). Finally, we also provide linear kernels for the versions of these problems where one wants to pack subgraphs instead of minors.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the complexity of computing the $k$-restricted edge-connectivity of a graph

The \emph{$k$-restricted edge-connectivity} of a graph $G$, denoted by $λ_k(G)$, is defined as the minimum size of an edge set whose removal leaves exactly two connected components each containing at least $k$ vertices. This graph invariant, which can be seen as a generalization of a minimum edge-cut, has been extensively studied from a combinatorial point of view. However, very little is known about the complexity of computing $λ_k(G)$. Very recently, in the parameterized complexity community the notion of \emph{good edge separation} of a graph has been defined, which happens to be essentially the same as the $k$-restricted edge-connectivity. Motivated by the relevance of this invariant from both combinatorial and algorithmic points of view, in this article we initiate a systematic study of its computational complexity, with special emphasis on its parameterized complexity for several choices of the parameters. We provide a number of NP-hardness and W[1]-hardness results, as well as FPT-algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Parameterized complexity dichotomy for $(r,\ell)$-Vertex Deletion

For two integers $r, \ell \geq 0$, a graph $G = (V, E)$ is an $(r,\ell)$-graph if $V$ can be partitioned into $r$ independent sets and $\ell$ cliques. In the parameterized $(r,\ell)$-Vertex Deletion problem, given a graph $G$ and an integer $k$, one has to decide whether at most $k$ vertices can be removed from $G$ to obtain an $(r,\ell)$-graph. This problem is NP-hard if $r+\ell \geq 1$ and encompasses several relevant problems such as Vertex Cover and Odd Cycle Transversal. The parameterized complexity of $(r,\ell)$-Vertex Deletion was known for all values of $(r,\ell)$ except for $(2,1)$, $(1,2)$, and $(2,2)$. We prove that each of these three cases is FPT and, furthermore, solvable in single-exponential time, which is asymptotically optimal in terms of $k$. We consider as well the version of $(r,\ell)$-Vertex Deletion where the set of vertices to be removed has to induce an independent set, and provide also a parameterized complexity dichotomy for this problem.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Parameterized complexity of the MINCCA problem on graphs of bounded decomposability

In an edge-colored graph, the cost incurred at a vertex on a path when two incident edges with different colors are traversed is called reload or changeover cost. The "Minimum Changeover Cost Arborescence" (MINCCA) problem consists in finding an arborescence with a given root vertex such that the total changeover cost of the internal vertices is minimized. It has been recently proved by Gözüpek et al. [TCS 2016] that the problem is FPT when parameterized by the treewidth and the maximum degree of the input graph. In this article we present the following results for the MINCCA problem: - the problem is W[1]-hard parameterized by the treedepth of the input graph, even on graphs of average degree at most 8. In particular, it is W[1]-hard parameterized by the treewidth of the input graph, which answers the main open problem of Gözüpek et al. [TCS 2016]; - it is W[1]-hard on multigraphs parameterized by the tree-cutwidth of the input multigraph; - it is FPT parameterized by the star tree-cutwidth of the input graph, which is a slightly restricted version of tree-cutwidth. This result strictly generalizes the FPT result given in Gözüpek et al. [TCS 2016]; - it remains NP-hard on planar graphs even when restricted to instances with at most 6 colors and 0/1 symmetric costs, or when restricted to instances with at most 8 colors, maximum degree bounded by 4, and 0/1 symmetric costs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The number of labeled graphs of bounded treewidth

We focus on counting the number of labeled graphs on $n$ vertices and treewidth at most $k$ (or equivalently, the number of labeled partial $k$-trees), which we denote by $T_{n,k}$. So far, only the particular cases $T_{n,1}$ and $T_{n,2}$ had been studied. We show that $$ \left(c \cdot \frac{k\cdot 2^k \cdot n}{\log k} \right)^n \cdot 2^{-\frac{k(k+3)}{2}} \cdot k^{-2k-2}\ \leq\ T_{n,k}\ \leq\ \left(k \cdot 2^k \cdot n\right)^n \cdot 2^{-\frac{k(k+1)}{2}} \cdot k^{-k}, $$ for $k > 1$ and some explicit absolute constant $c > 0$. The upper bound is an immediate consequence of the well-known number of labeled $k$-trees, while the lower bound is obtained from an explicit algorithmic construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most $k$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Uniquely restricted matchings and edge colorings

A matching in a graph is uniquely restricted if no other matching covers exactly the same set of vertices. This notion was defined by Golumbic, Hirst, and Lewenstein and studied in a number of articles. Our contribution is twofold. We provide approximation algorithms for computing a uniquely restricted matching of maximum size in some bipartite graphs. In particular, we achieve a ratio of $9/5$ for subcubic bipartite graphs, improving over a $2$-approximation algorithm proposed by Mishra. Furthermore, we study the uniquely restricted chromatic index of a graph, defined as the minimum number of uniquely restricted matchings into which its edge set can be partitioned. We provide tight upper bounds in terms of the maximum degree and characterize all extremal graphs. Our constructive proofs yield efficient algorithms to determine the corresponding edge colorings.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An edge variant of the Erdős-Pósa property

For every $r\in \mathbb{N}$, we denote by $θ_{r}$ the multigraph with two vertices and $r$ parallel edges. Given a graph $G$, we say that a subgraph $H$ of $G$ is a model of $θ_{r}$ in $G$ if $H$ contains $θ_{r}$ as a contraction. We prove that the following edge variant of the Erd{\H o}s-P{ó}sa property holds for every $r\geq 2$: if $G$ is a graph and $k$ is a positive integer, then either $G$ contains a packing of $k$ mutually edge-disjoint models of $θ_{r}$, or it contains a set $S$ of $f_r(k)$ edges such that $G\setminus S$ has no $θ_{r}$-model, for both $f_r(k) = O(k^2r^3 \mathrm{polylog}~kr)$ and $f_r(k) = O(k^4r^2 \mathrm{polylog}~kr).$

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Parameterized Algorithms for Min-Max Multiway Cut and List Digraph Homomorphism

In this paper we design {\sf FPT}-algorithms for two parameterized problems. The first is \textsc{List Digraph Homomorphism}: given two digraphs $G$ and $H$ and a list of allowed vertices of $H$ for every vertex of $G$, the question is whether there exists a homomorphism from $G$ to $H$ respecting the list constraints. The second problem is a variant of \textsc{Multiway Cut}, namely \textsc{Min-Max Multiway Cut}: given a graph $G$, a non-negative integer $\ell$, and a set $T$ of $r$ terminals, the question is whether we can partition the vertices of $G$ into $r$ parts such that (a) each part contains one terminal and (b) there are at most $\ell$ edges with only one endpoint in this part. We parameterize \textsc{List Digraph Homomorphism} by the number $w$ of edges of $G$ that are mapped to non-loop edges of $H$ and we give a time $2^{O(\ell\cdot\log h+\ell^2\cdot \log \ell)}\cdot n^{4}\cdot \log n$ algorithm, where $h$ is the order of the host graph $H$. We also prove that \textsc{Min-Max Multiway Cut} can be solved in time $2^{O((\ell r)^2\log \ell r)}\cdot n^{4}\cdot \log n$. Our approach introduces a general problem, called {\sc List Allocation}, whose expressive power permits the design of parameterized reductions of both aforementioned problems to it. Then our results are based on an {\sf FPT}-algorithm for the {\sc List Allocation} problem that is designed using a suitable adaptation of the {\em randomized contractions} technique (introduced by [Chitnis, Cygan, Hajiaghayi, Pilipczuk, and Pilipczuk, FOCS 2012]).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Polynomial-time Algorithm for Outerplanar Diameter Improvement

The Outerplanar Diameter Improvement problem asks, given a graph $G$ and an integer $D$, whether it is possible to add edges to $G$ in a way that the resulting graph is outerplanar and has diameter at most $D$. We provide a dynamic programming algorithm that solves this problem in polynomial time. Outerplanar Diameter Improvement demonstrates several structural analogues to the celebrated and challenging Planar Diameter Improvement problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Explicit linear kernels via dynamic programming

Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of Bodlaender et al. [FOCS 2009] on graphs of bounded genus, then generalized by Fomin et al. [SODA 2010] to graphs excluding a fixed minor, and by Kim et al. [ICALP 2013] to graphs excluding a fixed topological minor. Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants. In this paper we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in CMSO logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for $r$-Dominating Set and $r$-Scattered Set on apex-minor-free graphs, and for Planar-\mathcal{F}-Deletion on graphs excluding a fixed (topological) minor in the case where all the graphs in \mathcal{F} are connected.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Improved FPT algorithms for weighted independent set in bull-free graphs

Very recently, Thomassé, Trotignon and Vuskovic [WG 2014] have given an FPT algorithm for Weighted Independent Set in bull-free graphs parameterized by the weight of the solution, running in time $2^{O(k^5)} \cdot n^9$. In this article we improve this running time to $2^{O(k^2)} \cdot n^7$. As a byproduct, we also improve the previous Turing-kernel for this problem from $O(k^5)$ to $O(k^2)$. Furthermore, for the subclass of bull-free graphs without holes of length at most $2p-1$ for $p \geq 3$, we speed up the running time to $2^{O(k \cdot k^{\frac{1}{p-1}})} \cdot n^7$. As $p$ grows, this running time is asymptotically tight in terms of $k$, since we prove that for each integer $p \geq 3$, Weighted Independent Set cannot be solved in time $2^{o(k)} \cdot n^{O(1)}$ in the class of $\{bull,C_4,\ldots,C_{2p-1}\}$-free graphs unless the ETH fails.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Hitting and Harvesting Pumpkins

The "c-pumpkin" is the graph with two vertices linked by c>0 parallel edges. A c-pumpkin-model in a graph G is a pair A,B of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on covering and packing c-pumpkin-models in a given graph: On the one hand, we provide an FPT algorithm running in time 2^O(k) n^O(1) deciding, for any fixed c>0, whether all c-pumpkin-models can be covered by at most k vertices. This generalizes known single-exponential FPT algorithms for Vertex Cover and Feedback Vertex Set, which correspond to the cases c=1,2 respectively. On the other hand, we present a O(log n)-approximation algorithm for both the problems of covering all c-pumpkin-models with a smallest number of vertices, and packing a maximum number of vertex-disjoint c-pumpkin-models.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The role of planarity in connectivity problems parameterized by treewidth

For some years it was believed that for "connectivity" problems such as Hamiltonian Cycle, algorithms running in time 2^{O(tw)}n^{O(1)} -called single-exponential- existed only on planar and other sparse graph classes, where tw stands for the treewidth of the n-vertex input graph. This was recently disproved by Cygan et al. [FOCS 2011], Bodlaender et al. [ICALP 2013], and Fomin et al. [SODA 2014], who provided single-exponential algorithms on general graphs for essentially all connectivity problems that were known to be solvable in single-exponential time on sparse graphs. In this article we further investigate the role of planarity in connectivity problems parameterized by treewidth, and convey that several problems can indeed be distinguished according to their behavior on planar graphs. Known results from the literature imply that there exist problems, like Cycle Packing, that cannot be solved in time 2^{o(tw logtw)}n^{O(1)} on general graphs but that can be solved in time 2^{O(tw)}n^{O(1)} when restricted to planar graphs. Our main contribution is to show that there exist problems that can be solved in time 2^{O(tw logtw)}n^{O(1)} on general graphs but that cannot be solved in time 2^{o(tw logtw)}n^{O(1)} even when restricted to planar graphs. Furthermore, we prove that Planar Cycle Packing and Planar Disjoint Paths cannot be solved in time 2^{o(tw)}n^{O(1)}. The mentioned negative results hold unless the ETH fails. We feel that our results constitute a first step in a subject that can be further exploited.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Linear kernels and single-exponential algorithms via protrusion decompositions

A \emph{$t$-treewidth-modulator} of a graph $G$ is a set $X \subseteq V(G)$ such that the treewidth of $G-X$ is at most some constant $t-1$. In this paper, we present a novel algorithm to compute a decomposition scheme for graphs $G$ that come equipped with a $t$-treewidth-modulator. This decomposition, called a \emph{protrusion decomposition}, is the cornerstone in obtaining the following two main results. We first show that any parameterized graph problem (with parameter $k$) that has \emph{finite integer index} and is \emph{treewidth-bounding} admits a linear kernel on $H$-topological-minor-free graphs, where $H$ is some arbitrary but fixed graph. A parameterized graph problem is called treewidth-bounding if all positive instances have a $t$-treewidth-modulator of size $O(k)$, for some constant $t$. This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus [Bodlaender et al., FOCS 2009] and $H$-minor-free graphs [Fomin et al., SODA 2010]. Our second application concerns the Planar-$\mathcal{F}$-Deletion problem. Let $\mathcal{F}$ be a fixed finite family of graphs containing at least one planar graph. Given an $n$-vertex graph $G$ and a non-negative integer $k$, Planar-$\mathcal{F}$-Deletion asks whether $G$ has a set $X\subseteq V(G)$ such that $|X|\leq k$ and $G-X$ is $H$-minor-free for every $H\in \mathcal{F}$. Very recently, an algorithm for Planar-$\mathcal{F}$-Deletion with running time $2^{O(k)} n \log^2 n$ (such an algorithm is called \emph{single-exponential}) has been presented in [Fomin et al., FOCS 2012] under the condition that every graph in $\mathcal{F}$ is connected. Using our algorithm to construct protrusion decompositions as a building block, we get rid of this connectivity constraint and present an algorithm for the general Planar-$\mathcal{F}$-Deletion problem running in time $2^{O(k)} n^2$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Parameterized Domination in Circle Graphs

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Applied Mathematics, 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction: - Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution. - Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs. - If T is a given tree, deciding whether a circle graph has a dominating set isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by |V(T)|. We prove that the FPT algorithm is subexponential.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Asymptotic Enumeration of Non-crossing Partitions on Surfaces

We generalize the notion of non-crossing partition on a disk to general surfaces with boundary. For this, we consider a surface $Σ$ and introduce the number $C_Σ(n)$ of non-crossing partitions of a set of $n$ points laying on the boundary of $Σ$. Our proofs use bijective techniques arising from map enumeration, joint with the symbolic method and singularity analysis on generating functions. An outcome of our results is that the exponential growth of $C_Σ(n)$ is the same as the one of the $n$-th Catalan number, i.e., does not change when we move from the case where $Σ$ is a disk to general surfaces with boundary.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Dynamic Programming for Graphs on Surfaces

We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of problems where standard dynamic programming runs in 2^{O(k log k)} n steps. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called "surface cut decomposition", generalizing sphere cut decompositions of planar graphs introduced by Seymour and Thomas, which has nice combinatorial properties. Namely, the number of partial solutions that can be arranged on a surface cut decomposition can be upper-bounded by the number of non-crossing partitions on surfaces with boundary. It follows that partial solutions can be represented by a single-exponential (in the branchwidth k) number of configurations. This proves that, when applied on surface cut decompositions, dynamic programming runs in 2^{O(k)} n steps. That way, we considerably extend the class of problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improve most previous results in this direction.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Recognition of Tolerance and Bounded Tolerance Graphs

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its numerous applications. Several efficient algorithms for optimization problems that are NP-hard on general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs - namely, the problem of deciding whether a given graph is a tolerance graph - as well as the recognition of their main subclass of bounded tolerance graphs, have been the most fundamental open problems on this class of graphs (cf. the book on tolerance graphs \cite{GolTol04}) since their introduction in 1982 \cite{GoMo82}. In this article we prove that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. The presented results are surprising because, on the one hand, most subclasses of perfect graphs admit polynomial recognition algorithms and, on the other hand, bounded tolerance graphs were believed to be efficiently recognizable as they are a natural special case of trapezoid graphs (which can be recognized in polynomial time) and share a very similar structure with them. For our reduction we extend the notion of an \emph{acyclic orientation} of permutation and trapezoid graphs. Our main tool is a new algorithm that uses \emph{vertex splitting} to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it has been proved a powerful tool also in the design of efficient recognition algorithms for other classes of graphs \cite{MC-Trapezoid}.

0 citations0 reviewsNo code linkedOpen access