Search Results

Documents authored by Papadopoulos, Charis

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.IPEC.2018.20
Subset Feedback Vertex Set on Graphs of Bounded Independent Set Size

Authors: Charis Papadopoulos and Spyridon Tzimas

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
The (Weighted) Subset Feedback Vertex Set problem is a generalization of the classical Feedback Vertex Set problem and asks for a vertex set of minimum (weight) size that intersects all cycles containing a vertex of a predescribed set of vertices. Although the two problems exhibit different computational complexity on split graphs, no similar characterization is known on other classes of graphs. Towards the understanding of the complexity difference between the two problems, it is natural to study the importance of a structural graph parameter. Here we consider graphs of bounded independent set number for which it is known that Weighted Feedback Vertex Set can be solved in polynomial time. We provide a dichotomy result with respect to the size of a maximum independent set. In particular we show that Weighted Subset Feedback Vertex Set can be solved in polynomial time for graphs of independent set number at most three, whereas we prove that the problem remains NP-hard for graphs of independent set number four. Moreover, we show that the (unweighted) Subset Feedback Vertex Set problem can be solved in polynomial time on graphs of bounded independent set number by giving an algorithm with running time n^{O(d)}, where d is the size of a maximum independent set of the input graph. To complement our results, we demonstrate how our ideas can be extended to other terminal set problems on graphs of bounded independent set size. Based on our findings for Subset Feedback Vertex Set, we settle the complexity of Node Multiway Cut, a terminal set problem that asks for a vertex set of minimum size that intersects all paths connecting any two terminals, as well as its variants where nodes are weighted and/or the terminals are deletable, for every value of the given independent set number.
Cite as

Charis Papadopoulos and Spyridon Tzimas. Subset Feedback Vertex Set on Graphs of Bounded Independent Set Size. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{papadopoulos_et_al:LIPIcs.IPEC.2018.20,
  author =	{Papadopoulos, Charis and Tzimas, Spyridon},
  title =	{{Subset Feedback Vertex Set on Graphs of Bounded Independent Set Size}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.20},
  URN =		{urn:nbn:de:0030-drops-102216},
  doi =		{10.4230/LIPIcs.IPEC.2018.20},
  annote =	{Keywords: Subset Feedback Vertex Set, Node Multiway Cut, Terminal Set problem, polynomial-time algorithm, NP-completeness, W\lbrack1\rbrack-hardness, graphs of bounded independent set size}
}
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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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