4 Search Results for "Johnson, Matthew P."

Document
DOI: 10.4230/LIPIcs.CPM.2019.20
Finding a Small Number of Colourful Components

Authors: Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniël Paulusma, and Stéphane Vialette

Published in: LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)

Abstract
A partition (V_1,...,V_k) of the vertex set of a graph G with a (not necessarily proper) colouring c is colourful if no two vertices in any V_i have the same colour and every set V_i induces a connected graph. The Colourful Partition problem, introduced by Adamaszek and Popa, is to decide whether a coloured graph (G,c) has a colourful partition of size at most k. This problem is related to the Colourful Components problem, introduced by He, Liu and Zhao, which is to decide whether a graph can be modified into a graph whose connected components form a colourful partition by deleting at most p edges. Despite the similarities in their definitions, we show that Colourful Partition and Colourful Components may have different complexities for restricted instances. We tighten known NP-hardness results for both problems by closing a number of complexity gaps. In addition, we prove new hardness and tractability results for Colourful Partition. In particular, we prove that deciding whether a coloured graph (G,c) has a colourful partition of size 2 is NP-complete for coloured planar bipartite graphs of maximum degree 3 and path-width 3, but polynomial-time solvable for coloured graphs of treewidth 2. Rather than performing an ad hoc study, we use our classical complexity results to guide us in undertaking a thorough parameterized study of Colourful Partition. We show that this leads to suitable parameters for obtaining FPT results and moreover prove that Colourful Components and Colourful Partition may have different parameterized complexities, depending on the chosen parameter.
Cite as

Laurent Bulteau, Konrad K. Dabrowski, Guillaume Fertin, Matthew Johnson, Daniël Paulusma, and Stéphane Vialette. Finding a Small Number of Colourful Components. In 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 128, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bulteau_et_al:LIPIcs.CPM.2019.20,
  author =	{Bulteau, Laurent and Dabrowski, Konrad K. and Fertin, Guillaume and Johnson, Matthew and Paulusma, Dani\"{e}l and Vialette, St\'{e}phane},
  title =	{{Finding a Small Number of Colourful Components}},
  booktitle =	{30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Pisanti, Nadia and P. Pissis, Solon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.20},
  URN =		{urn:nbn:de:0030-drops-104914},
  doi =		{10.4230/LIPIcs.CPM.2019.20},
  annote =	{Keywords: Colourful component, colourful partition, tree, treewidth, vertex cover}
}
Document
DOI: 10.4230/OASIcs.ICCSW.2018.11
Harnessing AI For Research

Authors: Matthew Johnson

Published in: OASIcs, Volume 66, 2018 Imperial College Computing Student Workshop (ICCSW 2018)

Abstract
Artificial Intelligence is increasingly being used to both augment existing fields of research and open up new avenues of discovery. From quality control for imaging flow cytometry to computational musicology, modern AI is an exciting new tool for research and thus knowing how to engineer AI systems in a research context is a vital new skill for RSEs to acquire. In this talk, I will outline four different areas of AI: supervised learning, unsupervised learning, interactive learning, and Bayesian learning. For each of these approaches, I will discuss how they typically map to different research problems and explore best practices for RSEs via specific use cases. At the end of the talk, you will have received a high-level overview of AI technologies and their use in research, have seen some cool examples of how AI has been used in a wide range of research areas, and have a good sense of where to go to learn more.
Cite as

Matthew Johnson. Harnessing AI For Research. In 2018 Imperial College Computing Student Workshop (ICCSW 2018). Open Access Series in Informatics (OASIcs), Volume 66, p. 11:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{johnson:OASIcs.ICCSW.2018.11,
  author =	{Johnson, Matthew},
  title =	{{Harnessing AI For Research}},
  booktitle =	{2018 Imperial College Computing Student Workshop (ICCSW 2018)},
  pages =	{11:1--11:1},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-097-2},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{66},
  editor =	{Pirovano, Edoardo and Graversen, Eva},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2018.11},
  URN =		{urn:nbn:de:0030-drops-101922},
  doi =		{10.4230/OASIcs.ICCSW.2018.11},
  annote =	{Keywords: Artificial intelligence}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.12
Deciding the Closure of Inconsistent Rooted Triples Is NP-Complete

Authors: Matthew P. Johnson

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Interpreting three-leaf binary trees or rooted triples as constraints yields an entailment relation, whereby binary trees satisfying some rooted triples must also thus satisfy others, and thence a closure operator, which is known to be polynomial-time computable. This is extended to inconsistent triple sets by defining that a triple is entailed by such a set if it is entailed by any consistent subset of it. Determining whether the closure of an inconsistent rooted triple set can be computed in polynomial time was posed as an open problem in the Isaac Newton Institute's "Phylogenetics" program in 2007. It appears (as NC4) in a collection of such open problems maintained by Mike Steel, and it is the last of that collection's five problems concerning computational complexity to have remained open. We resolve the complexity of computing this closure, proving that its decision version is NP-Complete. In the process, we also prove that detecting the existence of any acyclic B-hyperpath (from specified source to destination) is NP-Complete, in a significantly narrower special case than the version whose minimization problem was recently proven NP-hard by Ritz et al. This implies it is NP-hard to approximate (our special case of) their minimization problem to within any factor.
Cite as

Matthew P. Johnson. Deciding the Closure of Inconsistent Rooted Triples Is NP-Complete. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 12:1-12:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{johnson:LIPIcs.ISAAC.2018.12,
  author =	{Johnson, Matthew P.},
  title =	{{Deciding the Closure of Inconsistent Rooted Triples Is NP-Complete}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{12:1--12:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.12},
  URN =		{urn:nbn:de:0030-drops-99600},
  doi =		{10.4230/LIPIcs.ISAAC.2018.12},
  annote =	{Keywords: phylogenetic trees, rooted triple entailment, NP-Completeness, directed hypergraphs, acyclic induced subgraphs, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.16
Independent Feedback Vertex Set for P_5-free Graphs

Authors: Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma

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

Abstract
The NP-complete problem Feedback Vertex Set is to decide if it is possible, for a given integer k>=0, to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called Independent Feedback Vertex Set and is also NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete and this problem is closely related to the 3-Colouring problem, or equivalently, to the problem of deciding if a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of Independent Feedback Vertex Set for H-free graphs. We prove that it is NP-complete if H contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for P_4-free graphs. We show that it remains in P for P_5-free graphs. We prove analogous results for the Independent Odd Cycle Transversal problem, which asks if a graph has an independent odd cycle transversal of size at most k for a given integer k>=0.
Cite as

Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, and Daniël Paulusma. Independent Feedback Vertex Set for P_5-free Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.ISAAC.2017.16,
  author =	{Bonamy, Marthe and Dabrowski, Konrad K. and Feghali, Carl and Johnson, Matthew and Paulusma, Dani\"{e}l},
  title =	{{Independent Feedback Vertex Set for P\underline5-free Graphs}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{16:1--16: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.16},
  URN =		{urn:nbn:de:0030-drops-82308},
  doi =		{10.4230/LIPIcs.ISAAC.2017.16},
  annote =	{Keywords: feedback vertex set, odd cycle transversal, independent set, H-free graph}
}
  • Refine by Author
  • 3 Johnson, Matthew
  • 2 Dabrowski, Konrad K.
  • 2 Paulusma, Daniël
  • 1 Bonamy, Marthe
  • 1 Bulteau, Laurent
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Molecular evolution
  • 1 Computing methodologies → Artificial intelligence
  • 1 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Hypergraphs
  • 1 Mathematics of computing → Trees
  • Show More...

  • Refine by Keyword
  • 1 Artificial intelligence
  • 1 Colourful component
  • 1 H-free graph
  • 1 NP-Completeness
  • 1 acyclic induced subgraphs
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2019
  • 1 2017
  • 1 2018

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