2 Search Results for "Van Pham, Trung"


Document
A Complexity Dichotomy for Poset Constraint Satisfaction

Authors: Michael Kompatscher and Trung Van Pham

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)


Abstract
We determine the complexity of all constraint satisfaction problems over partial orders, in particular we show that every such problem is NP-complete or can be solved in polynomial time. This result generalises the complexity dichotomy for temporal constraint satisfaction problems by Bodirsky and Kára. We apply the so called universal-algebraic approach together with tools from model theory and Ramsey theory to prove our result. In the course of this analysis we also establish a structural dichotomy regarding the model theoretic properties of the reducts of the random partial order.

Cite as

Michael Kompatscher and Trung Van Pham. A Complexity Dichotomy for Poset Constraint Satisfaction. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 47:1-47:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{kompatscher_et_al:LIPIcs.STACS.2017.47,
  author =	{Kompatscher, Michael and Pham, Trung Van},
  title =	{{A Complexity Dichotomy for Poset Constraint Satisfaction}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{47:1--47:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.47},
  URN =		{urn:nbn:de:0030-drops-69850},
  doi =		{10.4230/LIPIcs.STACS.2017.47},
  annote =	{Keywords: Constraint Satisfaction, Random Partial Order, Computational Complexity, Universal Algebra, Ramsey Theory}
}
Document
The Complexity of Phylogeny Constraint Satisfaction

Authors: Manuel Bodirsky, Peter Jonsson, and Trung Van Pham

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)


Abstract
We systematically study the computational complexity of a broad class of computational problems in phylogenetic reconstruction. The class contains for example the rooted triple consistency problem, forbidden subtree problems, the quartet consistency problem, and many other problems studied in the bioinformatics literature. The studied problems can be described as constraint satisfaction problems where the constraints have a first-order definition over the rooted triple relation. We show that every such phylogeny problem can be solved in polynomial time or is NP-complete. On the algorithmic side, we generalize a well-known polynomial-time algorithm of Aho, Sagiv, Szymanski, and Ullman for the rooted triple consistency problem. Our algorithm repeatedly solves linear equation systems to construct a solution in polynomial time. We then show that every phylogeny problem that cannot be solved by our algorithm is NP-complete. Our classification establishes a dichotomy for a large class of infinite structures that we believe is of independent interest in universal algebra, model theory, and topology. The proof of our main result combines results and techniques from various research areas: a recent classification of the model-complete cores of the reducts of the homogeneous binary branching C-relation, Leeb’s Ramsey theorem for rooted trees, and universal algebra.

Cite as

Manuel Bodirsky, Peter Jonsson, and Trung Van Pham. The Complexity of Phylogeny Constraint Satisfaction. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 20:1-20:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{bodirsky_et_al:LIPIcs.STACS.2016.20,
  author =	{Bodirsky, Manuel and Jonsson, Peter and Van Pham, Trung},
  title =	{{The Complexity of Phylogeny Constraint Satisfaction}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{20:1--20:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.20},
  URN =		{urn:nbn:de:0030-drops-57218},
  doi =		{10.4230/LIPIcs.STACS.2016.20},
  annote =	{Keywords: constraint satisfaction problems, computational complexity, phylogenetic reconstruction, ramsey theory, model theory}
}
  • Refine by Author
  • 1 Bodirsky, Manuel
  • 1 Jonsson, Peter
  • 1 Kompatscher, Michael
  • 1 Pham, Trung Van
  • 1 Van Pham, Trung

  • Refine by Classification

  • Refine by Keyword
  • 1 Computational Complexity
  • 1 Constraint Satisfaction
  • 1 Ramsey Theory
  • 1 Random Partial Order
  • 1 Universal Algebra
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2017

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