Search Results

Documents authored by Bazgan, Cristina

Document
DOI: 10.4230/LIPIcs.SWAT.2024.6
Destroying Densest Subgraphs Is Hard

Authors: Cristina Bazgan, André Nichterlein, and Sofia Vazquez Alferez

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
We analyze the computational complexity of the following computational problems called Bounded-Density Edge Deletion and Bounded-Density Vertex Deletion: Given a graph G, a budget k and a target density τ_ρ, are there k edges (k vertices) whose removal from G results in a graph where the densest subgraph has density at most τ_ρ? Here, the density of a graph is the number of its edges divided by the number of its vertices. We prove that both problems are polynomial-time solvable on trees and cliques but are NP-complete on planar bipartite graphs and split graphs. From a parameterized point of view, we show that both problems are fixed-parameter tractable with respect to the vertex cover number but W[1]-hard with respect to the solution size. Furthermore, we prove that Bounded-Density Edge Deletion is W[1]-hard with respect to the feedback edge number, demonstrating that the problem remains hard on very sparse graphs.
Cite as

Cristina Bazgan, André Nichterlein, and Sofia Vazquez Alferez. Destroying Densest Subgraphs Is Hard. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bazgan_et_al:LIPIcs.SWAT.2024.6,
  author =	{Bazgan, Cristina and Nichterlein, Andr\'{e} and Vazquez Alferez, Sofia},
  title =	{{Destroying Densest Subgraphs Is Hard}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.6},
  URN =		{urn:nbn:de:0030-drops-200461},
  doi =		{10.4230/LIPIcs.SWAT.2024.6},
  annote =	{Keywords: Graph modification problems, NP-hardness, fixed-parameter tractability, W-hardness, special graph classes}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.13
Dense Graph Partitioning on Sparse and Dense Graphs

Authors: Cristina Bazgan, Katrin Casel, and Pierre Cazals

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
We consider the problem of partitioning a graph into a non-fixed number of non-overlapping subgraphs of maximum density. The density of a partition is the sum of the densities of the subgraphs, where the density of a subgraph is half its average degree, that is, the ratio of its number of edges and its number of vertices. This problem, called Dense Graph Partition, is known to be NP-hard on general graphs and polynomial-time solvable on trees, and polynomial-time 2-approximable. In this paper we study the restriction of Dense Graph Partition to particular sparse and dense graph classes. In particular, we prove that it is NP-hard on dense bipartite graphs as well as on cubic graphs. On dense graphs on n vertices, it is polynomial-time solvable on graphs with minimum degree n-3 and NP-hard on (n-4)-regular graphs. We prove that it is polynomial-time 4/3-approximable on cubic graphs and admits an efficient polynomial-time approximation scheme on graphs of minimum degree n-t for any constant t ≥ 4.
Cite as

Cristina Bazgan, Katrin Casel, and Pierre Cazals. Dense Graph Partitioning on Sparse and Dense Graphs. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bazgan_et_al:LIPIcs.SWAT.2022.13,
  author =	{Bazgan, Cristina and Casel, Katrin and Cazals, Pierre},
  title =	{{Dense Graph Partitioning on Sparse and Dense Graphs}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.13},
  URN =		{urn:nbn:de:0030-drops-161732},
  doi =		{10.4230/LIPIcs.SWAT.2022.13},
  annote =	{Keywords: NP-hardness, approximation, density, graph partitioning, bipartite graphs, cubic graphs, dense graphs}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.4
Building Clusters with Lower-Bounded Sizes

Authors: Faisal Abu-Khzam, Cristina Bazgan, Katrin Casel, and Henning Fernau

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
Classical clustering problems search for a partition of objects into a fixed number of clusters. In many scenarios however the number of clusters is not known or necessarily fixed. Further, clusters are sometimes only considered to be of significance if they have a certain size. We discuss clustering into sets of minimum cardinality k without a fixed number of sets and present a general model for these types of problems. This general framework allows the comparison of different measures to assess the quality of a clustering. We specifically consider nine quality-measures and classify the complexity of the resulting problems with respect to k. Further, we derive some polynomial-time solvable cases for k = 2 with connections to matching-type problems which, among other graph problems, then are used to compute approximations for larger values of k.
Cite as

Faisal Abu-Khzam, Cristina Bazgan, Katrin Casel, and Henning Fernau. Building Clusters with Lower-Bounded Sizes. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{abukhzam_et_al:LIPIcs.ISAAC.2016.4,
  author =	{Abu-Khzam, Faisal and Bazgan, Cristina and Casel, Katrin and Fernau, Henning},
  title =	{{Building Clusters with Lower-Bounded Sizes}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{4:1--4:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.4},
  URN =		{urn:nbn:de:0030-drops-67742},
  doi =		{10.4230/LIPIcs.ISAAC.2016.4},
  annote =	{Keywords: Clustering, Approximation Algorithms, Complexity, Matching}
}
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 Imprint Privacy Contact