5 Search Results for "Blair, Gordon"


Document
Cluster Editing with Overlapping Communities

Authors: Emmanuel Arrighi, Matthias Bentert, Pål Grønås Drange, Blair D. Sullivan, and Petra Wolf

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)


Abstract
Cluster Editing, also known as correlation clustering, is a well-studied graph modification problem. In this problem, one is given a graph and allowed to perform up to k edge additions and deletions to transform it into a cluster graph, i.e., a graph consisting of a disjoint union of cliques. However, in real-world networks, clusters are often overlapping. For example, in social networks, a person might belong to several communities - e.g. those corresponding to work, school, or neighborhood. Another strong motivation comes from language networks where trying to cluster words with similar usage can be confounded by homonyms, that is, words with multiple meanings like "bat". The recently introduced operation of vertex splitting is one natural approach to incorporating such overlap into Cluster Editing. First used in the context of graph drawing, this operation allows a vertex v to be replaced by two vertices whose combined neighborhood is the neighborhood of v (and thus v can belong to more than one cluster). The problem of transforming a graph into a cluster graph using at most k edge additions, edge deletions, or vertex splits is called Cluster Editing with Vertex Splitting and is known to admit a polynomial kernel with respect to k and an O(9^{k²} + n + m)-time (parameterized) algorithm. However, it was not known whether the problem is NP-hard, a question which was originally asked by Abu-Khzam et al. [Combinatorial Optimization, 2018]. We answer this in the affirmative. We further give an improved algorithm running in O(2^{7klog k} + n + m) time.

Cite as

Emmanuel Arrighi, Matthias Bentert, Pål Grønås Drange, Blair D. Sullivan, and Petra Wolf. Cluster Editing with Overlapping Communities. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{arrighi_et_al:LIPIcs.IPEC.2023.2,
  author =	{Arrighi, Emmanuel and Bentert, Matthias and Drange, P\r{a}l Gr{\o}n\r{a}s and Sullivan, Blair D. and Wolf, Petra},
  title =	{{Cluster Editing with Overlapping Communities}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{2:1--2:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.2},
  URN =		{urn:nbn:de:0030-drops-194218},
  doi =		{10.4230/LIPIcs.IPEC.2023.2},
  annote =	{Keywords: graph modification, correlation clustering, vertex splitting, NP-hardness, parameterized algorithm}
}
Document
PACE Solver Description
PACE Solver Description: Hydra Prime

Authors: Yosuke Mizutani, David Dursteler, and Blair D. Sullivan

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)


Abstract
This note describes our submission to the 2023 PACE Challenge on the computation of twin-width. Our solver Hydra Prime combines modular decomposition with a collection of upper- and lower-bound algorithms, which are alternatingly applied on the prime graphs resulting from the modular decomposition. We introduce two novel approaches which contributed to the solver’s winning performance in the Exact Track: timeline encoding and hydra decomposition. Timeline encoding is a new data structure for computing the width of a given contraction sequence, enabling faster local search; the hydra decomposition is an iterative refinement strategy featuring a small vertex separator.

Cite as

Yosuke Mizutani, David Dursteler, and Blair D. Sullivan. PACE Solver Description: Hydra Prime. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 36:1-36:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{mizutani_et_al:LIPIcs.IPEC.2023.36,
  author =	{Mizutani, Yosuke and Dursteler, David and Sullivan, Blair D.},
  title =	{{PACE Solver Description: Hydra Prime}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{36:1--36:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.36},
  URN =		{urn:nbn:de:0030-drops-194552},
  doi =		{10.4230/LIPIcs.IPEC.2023.36},
  annote =	{Keywords: Twin-width, PACE 2023}
}
Document
Parameterized Complexity of Maximum Happy Set and Densest k-Subgraph

Authors: Yosuke Mizutani and Blair D. Sullivan

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)


Abstract
We present fixed-parameter tractable (FPT) algorithms for two problems, Maximum Happy Set (MaxHS) and Densest k-Subgraph (DkS) - also known as Maximum Edge Happy Set. Given a graph G and an integer k, MaxHS asks for a set S of k vertices such that the number of happy vertices with respect to S is maximized, where a vertex v is happy if v and all its neighbors are in S. We show that MaxHS can be solved in time 𝒪(2^mw ⋅ mw ⋅ k² ⋅ |V(G)|) and 𝒪(8^cw ⋅ k² ⋅ |V(G)|), where mw and cw denote the modular-width and the clique-width of G, respectively. This answers the open questions on fixed-parameter tractability posed in [Asahiro et al., 2021]. The DkS problem asks for a subgraph with k vertices maximizing the number of edges. If we define happy edges as the edges whose endpoints are in S, then DkS can be seen as an edge-variant of MaxHS. In this paper we show that DkS can be solved in time f(nd)⋅|V(G)|^𝒪(1) and 𝒪(2^{cd}⋅ k² ⋅ |V(G)|), where nd and cd denote the neighborhood diversity and the cluster deletion number of G, respectively, and f is some computable function. This result implies that DkS is also fixed-parameter tractable by twin cover number.

Cite as

Yosuke Mizutani and Blair D. Sullivan. Parameterized Complexity of Maximum Happy Set and Densest k-Subgraph. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{mizutani_et_al:LIPIcs.IPEC.2022.23,
  author =	{Mizutani, Yosuke and Sullivan, Blair D.},
  title =	{{Parameterized Complexity of Maximum Happy Set and Densest k-Subgraph}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.23},
  URN =		{urn:nbn:de:0030-drops-173795},
  doi =		{10.4230/LIPIcs.IPEC.2022.23},
  annote =	{Keywords: parameterized algorithms, maximum happy set, densest k-subgraph, modular-width, clique-width, neighborhood diversity, cluster deletion number, twin cover}
}
Document
Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class

Authors: Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian, and Andrew van der Poel

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
We develop a framework for generalizing approximation algorithms from the structural graph algorithm literature so that they apply to graphs somewhat close to that class (a scenario we expect is common when working with real-world networks) while still guaranteeing approximation ratios. The idea is to edit a given graph via vertex- or edge-deletions to put the graph into an algorithmically tractable class, apply known approximation algorithms for that class, and then lift the solution to apply to the original graph. We give a general characterization of when an optimization problem is amenable to this approach, and show that it includes many well-studied graph problems, such as Independent Set, Vertex Cover, Feedback Vertex Set, Minimum Maximal Matching, Chromatic Number, (l-)Dominating Set, Edge (l-)Dominating Set, and Connected Dominating Set. To enable this framework, we develop new editing algorithms that find the approximately-fewest edits required to bring a given graph into one of a few important graph classes (in some cases these are bicriteria algorithms which simultaneously approximate both the number of editing operations and the target parameter of the family). For bounded degeneracy, we obtain an O(r log{n})-approximation and a bicriteria (4,4)-approximation which also extends to a smoother bicriteria trade-off. For bounded treewidth, we obtain a bicriteria (O(log^{1.5} n), O(sqrt{log w}))-approximation, and for bounded pathwidth, we obtain a bicriteria (O(log^{1.5} n), O(sqrt{log w} * log n))-approximation. For treedepth 2 (related to bounded expansion), we obtain a 4-approximation. We also prove complementary hardness-of-approximation results assuming P != NP: in particular, these problems are all log-factor inapproximable, except the last which is not approximable below some constant factor 2 (assuming UGC).

Cite as

Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian, and Andrew van der Poel. Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.ESA.2019.37,
  author =	{Demaine, Erik D. and Goodrich, Timothy D. and Kloster, Kyle and Lavallee, Brian and Liu, Quanquan C. and Sullivan, Blair D. and Vakilian, Ali and van der Poel, Andrew},
  title =	{{Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.37},
  URN =		{urn:nbn:de:0030-drops-111583},
  doi =		{10.4230/LIPIcs.ESA.2019.37},
  annote =	{Keywords: structural rounding, graph editing, approximation algorithms}
}
Document
Modeling for Sustainability (Dagstuhl Seminar 18351)

Authors: Gordon Blair, Betty H. C. Cheng, Lorenz Hilty, and Richard F. Paige

Published in: Dagstuhl Reports, Volume 8, Issue 8 (2019)


Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 18351 "Modeling for Sustainability".

Cite as

Gordon Blair, Betty H. C. Cheng, Lorenz Hilty, and Richard F. Paige. Modeling for Sustainability (Dagstuhl Seminar 18351). In Dagstuhl Reports, Volume 8, Issue 8, pp. 146-168, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@Article{blair_et_al:DagRep.8.8.146,
  author =	{Blair, Gordon and Cheng, Betty H. C. and Hilty, Lorenz and Paige, Richard F.},
  title =	{{Modeling for Sustainability (Dagstuhl Seminar 18351)}},
  pages =	{146--168},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{8},
  number =	{8},
  editor =	{Blair, Gordon and Cheng, Betty H. C. and Hilty, Lorenz and Paige, Richard F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.8.8.146},
  URN =		{urn:nbn:de:0030-drops-102383},
  doi =		{10.4230/DagRep.8.8.146},
  annote =	{Keywords: modeling for sustainability, sustainability dimensions, environmental sustainability, social sustanability, economic sustainability model driven engineering}
}
  • Refine by Author
  • 4 Sullivan, Blair D.
  • 2 Mizutani, Yosuke
  • 1 Arrighi, Emmanuel
  • 1 Bentert, Matthias
  • 1 Blair, Gordon
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Fixed parameter tractability

  • Refine by Keyword
  • 1 NP-hardness
  • 1 PACE 2023
  • 1 Twin-width
  • 1 approximation algorithms
  • 1 clique-width
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2019
  • 2 2023
  • 1 2022

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