Search

We examine the Π-Vertex Splitting problem, which consists of determining if a given graph can be transformed into a member of a fixed graph class Π using at most k vertex splits. A vertex split is a graph modification that replaces a vertex v with two new vertices, v_1 and v_2, and assigns each edge previously incident to v to either v_1, v_2, or both. We present polynomial-time algorithms for Forest-, Split-, and Threshold-Vertex Splitting, but show that Π-Vertex Splitting is NP-complete for various hereditary graph classes, including cluster graphs, bipartite graphs, perfect graphs, graphs free of finite sets of (induced) cycles, graphs free of a single biconnected forbidden (induced) subgraph, graphs free of a set of triconnected forbidden (induced) subgraphs with bounded diameter, and graphs free of a set of 4-connected forbidden (induced) subgraphs. Furthermore, we provide a dichotomy regarding the classical complexity of Π-Vertex Splitting for graph classes characterized by sets of forbidden induced subgraphs, each containing no more than three vertices. For each such class Π, we either demonstrate that Π-Vertex Splitting is in P, or show that the problem is NP-complete. Lastly, we investigate the parameterized complexity of Π-Vertex Splitting with respect to the number of splits as the parameter. We demonstrate that Triangle-Free Vertex Splitting is para-NP-hard, which implies that for Π characterized by a finite set of forbidden induced subgraphs, Π-Vertex Splitting is in general not fixed-parameter tractable. However, we obtain a linear kernel for Cluster Vertex Splitting.

Let G be a minor-closed graph class and let G be an n-vertex graph. We say that 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. Our first result is an algorithm that decides whether G is a k-apex of G in time 2^poly(k)⋅n². This algorithm improves the previous one, given by Sau, Stamoulis, and Thilikos [ICALP 2020, TALG 2022], whose running time was 2^poly(k)⋅n³. The elimination distance of G to G, denoted by ed_G(G), is the minimum number of rounds required to reduce each connected component of G to a graph in G by removing one vertex from each connected component in each round. Bulian and Dawar [Algorithmica 2017] proved the existence of an FPT-algorithm, with parameter k, to decide whether ed_G(G) ≤ k. This algorithm is based on the computability of the minor-obstructions and its dependence on k is not explicit. We extend the techniques used in the first algorithm to decide whether ed_G(G) ≤ k in time 2^{2^{2^poly(k)}}⋅n². This is the first algorithm for this problem with an explicit parametric dependence in k. In the special case where G excludes some apex-graph as a minor, we give two alternative algorithms, one running in time 2^{2^O(k²log k)}⋅n² and one running in time 2^{poly(k)}⋅n³. As a stepping stone for these algorithms, we provide an algorithm that decides whether ed_G(G) ≤ k in time 2^O(tw⋅ k + tw log tw)⋅n, where tw is the treewidth of G. This algorithm combines the dynamic programming framework of Reidl, Rossmanith, Villaamil, and Sikdar [ICALP 2014] for the particular case where G contains only the empty graph (i.e., for treedepth) with the representative-based techniques introduced by Baste, Sau, and Thilikos [SODA 2020]. In all the algorithmic complexities above, poly is a polynomial function whose degree depends on G, while the hidden constants also depend on G. Finally, we provide explicit upper bounds on the size of the graphs in the minor-obstruction set of the class of graphs E_k(G) = {G ∣ ed_G(G) ≤ k}., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 93:1-93:19

We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framework is a new compound logic operating with two types of sentences, expressing graph modification: the modulator sentence, defining some property of the modified part of the graph, and the target sentence, defining some property of the resulting graph. In our framework, modulator sentences are in counting monadic second-order logic (CMSOL) and have models of bounded treewidth, while target sentences express first-order logic (FOL) properties along with minor-exclusion. Our logic captures problems that are not definable in first-order logic and, moreover, may have instances of unbounded treewidth. Also, it permits the modeling of wide families of problems involving vertex/edge removals, alternative modulator measures (such as elimination distance or G-treewidth), multistage modifications, and various cut problems. Our main result is that, for this compound logic, model-checking can be done in quadratic time. All derived algorithms are constructive and this, as a byproduct, extends the constructibility horizon of the algorithmic applications of the Graph Minors theorem of Robertson and Seymour. The proposed logic can be seen as a general framework to capitalize on the potential of the irrelevant vertex technique. It gives a way to deal with problem instances of unbounded treewidth, for which Courcelle’s theorem does not apply., LIPIcs, Vol. 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), pages 61:1-61:21

The Weighted ℱ-Vertex Deletion for a class ℱ of graphs asks, weighted graph G, for a minimum weight vertex set S such that G-S ∈ ℱ. The case when ℱ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted ℱ-Vertex Deletion. Only three cases of minor-closed ℱ are known to admit constant-factor approximations, namely Vertex Cover, Feedback Vertex Set and Diamond Hitting Set. We study the problem for the class ℱ of θ_c-minor-free graphs, under the equivalent setting of the Weighted c-Bond Cover problem, and present a constant-factor approximation algorithm using the primal-dual method. For this, we leverage a structure theorem implicit in [Joret et al., SIDMA'14] which states the following: any graph G containing a θ_c-minor-model either contains a large two-terminal protrusion, or contains a constant-size θ_c-minor-model, or a collection of pairwise disjoint constant-sized connected sets that can be contracted simultaneously to yield a dense graph. In the first case, we tame the graph by replacing the protrusion with a special-purpose weighted gadget. For the second and third case, we provide a weighting scheme which guarantees a local approximation ratio. Besides making an important step in the quest of (dis)proving a constant-factor approximation for Weighted ℱ-Vertex Deletion, our result may be useful as a template for algorithms for other minor-closed families., LIPIcs, Vol. 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), pages 7:1-7:14

Graph modification problems play important role in both structural and algorithmic graph theory. These problems have been studied for decades and find a large number of practical applications in several different fields in real world. In this thesis, we study a famous edge deletion problem, known under the terms Cluster Deletion or P_3-free Edge Deletion, and we consider an edge labeling scheme that characterizes social networks in terms of an edge deletion problem, known as MaxSTC. Both problems are known to be NP-hard. We provide the first computational results of MaxSTC and we determine the computational complexity of Cluster Deletion on particular graph classes. Moreover, we generalize the MaxSTC problem and propose a relaxation of the classical F-free Edge Deletion problem that we call Strong F-Closure. We study Strong F-Closure from the parameterized perspective and provide computational results with various natural parameterizations. Τα προβλήματα επεξεργασίας γραφημάτων παίζουν σημαντικό ρόλο τόσο στην δομική όσο και στην αλγοριθμική θεωρία γραφημάτων. Τα προβλήματα αυτά έχουν μελετηθεί για δεκαετίες και βρίσκουν πρακτικές εφαρμογές σε σημαντικές περιοχές έρευνας. Σε αυτήν την διατριβή μελετάμε ένα κλασικό πρόβλημα επεξεργασίας ακμών, γνωστό ως Cluster Deletion ή P_3-free Edge Deletion, και εξετάζουμε έναν κανόνα επιγραφής ακμών ο οποίος χαρακτηρίζει τα κοινωνικά δίκτυα, ως ένα πρόβλημα διαγραφής ακμών, γνωστό ως MaxSTC. Τα δύο αυτά προβλήματα είναι γνωστό ότι είναι ΝΡ-δύσκολα. Παρέχουμε τα πρώτα υπολογιστικά αποτελέσματα για το MaxSTC και καθορίζουμε την υπολογιστική πολυπλοκότητα για το Cluster Deletion σε κλάσεις γραφημάτων. Επιπλέον, γενικεύουμε το πρόβλημα MaxSTC προτείνοντας μία "χαλάρωση1’ του κλασικού προβλήματος επεξεργασίας ακμών F-free Edge Deletion, το οποίο καλούμε Strong F-Closure. Μελετάμε το πρόβλημα Strong F-Closure από την σκοπιά της παραμετρικής πολυπλοκότητας και παρέχουμε τα πρώτα υπολογιστικά αποτελέσματα υπό διαφορετικούς παραμέτρους. 170 σ.

International audience; 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.

A permutation graph can be defined as an intersection graph of segments whose endpoints lie on two parallel lines 𝓁₁ and 𝓁₂, one on each. A bipartite permutation graph is a permutation graph which is bipartite. In this paper we study the parameterized complexity of the bipartite permutation vertex deletion problem, which asks, for a given n-vertex graph, whether we can remove at most k vertices to obtain a bipartite permutation graph. This problem is NP-complete by the classical result of Lewis and Yannakakis [John M. Lewis and Mihalis Yannakakis, 1980]. We analyze the structure of the so-called almost bipartite permutation graphs which may contain holes (large induced cycles) in contrast to bipartite permutation graphs. We exploit the structural properties of the shortest hole in a such graph. We use it to obtain an algorithm for the bipartite permutation vertex deletion problem with running time f(k)n^O(1), and also give a polynomial-time 9-approximation algorithm., LIPIcs, Vol. 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), pages 5:1-5:16

In general, a graph modification problem is defined by a graph modification operation ⊠ and a target graph property 𝒫. Typically, the modification operation ⊠ may be vertex deletion , edge deletion , edge contraction , or edge addition and the question is, given a graph G and an integer k , whether it is possible to transform G to a graph in 𝒫 after applying the operation ⊠ k times on G . This problem has been extensively studied for particular instantiations of ⊠ and 𝒫. In this article, we consider the general property 𝒫 𝛗 of being planar and, additionally, being a model of some First-Order Logic (FOL) sentence 𝛗 (an FOL-sentence). We call the corresponding meta-problem Graph ⊠-Modification to Planarity and 𝛗 and prove the following algorithmic meta-theorem: there exists a function f : ℕ 2 → ℕ such that, for every ⊠ and every FOL-sentence 𝛗, the Graph ⊠-Modification to Planarity and 𝛗 is solvable in f ( k,|𝛗| )⋅ n 2 time. The proof constitutes a hybrid of two different classic techniques in graph algorithms. The first is the irrelevant vertex technique that is typically used in the context of Graph Minors and deals with properties such as planarity or surface-embeddability (that are not FOL-expressible) and the second is the use of Gaifman’s locality theorem that is the theoretical base for the meta-algorithmic study of FOL-expressible problems.

The {\sc Plane Diameter Completion} problem asks, given a plane graph $G$ and a positive integer $d$, if it is a spanning subgraph of a plane graph $H$ that has diameter at most $d$. We examine two variants of this problem where the input comes with another parameter $k$. In the first variant, called BPDC, $k$ upper bounds the total number of edges to be added and in the second, called BFPDC, $k$ upper bounds the number of additional edges per face. We prove that both problems are {\sf NP}-complete, the first even for 3-connected graphs of face-degree at most 4 and the second even when $k=1$ on 3-connected graphs of face-degree at most 5. In this paper we give parameterized algorithms for both problems that run in $O(n^{3})+2^{2^{O((kd)^2\log d)}}\cdot n$ steps., Accepted in IPEC 2015

In this thesis, we study the parameterized complexity of several N P -complete problems. More precisely, we study the existence of polynomial kernels for graph and relations modification prob- lems. In particular, we introduce the concept of branches, which provides polynomial kernels for some graph modification problems when the target graph class admits a so-called adjacency de- composition. This technique allows us to obtain the first known polynomial kernels for the CLOSEST 3-LEAF POWER, COGRAPH EDITION and PROPER INTERVAL COMPLETION problems. Regarding relations modification problems, we develop and push further the concept of Conflict Packing, a technique that has already been used in a few parameterized problems and that provides polynomial kernels for several problems. We thus present a linear vertex-kernel for the FEEDBACK ARC SET IN TOURNAMENTS problem, and adapt these techniques to obtain a linear vertex-kernel for the DENSE ROOTED TRIPLET INCONSISTENCY problem as well. In both cases, our results im- prove the best known bound of O(k^2) vertices. Finally, we apply the Conflict Packing technique on the DENSE BETWEENNESS and DENSE CIRCULAR ORDERING problems, obtaining once again linear vertex-kernels. To the best of our knowledge, these results constitute the first known polynomial kernels for these problems.; Dans le cadre de cette thèse, nous considérons la complexité paramétrée de problèmes NP- complets. Plus précisément, nous nous intéressons à l'existence d'algorithmes de noyau polynomiaux pour des problèmes d'édition de graphes et de relations. Nous introduisons en particulier la notion de branches, qui permet d'obtenir des algorithmes polynomiaux pour des problèmes d'édition de graphes lorsque la classe de graphes cible respecte une décomposition d'adjacence. Cette technique nous permet ainsi d'élaborer les premiers algorithmes de noyaux polynomiaux pour les problèmes CLOSEST 3-LEAF POWER, COGRAPH EDITION et PROPER INTERVAL COMPLETION. Concernant les problèmes d'édition de relations, nous étendons la notion de Conflict Packing, qui a déjà été utilisée dans quelques problèmes paramétrés et permet d'élaborer des algorithmes de noyau linéaires pour différents problèmes. Nous présentons un noyau linéaire pour le problème FEEDBACK ARC SET IN TOURNAMENTS, et adaptons les techniques utilisées pour obtenir un noyau linéaire pour le problème DENSE ROOTED TRIPLET INCONSISTENCY. Dans les deux cas, nos résultats améliorent la meilleure borne connue, à savoir un noyau quadratique. Finalement, nous appliquons cette tech- nique sur les problèmes DENSE BETWEENNESS et DENSE CIRCULAR ORDERING, obtenant à nouveau des noyaux linéaires, qui constituent les premiers algorithmes de noyau polynomiaux connus pour ces problèmes.

International audience; We initiate the study of the Bipartite Contraction problem from the perspective of param- eterized complexity. In this problem we are given a graph G on n vertices and an integer k, and the task is to determine whether we can obtain a bipartite graph from G by a sequence of at most k edge contractions. Our main result is an $f(k)n^{O(1)}$ time algorithm for Bipartite Con- traction. Despite a strong resemblance between Bipartite Contraction and the classical Odd Cycle Transversal (OCT) problem, the methods developed to tackle OCT do not seem to be directly applicable to Bipartite Contraction. To obtain our result, we combine several techniques and concepts that are central in parameterized complexity: iterative compression, irrelevant vertex, and important separators. To the best of our knowledge, this is the first time the irrelevant vertex technique and the concept of important separators are applied in unison. Furthermore, our algorithm may serve as a comprehensible example of the usage of the irrelevant vertex technique.

In this thesis, we study the parameterized complexity of several N P -complete problems. More precisely, we study the existence of polynomial kernels for graph and relations modification prob- lems. In particular, we introduce the concept of branches, which provides polynomial kernels for some graph modification problems when the target graph class admits a so-called adjacency de- composition. This technique allows us to obtain the first known polynomial kernels for the CLOSEST 3-LEAF POWER, COGRAPH EDITION and PROPER INTERVAL COMPLETION problems. Regarding relations modification problems, we develop and push further the concept of Conflict Packing, a technique that has already been used in a few parameterized problems and that provides polynomial kernels for several problems. We thus present a linear vertex-kernel for the FEEDBACK ARC SET IN TOURNAMENTS problem, and adapt these techniques to obtain a linear vertex-kernel for the DENSE ROOTED TRIPLET INCONSISTENCY problem as well. In both cases, our results im- prove the best known bound of O(k^2) vertices. Finally, we apply the Conflict Packing technique on the DENSE BETWEENNESS and DENSE CIRCULAR ORDERING problems, obtaining once again linear vertex-kernels. To the best of our knowledge, these results constitute the first known polynomial kernels for these problems., Dans le cadre de cette thèse, nous considérons la complexité paramétrée de problèmes NP- complets. Plus précisément, nous nous intéressons à l'existence d'algorithmes de noyau polynomiaux pour des problèmes d'édition de graphes et de relations. Nous introduisons en particulier la notion de branches, qui permet d'obtenir des algorithmes polynomiaux pour des problèmes d'édition de graphes lorsque la classe de graphes cible respecte une décomposition d'adjacence. Cette technique nous permet ainsi d'élaborer les premiers algorithmes de noyaux polynomiaux pour les problèmes CLOSEST 3-LEAF POWER, COGRAPH EDITION et PROPER INTERVAL COMPLETION. Concernant les problèmes d'édition de relations, nous étendons la notion de Conflict Packing, qui a déjà été utilisée dans quelques problèmes paramétrés et permet d'élaborer des algorithmes de noyau linéaires pour différents problèmes. Nous présentons un noyau linéaire pour le problème FEEDBACK ARC SET IN TOURNAMENTS, et adaptons les techniques utilisées pour obtenir un noyau linéaire pour le problème DENSE ROOTED TRIPLET INCONSISTENCY. Dans les deux cas, nos résultats améliorent la meilleure borne connue, à savoir un noyau quadratique. Finalement, nous appliquons cette tech- nique sur les problèmes DENSE BETWEENNESS et DENSE CIRCULAR ORDERING, obtenant à nouveau des noyaux linéaires, qui constituent les premiers algorithmes de noyau polynomiaux connus pour ces problèmes.