Search Results

Documents authored by Konstantinidis, Athanasios L.

Document
Research
DOI: 10.4230/OASIcs.Grossi.4
On Graph Burning and Edge Burning

Authors: Giuseppe F. Italiano, Athanasios L. Konstantinidis, and Manas Jyoti Kashyop

Published in: OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025)

Abstract
Graph burning is a deterministic, discrete-time process that models how influence or contagion spreads in a graph. Initially, all vertices are unburned. At each round, one new vertex is chosen to burn. Once a vertex is burned, in the next round each of its unburned neighbors become burned. The process ends when all vertices are burned. The burning number of a graph is the minimum number of rounds needed for the process to end. Very recently, a variant called edge burning was introduced, where instead of vertices we burn edges: at each round one new edge is burned. Once an edge is burned, in the next round all its unburned incident edges become burned. The edge burning number is the minimum number of rounds that are needed to burn all the edges. In this paper, we present a systematic study of edge burning and provide some new results for graph burning. First, we show a tight relationship between the edge burning number and the burning number of a given graph: specifically, their absolute difference is at most 1. Moreover, we show that the edge burning number of a graph is equal to the graph burning number of its line graph. On the computation complexity side, we show that the edge burning problem is NP-complete, but can be solved in linear time on paths, split graphs, and cographs. Furthermore, we give an XP algorithm when the edge burning problem is parameterized by the diameter of the input graph and a linear kernel when parameterized by the neighborhood diversity. For the graph burning problem, we provide 2-approximation algorithms when either the solution is part of the input or forced to form a path.
Cite as

Giuseppe F. Italiano, Athanasios L. Konstantinidis, and Manas Jyoti Kashyop. On Graph Burning and Edge Burning. In From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 132, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{italiano_et_al:OASIcs.Grossi.4,
  author =	{Italiano, Giuseppe F. and Konstantinidis, Athanasios L. and Kashyop, Manas Jyoti},
  title =	{{On Graph Burning and Edge Burning}},
  booktitle =	{From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday},
  pages =	{4:1--4:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-391-1},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{132},
  editor =	{Conte, Alessio and Marino, Andrea and Rosone, Giovanna and Vitter, Jeffrey Scott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.4},
  URN =		{urn:nbn:de:0030-drops-238039},
  doi =		{10.4230/OASIcs.Grossi.4},
  annote =	{Keywords: Burning Number, Graph Burning, Edge Burning, Approximation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.12
Cluster Deletion on Interval Graphs and Split Related Graphs

Authors: Athanasios L. Konstantinidis and Charis Papadopoulos

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
In 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 (P_5-free) chordal graphs, whereas Cluster Deletion is solved in polynomial time on split graphs. However, the existence of a polynomial-time algorithm of Cluster Deletion 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 the 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 P_5-free chordal graphs. Although the later result arises from the already-known reduction for P_5-free chordal graphs, we give an alternative proof showing an interesting connection between edge-weighted and vertex-weighted variations of the problem. To complement our results, we provide faster and simpler polynomial-time algorithms for Cluster Deletion on subclasses of such a generalization of split graphs.
Cite as

Athanasios L. Konstantinidis and Charis Papadopoulos. Cluster Deletion on Interval Graphs and Split Related Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{konstantinidis_et_al:LIPIcs.MFCS.2019.12,
  author =	{Konstantinidis, Athanasios L. and Papadopoulos, Charis},
  title =	{{Cluster Deletion on Interval Graphs and Split Related Graphs}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.12},
  URN =		{urn:nbn:de:0030-drops-109568},
  doi =		{10.4230/LIPIcs.MFCS.2019.12},
  annote =	{Keywords: Cluster deletion, interval graphs, split graphs}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.23
Parameterized Aspects of Strong Subgraph Closure

Authors: Petr A. Golovach, Pinar Heggernes, Athanasios L. Konstantinidis, Paloma T. Lima, and Charis Papadopoulos

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
Motivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized study of the Strong F-closure problem, where F is a fixed graph. This is a generalization of Strong Triadic Closure, whereas it is a relaxation of F-free Edge Deletion. In Strong F-closure, we want 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 destroy that strong copy of F in G. 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 =P_3. In fact, this latter case is equivalent to the Strong Triadic Closure problem, which motivates us to study this problem on input graphs belonging to well known graph classes. We show that Strong Triadic Closure 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 Strong Triadic Closure is FPT with the above guarantee parameterization k - mu(G), where mu(G) is the maximum matching size of G. We conclude with some results on the parameterization of Strong F-closure by the number of edges of G that are not selected as strong.
Cite as

Petr A. Golovach, Pinar Heggernes, Athanasios L. Konstantinidis, Paloma T. Lima, and Charis Papadopoulos. Parameterized Aspects of Strong Subgraph Closure. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{golovach_et_al:LIPIcs.SWAT.2018.23,
  author =	{Golovach, Petr A. and Heggernes, Pinar and Konstantinidis, Athanasios L. and Lima, Paloma T. and Papadopoulos, Charis},
  title =	{{Parameterized Aspects of Strong Subgraph Closure}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{23:1--23:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.23},
  URN =		{urn:nbn:de:0030-drops-88490},
  doi =		{10.4230/LIPIcs.SWAT.2018.23},
  annote =	{Keywords: Strong triadic closure, Parameterized complexity, Forbidden subgraphs}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.53
Maximizing the Strong Triadic Closure in Split Graphs and Proper Interval Graphs

Authors: Athanasios L. Konstantinidis and Charis Papadopoulos

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
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 was recently shown to be NP-complete for general graphs. Here we initiate the study of graph classes for which the problem is solvable. We show that the problem admits a polynomial-time algorithm for two unrelated classes of graphs: proper interval graphs and trivially-perfect graphs. To complement our result, we show that the problem remains NP-complete on split graphs, and consequently also on chordal 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.
Cite as

Athanasios L. Konstantinidis and Charis Papadopoulos. Maximizing the Strong Triadic Closure in Split Graphs and Proper Interval Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 53:1-53:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{konstantinidis_et_al:LIPIcs.ISAAC.2017.53,
  author =	{Konstantinidis, Athanasios L. and Papadopoulos, Charis},
  title =	{{Maximizing the Strong Triadic Closure in Split Graphs and Proper Interval Graphs}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{53:1--53:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.53},
  URN =		{urn:nbn:de:0030-drops-82113},
  doi =		{10.4230/LIPIcs.ISAAC.2017.53},
  annote =	{Keywords: strong triadic closure, polynomial-time algorithm, NP-completeness, split graphs, proper interval graphs}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact