Back to results

University of Ioannina

Edge modification on perfect and reducible graphs with application to watermarking

Abstract

dc:description

In 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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/53107

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Mpanti, Anna; Μπαντή, Άννα. Edge modification on perfect and reducible graphs with application to watermarking. University of Ioannina, 2022. http://hdl.handle.net/10442/hedi/53107