The Experts below are selected from a list of 27552 Experts worldwide ranked by ideXlab platform
Peter Jonsson - One of the best experts on this subject based on the ideXlab platform.
-
a refined view of causal Graphs and component sizes sp Closed Graph classes and beyond
arXiv: Artificial Intelligence, 2014Co-Authors: Christer Backstrom, Peter JonssonAbstract:The causal Graph of a planning instance is an important tool for planning both in practice and in theory. The theoretical studies of causal Graphs have largely analysed the computational complexity of planning for instances where the causal Graph has a certain structure, often in combination with other parameters like the domain size of the variables. Chen and Gimand#233;nez ignored even the structure and considered only the size of the weakly connected components. They proved that planning is tractable if the components are bounded by a constant and otherwise intractable. Their intractability result was, however, conditioned by an assumption from parameterised complexity theory that has no known useful relationship with the standard complexity classes. We approach the same problem from the perspective of standard complexity classes, and prove that planning is NP-hard for classes with unbounded components under an additional restriction we refer to as SP-Closed. We then argue that most NP-hardness theorems for causal Graphs are difficult to apply and, thus, prove a more general result; even if the component sizes grow slowly and the class is not densely populated with Graphs, planning still cannot be tractable unless the polynomial hierachy collapses. Both these results still hold when restricted to the class of acyclic causal Graphs. We finally give a partial characterization of the borderline between NP-hard and NP-intermediate classes, giving further insight into the problem.
-
a refined view of causal Graphs and component sizes sp Closed Graph classes and beyond
Journal of Artificial Intelligence Research, 2013Co-Authors: Christer Backstrom, Peter JonssonAbstract:The causal Graph of a planning instance is an important tool for planning both in practice and in theory. The theoretical studies of causal Graphs have largely analysed the computational complexity of planning for instances where the causal Graph has a certain structure, often in combination with other parameters like the domain size of the variables. Chen and Gimenez ignored even the structure and considered only the size of the weakly connected components. They proved that planning is tractable if the components are bounded by a constant and otherwise intractable. Their intractability result was, however, conditioned by an assumption from parameterised complexity theory that has no known useful relationship with the standard complexity classes. We approach the same problem from the perspective of standard complexity classes, and prove that planning is NP-hard for classes with unbounded components under an additional restriction we refer to as SP-Closed. We then argue that most NP-hardness theorems for causal Graphs are difficult to apply and, thus, prove a more general result; even if the component sizes grow slowly and the class is not densely populated with Graphs, planning still cannot be tractable unless the polynomial hierachy collapses. Both these results still hold when restricted to the class of acyclic causal Graphs. We finally give a partial characterization of the borderline between NP-hard and NP-intermediate classes, giving further insight into the problem.
Christer Backstrom - One of the best experts on this subject based on the ideXlab platform.
-
a refined view of causal Graphs and component sizes sp Closed Graph classes and beyond
arXiv: Artificial Intelligence, 2014Co-Authors: Christer Backstrom, Peter JonssonAbstract:The causal Graph of a planning instance is an important tool for planning both in practice and in theory. The theoretical studies of causal Graphs have largely analysed the computational complexity of planning for instances where the causal Graph has a certain structure, often in combination with other parameters like the domain size of the variables. Chen and Gimand#233;nez ignored even the structure and considered only the size of the weakly connected components. They proved that planning is tractable if the components are bounded by a constant and otherwise intractable. Their intractability result was, however, conditioned by an assumption from parameterised complexity theory that has no known useful relationship with the standard complexity classes. We approach the same problem from the perspective of standard complexity classes, and prove that planning is NP-hard for classes with unbounded components under an additional restriction we refer to as SP-Closed. We then argue that most NP-hardness theorems for causal Graphs are difficult to apply and, thus, prove a more general result; even if the component sizes grow slowly and the class is not densely populated with Graphs, planning still cannot be tractable unless the polynomial hierachy collapses. Both these results still hold when restricted to the class of acyclic causal Graphs. We finally give a partial characterization of the borderline between NP-hard and NP-intermediate classes, giving further insight into the problem.
-
a refined view of causal Graphs and component sizes sp Closed Graph classes and beyond
Journal of Artificial Intelligence Research, 2013Co-Authors: Christer Backstrom, Peter JonssonAbstract:The causal Graph of a planning instance is an important tool for planning both in practice and in theory. The theoretical studies of causal Graphs have largely analysed the computational complexity of planning for instances where the causal Graph has a certain structure, often in combination with other parameters like the domain size of the variables. Chen and Gimenez ignored even the structure and considered only the size of the weakly connected components. They proved that planning is tractable if the components are bounded by a constant and otherwise intractable. Their intractability result was, however, conditioned by an assumption from parameterised complexity theory that has no known useful relationship with the standard complexity classes. We approach the same problem from the perspective of standard complexity classes, and prove that planning is NP-hard for classes with unbounded components under an additional restriction we refer to as SP-Closed. We then argue that most NP-hardness theorems for causal Graphs are difficult to apply and, thus, prove a more general result; even if the component sizes grow slowly and the class is not densely populated with Graphs, planning still cannot be tractable unless the polynomial hierachy collapses. Both these results still hold when restricted to the class of acyclic causal Graphs. We finally give a partial characterization of the borderline between NP-hard and NP-intermediate classes, giving further insight into the problem.
Dimitrios M Thilikos - One of the best experts on this subject based on the ideXlab platform.
-
k apices of minor Closed Graph classes i bounding the obstructions
arXiv: Combinatorics, 2021Co-Authors: Ignasi Sau, Giannos Stamoulis, Dimitrios M ThilikosAbstract: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}.$ We prove that every Graph in the obstruction set of ${\cal A}_k ({\cal G}),$ i.e., the minor-minimal set of Graphs not belonging to ${\cal A}_k ({\cal G}),$ has size at most $2^{2^{2^{2^{{\sf poly}(k)}}}},$ where ${\sf poly}$ is a polynomial function whose degree depends on the size of the minor-obstructions of ${\cal G}.$ This bound drops to $2^{2^{{\sf poly}(k)}}$ when ${\cal G}$ excludes some apex Graph as a minor.
-
linear kernels for edge deletion problems to immersion Closed Graph classes
SIAM Journal on Discrete Mathematics, 2021Co-Authors: Archontia C. Giannopoulou, Dimitrios M Thilikos, Michal Pilipczuk, Jean-florent Raymond, Marcin WrochnaAbstract:Suppose ${\mathcal{F}}$ is a finite family of Graphs. We consider the following meta-problem, called $\mathcal{F}$-Immersion Deletion: given a Graph $G$ and integer $k$, decide whether the deletion...
-
An FPT-Algorithm for Recognizing k-Apices of Minor-Closed Graph Classes
2020Co-Authors: Ignasi Sau Valls, Giannos Stamoulis, Dimitrios M ThilikosAbstract:Let G be a Graph class. We say that a Graph G is a k-apex of G if G contains a set S of at most k vertices such that G \ S belongs to G. We prove that if G is minor-Closed, then there is an algorithm that either returns a set S certifying that G is a k-apex of G or reports that such a set does not exist, in 2 poly(k) n 3 time. Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G, i.e., the minor-minimal set of Graphs not belonging to G. In the special case where G excludes some apex Graph as a minor, we give an alternative algorithm running in 2 poly(k) n 2 time.
-
k apices of minor Closed Graph classes ii parameterized algorithms
arXiv: Data Structures and Algorithms, 2020Co-Authors: Ignasi Sau, Giannos Stamoulis, Dimitrios M ThilikosAbstract: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.
-
an fpt algorithm for recognizing k apices of minor Closed Graph classes
arXiv: Data Structures and Algorithms, 2020Co-Authors: Ignasi Sau, Giannos Stamoulis, Dimitrios M ThilikosAbstract:Let ${\cal G}$ be a 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 prove that if ${\cal G}$ is minor-Closed, then there is an algorithm that either returns a set $S$ certifying that $G$ is a $k$-apex of ${\cal G}$ or reports that such a set does not exist, in $2^{{\sf poly}(k)}\cdot n^3$ time. Here ${\sf poly}$ is a polynomial function whose degree depends on the maximum size of a minor-obstruction of ${\cal G}$, i.e., the minor-minimal set of Graphs not belonging to ${\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.
Laurent Viennot - One of the best experts on this subject based on the ideXlab platform.
-
diameter computation on h minor free Graphs and Graphs of bounded distance vc dimension
Symposium on Discrete Algorithms, 2020Co-Authors: Guillaume Ducoffe, Michel Habib, Laurent ViennotAbstract:Under the Strong Exponential-Time Hypothesis, the diameter of general unweighted Graphs cannot be computed in truly subquadratic time. Nevertheless there are several Graph classes for which this can be done such as bounded-treewidth Graphs, interval Graphs and planar Graphs, to name a few. We propose to study unweighted Graphs of constant distance VC-dimension as a broad generalization of many such classes - where the distance VC-dimension of a Graph G is defined as the VC-dimension of its ball hyperGraph: whose hyper-edges are the balls of all possible radii and centers in G. In particular for any fixed H, the class of H-minor free Graphs has distance VC-dimension at most |V(H)| − 1. • Our first main result is a Monte Carlo algorithm that on Graphs of distance VC-dimension at most d, for any fixed k, either computes the diameter or concludes that it is larger than k in time [MATH HERE], where ed ∈ (0; 1) only depends on d. We thus obtain a truly subquadratic-time parameterized algorithm for computing the diameter on such Graphs. • Then as a byproduct of our approach, we get the first truly subquadratic-time randomized algorithm for constant diameter computation on all the nowhere dense Graph classes. The latter classes include all proper minor-Closed Graph classes, bounded-degree Graphs and Graphs of bounded expansion. • Finally we show how to remove the dependency on k for any Graph class that excludes a fixed Graph H as a minor. More generally, our techniques apply to any Graph with constant distance VC-dimension and polynomial expansion (or equivalently having strongly sublinear balanced separators). As a result for all such Graphs one obtains a truly subquadratic-time randomized algorithm for computing their diameter. We note that all our results also hold for radius computation. Our approach is based on the work of Chazelle and Welzl who proved the existence of spanning paths with strongly sublinear stabbing number for every hyperGraph of constant VC-dimension. We show how to compute such paths efficiently by combining known algorithms for the stabbing number problem with a clever use of e-nets, region decomposition and other partition techniques.
Michal Pilipczuk - One of the best experts on this subject based on the ideXlab platform.
-
polynomial bounds for centered colorings on proper minor Closed Graph classes
Journal of Combinatorial Theory Series B, 2021Co-Authors: Michal Pilipczuk, Sebastian SiebertzAbstract:Abstract For p ∈ N , a coloring λ of the vertices of a Graph G is p-centered if for every connected subGraph H of G, either H receives more than p colors under λ or there is a color that appears exactly once in H. Centered colorings play an important role in the theory of sparse Graph classes introduced by Nesetřil and Ossona de Mendez [31] , [32] , as they structurally characterize classes of bounded expansion — one of the key sparsity notions in this theory. More precisely, a class of Graphs C has bounded expansion if and only if there is a function f : N → N such that every Graph G ∈ C for every p ∈ N admits a p-centered coloring with at most f ( p ) colors. Unfortunately, known proofs for the existence of such colorings yield large upper bounds on the function f governing the number of colors needed, even for as simple classes as planar Graphs. In this paper, we prove that every K t -minor-free Graph admits a p-centered coloring with O ( p g ( t ) ) colors for some function g. In the special case that the Graph is embeddable in a fixed surface Σ we show that it admits a p-centered coloring with O ( p 19 ) colors, with the degree of the polynomial independent of the genus of Σ. This provides the first polynomial upper bounds on the number of colors needed in p-centered colorings of Graphs drawn from proper minor-Closed classes, which answers an open problem posed by Dvořak [1] . As an algorithmic application, we use our main result to prove that if C is a fixed proper minor-Closed class of Graphs, then given Graphs H and G, on p and n vertices, respectively, where G ∈ C , it can be decided whether H is a subGraph of G in time 2 O ( p log p ) ⋅ n O ( 1 ) and space n O ( 1 ) .
-
linear kernels for edge deletion problems to immersion Closed Graph classes
SIAM Journal on Discrete Mathematics, 2021Co-Authors: Archontia C. Giannopoulou, Dimitrios M Thilikos, Michal Pilipczuk, Jean-florent Raymond, Marcin WrochnaAbstract:Suppose ${\mathcal{F}}$ is a finite family of Graphs. We consider the following meta-problem, called $\mathcal{F}$-Immersion Deletion: given a Graph $G$ and integer $k$, decide whether the deletion...
-
polynomial bounds for centered colorings on proper minor Closed Graph classes
Symposium on Discrete Algorithms, 2019Co-Authors: Michal Pilipczuk, Sebastian SiebertzAbstract:For p ∈ N, a coloring λ of the vertices of a Graph G is p-centered if for every connected subGraph H of G, either H receives more than p colors under λ or there is a color that appears exactly once in H. Centered colorings play an important role in the theory of sparse Graphs introduced by Nesetril and Ossona de Mendez [27], as they structurally characterize classes of bounded expansion, one of the key notions in this theory. More precisely, a class of Graphs C has bounded expansion if and only if there is a function f : N → N such that every Graph G ∈ C for every p ∈ N admits a p-centered coloring with at most f (p) colors. Unfortunately, known proofs of the existence of such colorings yield large upper bounds on the function f governing the number of colors needed, even for as simple classes as planar Graphs.We prove that every Kt-minor-free Graph admits a p-centered coloring with O(pg(t)) colors for some function g. In the special case that the Graph is embeddable in a fixed surface Σ we show that it admits a p-centered coloring with O(p19) colors, with the degree of the polynomial independent of the genus of Σ. This provides the first polynomial upper bounds on the number of colors needed in p-centered colorings of Graphs drawn from proper minor-Closed classes, which answers an open problem posed by Dvorak [1].As an algorithmic application, we use our main result to prove that if C is a fixed proper minor-Closed class of Graphs, then given Graphs H and G, on p and n vertices, respectively, where G ∈ C, it can be decided whether H is a subGraph of G in time 2 O(p log p) . nO(1) and space nO(1).
-
polynomial bounds for centered colorings on proper minor Closed Graph classes
arXiv: Discrete Mathematics, 2018Co-Authors: Michal Pilipczuk, Sebastian SiebertzAbstract:For $p\in \mathbb{N}$, a coloring $\lambda$ of the vertices of a Graph $G$ is {\em{$p$-centered}} if for every connected subGraph~$H$ of $G$, either $H$ receives more than $p$ colors under $\lambda$ or there is a color that appears exactly once in $H$. In this paper, we prove that every $K_t$-minor-free Graph admits a $p$-centered coloring with $\mathcal{O}(p^{g(t)})$ colors for some function $g$. In the special case that the Graph is embeddable in a fixed surface $\Sigma$ we show that it admits a $p$-centered coloring with $\mathcal{O}(p^{19})$ colors, with the degree of the polynomial independent of the genus of $\Sigma$. This provides the first polynomial upper bounds on the number of colors needed in $p$-centered colorings of Graphs drawn from proper minor-Closed classes, which answers an open problem posed by Dvoř{a}k. As an algorithmic application, we use our main result to prove that if $\mathcal{C}$ is a fixed proper minor-Closed class of Graphs, then given Graphs $H$ and $G$, on $p$ and $n$ vertices, respectively, where $G\in \mathcal{C}$, it can be decided whether $H$ is a subGraph of $G$ in time $2^{\mathcal{O}(p\log p)}\cdot n^{\mathcal{O}(1)}$ and space $n^{\mathcal{O}(1)}$.
-
Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
2017Co-Authors: Archontia C. Giannopoulou, Dimitrios M Thilikos, Michal Pilipczuk, Jean-florent Raymond, Marcin WrochnaAbstract:Suppose F is a finite family of Graphs. We consider the following meta-problem, called F-Immersion Deletion: given a Graph G and an integer k, decide whether the deletion of at most k edges of G can result in a Graph that does not contain any Graph from F as an immersion. This problem is a close relative of the F-Minor Deletion problem studied by Fomin et al. [FOCS 2012], where one deletes vertices in order to remove all minor models of Graphs from F. We prove that whenever all Graphs from F are connected and at least one Graph of F is planar and subcubic, then the F-Immersion Deletion problem admits: a constant-factor approximation algorithm running in time O(m 3 · n 3 · log m); a linear kernel that can be computed in time O(m 4 · n 3 · log m); and a O(2 O(k) + m 4 · n 3 · log m)-time fixed-parameter algorithm, where n, m count the vertices and edges of the input Graph. Our findings mirror those of Fomin et al. [FOCS 2012], who obtained similar results for F-Minor Deletion, under the assumption that at least one Graph from F is planar. An important difference is that we are able to obtain a linear kernel for F-Immersion Deletion, while the exponent of the kernel of Fomin et al. depends heavily on the family F. In fact, this dependence is unavoidable under plausible complexity assumptions, as proven by Giannopoulou et al. [ICALP 2015]. This reveals that the kernelization complexity of F-Immersion Deletion is quite different than that of F-Minor Deletion.