Abstract
dc:descriptionGraph 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 P3-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.In social networks the Strong Triadic Closure is an assignment of the edges with strong or weak labels such that any two vertices that have a common neighbor with a strong edge are adjacent. The problem of maximizing the number of strong edges that satisfy the strong triadic closure is known as MaxSTC and it was recently shown to be NP-complete for general graphs. Here we initiate the study of graph classes for which MaxSTC is solvable in polynomial time or NP-complete. On the positive side, we show that the problem admits a polynomial-time algorithm for the following incomparable classes of graphs: proper interval graphs, cographs, graphs with maximum degree 3, and graphs with bounded treewidth. To complement our result, we show that the problem remains NP-complete on the following graphs: split graphs, and consequently also on chordal graphs, graphs with maximum degree at most 4, planar graphs, and (3K1, 2K2)-free graphs. Thus, we contribute to define the first border between graph classes on which the problem is polynomially solvable and on which it remains NP-complete.Inspired by the close relative of MaxSTC, we consider the Cluster Deletion problem. The goal is to remove the minimum number of edges of a given graph, such that every connected component of the resulting graph constitutes a clique. It is known that the decision version of Cluster Deletion is NP-complete on (P5-free) chordal graphs, whereas Cluster Deletion is solved in polynomial time on split graphs. However, the existence of a polynomial-time algorithm of Cluster Deleition on interval graphs, a proper subclass of chordal graphs, remained a well-known open problem. Our main contribution is that we settle this problem in the affirmative, by providing a polynomial-time algorithm for Cluster Deletion on interval graphs. Moreover, despite the simple formulation of a polynomial-time algorithm on split graphs, we show that Cluster Deletion remains NP-complete on a natural and slight generalization of split graphs that constitutes a proper subclass of P5-free chordal graphs. To complement our results, we provide faster and simpler polynomial-time algorithms for Cluster Deletion on subclasses of such a generalization of split graphs.Furthermore we introduce and initiate the parameterized study of the Strong F-closure problem, for a fixed graph F, which a natural generalization of MaxSTC. The goal is to select a maximum number of edges of the input graph G, and mark them as strong edges, in the following way: whenever a subset of the strong edges forms a subgraph isomorphic to F, then the corresponding induced subgraph of G is not isomorphic to F. Hence, the subgraph of G defined by the strong edges is not necessarily F-free, but whenever it contains a copy of F, there are additional edges in G to forbid that strong copy of F in G. Therefore Strong F-closure is a generalization of MaxSTC, whereas it is a relaxation of F-free Edge Deletion. We study Strong F-closure from a parameterized perspective with various natural parameterizations. Our main focus is on the number k of strong edges as the parameter. We show that the problem is FPT with this parameterization for every fixed graph F, whereas it does not admit a polynomial kernel even when F = P3. In fact, this latter case is equivalent to the MaxSTC problem, which motivates us to study this problem on input graphs belonging to well known graph classes. We show that MaxSTC does not admit a polynomial kernel even when the input graph is a split graph, whereas it admits a polynomial kernel when the input graph is planar, and even d-degenerate. Furthermore, on graphs of maximum degree at most 4, we show that MaxSTC is FPT with the above guarantee parameterization k − μ(G), where μ(G) is the maximum matching size of G. We conclude with some results on the arameterization of Strong F-closure by the number of weak edges of G.
Degree
thesis:*- Grantor dc:publisher
- University of Ioannina
- Year dc:date
- 2021
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Konstantinidis, Athanasios
- Κωνσταντινίδης, Αθανάσιος
Subjects
dc:subject × 23- Θεωρία γραφημάτων
- Προβλήματα Επεξεργασίας Γραφημάτων
- Πολυπλοκότητα
- Παραμετρική πολυπλοκότητα
- Αλγόριθμοι
- Ισχυρή Τριαδική Κλειστότητα
- Graph theory
- Graph Modification Problems
- Complexity
- Parameterized complexity
- Algorithms
- Strong triadic closure
- Cluster Deletion
- Μαθηματικά
- Φυσικές Επιστήμες
- Διακριτά μαθηματικά και Συνδυαστική
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμη ηλεκτρονικών υπολογιστών, θεωρία και μέθοδοι
- Mathematics
- Natural Sciences
- Discrete Mathematics and Combinatorics
- Computer and Information Sciences
- Computer science, theory and methods
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/57394