Search

Given a graph $G$, we define ${\bf bcg}(G)$ as the minimum $k$ for which $G$ can be contracted to the uniformly triangulated grid $\Gamma_{k}$. A graph class ${\cal G}$ has the SQG${\bf C}$ property if every graph $G\in{\cal G}$ has treewidth $\mathcal{O}({\bf bcg}(G)^{c})$ for some $1\leq c<2$. The SQG${\bf C}$ property is important for algorithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a wide family of graph classes that satisfy the SQG${\bf C}$ property. This family includes, in particular, bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for contraction bidimensional problems.

For a finite collection of graphs ${\cal F}$, the ${\cal F}$-M-DELETION problem consists in, given a graph $G$ and an integer $k$, decide whether there exists $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus S$ does not contain any of the graphs in ${\cal F}$ as a minor. We are interested in the parameterized complexity of ${\cal F}$-M-DELETION when the parameter is the treewidth of $G$, denoted by $tw$. Our objective is to determine, for a fixed ${\cal F}$, the smallest function $f_{{\cal F}}$ such that ${\cal F}$-M-DELETION can be solved in time $f_{{\cal F}}(tw) \cdot n^{O(1)}$ on $n$-vertex graphs. We provide lower bounds under the ETH on $f_{{\cal F}}$ for several collections ${\cal F}$. We first prove that for any ${\cal F}$ containing connected graphs of size at least two, $f_{{\cal F}}(tw)= 2^{\Omega(tw)}$, even if the input graph $G$ is planar. Our main contribution consists of superexponential lower bounds for a number of collections ${\cal F}$, inspired by a reduction of Bonnet et al.~[IPEC, 2017]. In particular, we prove that when ${\cal F}$ contains a single connected graph $H$ that is either $P_5$ or is not a minor of the banner (that is, the graph consisting of a $C_4$ plus a pendent edge), then $f_{{\cal F}}(tw)= 2^{\Omega(tw \cdot \log tw)}$. This is the third of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of $\{H\}$-M-DELETION, in terms of $H$, when $H$ is connected., Comment: 41 pages, 20 figures. arXiv admin note: substantial text overlap with arXiv:1907.04442, arXiv:1704.07284

For a finite collection of graphs ${\cal F}$, the ${\cal F}$-M-DELETION (resp. ${\cal F}$-TM-DELETION) problem consists in, given a graph $G$ and an integer $k$, decide whether there exists $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus S$ does not contain any of the graphs in ${\cal F}$ as a minor (resp. topological minor). We are interested in the parameterized complexity of both problems when the parameter is the treewidth of $G$, denoted by $tw$, and specifically in the cases where ${\cal F}$ contains a single connected planar graph $H$. We present algorithms running in time $2^{O(tw)} \cdot n^{O(1)}$, called single-exponential, when $H$ is either $P_3$, $P_4$, $C_4$, the paw, the chair, and the banner for both $\{H\}$-M-DELETION and $\{H\}$-TM-DELETION, and when $H=K_{1,i}$, with $i \geq 1$, for $\{H\}$-TM-DELETION. Some of these algorithms use the rank-based approach introduced by Bodlaender et al. [Inform Comput, 2015]. This is the second of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of $\{H\}$-M-DELETION in terms of $H$., Comment: 36 pages, 2 figures

For a fixed finite collection of graphs ${\cal F}$, the ${\cal F}$-M-DELETION problem asks, given an $n$-vertex input graph $G,$ for the minimum number of vertices that intersect all minor models in $G$ of the graphs in ${\cal F}$. by Courcelle Theorem, this problem can be solved in time $f_{{\cal F}}(tw)\cdot n^{O(1)},$ where $tw$ is the treewidth of $G$, for some function $f_{{\cal F}}$ depending on ${\cal F}$ In a recent series of articles, we have initiated the programme of optimizing asymptotically the function $f_{{\cal F}}$. Here we provide an algorithm showing that $f_{{\cal F}}(tw) = 2^{O(tw\cdot \log tw)}$ for every collection ${\cal F}$. Prior to this work, the best known function $f_{{\cal F}}$ was double-exponential in $tw$. In particular, our algorithm vastly extends the results of Jansen et al. [SODA 2014] for the particular case ${\cal F}=\{K_5,K_{3,3}\}$ and of Kociumaka and Pilipczuk [Algorithmica 2019] for graphs of bounded genus, and answers an open problem posed by Cygan et al. [Inf Comput 2017]. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, Bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. Together with our previous results providing single-exponential algorithms for particular collections ${\cal F}$ [Theor Comput Sci 2020] and general lower bounds [J Comput Syst Sci 2020], our algorithm yields the following complexity dichotomy when ${\cal F} = \{H\}$ contains a single connected graph $H,$ assuming the Exponential Time Hypothesis: $f_H(tw)=2^{\Theta(tw)}$ if $H$ is a contraction of the chair or the banner, and $f_H(tw)=2^{\Theta(tw\cdot \log tw)}$ otherwise., Comment: 51 pages, 17 figures

The concept of Reload cost in a graph refers to the cost that occurs while traversing a vertex via two of its incident edges. This cost is uniquely determined by the colors of the two edges. This concept has various applications in transportation networks, communication networks, and energy distribution networks. Various problems using this model are defined and studied in the literature. The problem of finding a spanning tree whose diameter with respect to the reload costs is the smallest possible, the problems of finding a path, trail or walk with minimum total reload cost between two given vertices, problems about finding a proper edge coloring of a graph such that the total reload cost is minimized, the problem of finding a spanning tree such that the sum of the reload costs of all paths between all pairs of vertices is minimized, and the problem of finding a set of cycles of minimum reload cost, that cover all the vertices of a graph, are examples of such problems. % In this work we focus on the last problem. Noting that a cycle cover of a graph is a 2-factor of it, we generalize the problem to that of finding an $r$-factor of minimum reload cost of an edge colored graph. We prove several NP-hardness results for special cases of the problem. Namely, bounded degree graphs, planar graphs, bounded total cost, and bounded number of distinct costs. For the special case of $r=2$, our results imply an improved NP-hardness result. On the positive side, we present a polynomial-time solvable special case which provides a tight boundary between the polynomial and hard cases in terms of $r$ and the maximum degree of the graph. We then investigate the parameterized complexity of the problem, prove W[1]-hardness results and present an FPT algorithm.

For a finite collection of graphs ${\cal F}$, the ${\cal F}$-M-DELETION problem consists in, given a graph $G$ and an integer $k$, deciding whether there exists $S \subseteq V(G)$ with $|S| \leq k$ such that $G \setminus S$ does not contain any of the graphs in ${\cal F}$ as a minor. We are interested in the parameterized complexity of ${\cal F}$-M-DELETION when the parameter is the treewidth of $G$, denoted by $tw$. Our objective is to determine, for a fixed ${\cal F}$, the smallest function $f_{{\cal F}}$ such that {${\cal F}$-M-DELETION can be solved in time $f_{{\cal F}}(tw) \cdot n^{O(1)}$ on $n$-vertex graphs. We prove that $f_{{\cal F}}(tw) = 2^{2^{O(tw \cdot\log tw)}}$ for every collection ${\cal F}$, that $f_{{\cal F}}(tw) = 2^{O(tw \cdot\log tw)}$ if ${\cal F}$ contains a planar graph, and that $f_{{\cal F}}(tw) = 2^{O(tw)}$ if in addition the input graph $G$ is planar or embedded in a surface. We also consider the version of the problem where the graphs in ${\cal F}$ are forbidden as topological minors, called ${\cal F}$-TM-DELETION. We prove similar results for this problem, except that in the last two algorithms, instead of requiring ${\cal F}$ to contain a planar graph, we need it to contain a subcubic planar graph. This is the first of a series of articles on this topic., Comment: 36 pages

Given a graph $G$, a proper $k$-coloring of $G$ is a partition $c = (S_i)_{i\in [1,k]}$ of $V(G)$ into $k$ stable sets $S_1,\ldots, S_{k}$. Given a weight function $w: V(G) \to \mathbb{R}^+$, the weight of a color $S_i$ is defined as $w(i) = \max_{v \in S_i} w(v)$ and the weight of a coloring $c$ as $w(c) = \sum_{i=1}^{k}w(i)$. Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair $(G,w)$, denoted by $\sigma(G,w)$, as the minimum weight of a proper coloring of $G$. For a positive integer $r$, they also defined $\sigma(G,w;r)$ as the minimum of $w(c)$ among all proper $r$-colorings $c$ of $G$. The complexity of determining $\sigma(G,w)$ when $G$ is a tree was open for almost 20 years, until Ara\'ujo et al. [SIAM J. Discrete Math., 2014] recently proved that the problem cannot be solved in time $n^{o(\log n)}$ on $n$-vertex trees unless the Exponential Time Hypothesis (ETH) fails. The objective of this article is to provide hardness results for computing $\sigma(G,w)$ and $\sigma(G,w;r)$ when $G$ is a tree or a forest, relying on complexity assumptions weaker than the ETH. Namely, we study the problem from the viewpoint of parameterized complexity, and we assume the weaker hypothesis $FPT \neq W[1]$. Building on the techniques of Ara\'ujo et al., we prove that when $G$ is a forest, computing $\sigma(G,w)$ is $W[1]$-hard parameterized by the size of a largest connected component of $G$, and that computing $\sigma(G,w;r)$ is $W[2]$-hard parameterized by $r$. Our results rule out the existence of $FPT$ algorithms for computing these invariants on trees or forests for many natural choices of the parameter., Comment: 14 pages, 4 figures

We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirected edge-colored graph $G$, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree of $G$ of minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of the DIAMETER-TREE problem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree $\Delta$ of the input graph. We prove that DIAMETER-TREE is para-NP-hard for any combination of two of these three parameters, and that it is FPT parameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we prove DIAMETER-TREE to be NP-hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan (2001) proved that the problem can be solved in polynomial time on graphs with $\Delta = 3$, and Galbiati (2008) proved that it is NP-hard if $\Delta = 4$. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP-hard if $\Delta = 3$, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove that DIAMETER-TREE is in XP and W[1]-hard parameterized by the treewidth plus $\Delta$., Comment: 29 pages, 6 figures

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., Comment: 23 pages, 11 figures

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$., Comment: 12 pages, 3 figures

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., Comment: 18 pages, 1 figure

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., Comment: After the first version of this article appeared in arXiv, we learnt that Kolay and Panolan [abs/1504.08120] obtained simultaneously and independently some of the results of this article

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., Comment: 23 pages