University of Ioannina
Edge modification on perfect and reducible graphs with application to watermarking
Abstract
dc:descriptionIn graph modification problems, we have to repair, improve, or adjust a graph to satisfy appropriate properties while minimizing the cost of the modification. The study of graph modification problems is crucial to computer science as they find applications in different areas, such as biology, mathematics, sociology, machine learning, data mining, and computer vision. This PhD thesis has a theoretical and a more applied part, both related to edge modification problems on classes of graphs. For the theoretical part, we study and present polynomial algorithms for the minimum completion problem (i) of a graph with a “tail” for four subclasses of perfect graphs and (ii) of a graph and an added edge for the class of P4-sparse graphs. The minimum completion (fill-in) problem is defined as follows: Given a graph family F (more generally, a property Π) and a graph G, the completion problem asks for the minimum number of non-edges needed to be added to G so that the resulting graph belongs to the graph family F (or has property Π). This problem is NP-complete for many subclasses of perfect graphs and polynomial solutions are available only for minimal completion sets. Given a graph G, a tail uw is an edge connecting a vertex w ̸∈ V (G) to a vertex u ∈ V (G). We study the minimum completion problem for the graph G+uw for the classes of split, quasi-threshold, threshold, and P4-sparse graphs. Based on properties of the structure of split graphs and of the tree representation of quasi-threshold, threshold, and P4-sparse graphs, we present linear-time algorithms to solve this problem. Additionally, for the class of P4-sparse graphs, we study the minimum completion problem of a P4-sparse graph G with an added edge. For any optimal solution of the problem, we prove that there is an optimal solution whose form is of one of a small number of possibilities. This along with the solution of the problem when the added edge connects two non-adjacent vertices of a spider or connects two vertices in different connected components of the graph enables us to present a linear-time algorithm for the problem. The applied part of this thesis focuses on the study of malicious edge modifications of reducible graphs used to encode an integer number as a watermark in a specific software watermarking codec system. The most important step in any software watermarking method is the choice of the right watermark, which, in the watermarking system we study, is a watermark producing a reducible graph in which edge modifications can be detected. Through the study of such edge modifications, we classify watermarks as strong, intermediate, or weak and we are able to give recommendations for the best choice of watermarks to use.
Degree
thesis:*- Grantor dc:publisher
- University of Ioannina
- Year dc:date
- 2022
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Mpanti, Anna
- Μπαντή, Άννα
Subjects
dc:subject × 22- Υδατογράφηση
- Πρόβλημα συμπλήρωσης
- Προσθήκη ακμής
- Split γράφημα
- Quasi-threshold γράφημα
- Threshold γράφημα
- P4-sparse γράφημα
- Αναγώγιμο γράφημα
- Watermarking
- Completion problem
- Edge addition
- Split graph
- Quasi-threshold graph
- Threshold graph
- P4-sparse graph
- Reducible graph
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Φυσικές Επιστήμες
- Επιστήμη ηλεκτρονικών υπολογιστών, θεωρία και μέθοδοι
- Computer and Information Sciences
- Natural Sciences
- Computer science, theory and methods
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/53107