5 Search Results for "Egri, L�szl�"


Document
Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs

Authors: Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)


Abstract
A homomorphism from a graph G to a graph H is an edge-preserving mapping from V(G) to V(H). Let H be a fixed graph with possible loops. In the list homomorphism problem, denoted by LHom(H), we are given a graph G, whose every vertex v is assigned with a list L(v) of vertices of H. We ask whether there exists a homomorphism h from G to H, which respects lists L, i.e., for every v ∈ V(G) it holds that h(v) ∈ L(v). The complexity dichotomy for LHom(H) was proven by Feder, Hell, and Huang [JGT 2003]. The authors showed that the problem is polynomial-time solvable if H belongs to the class called bi-arc graphs, and for all other graphs H it is NP-complete. We are interested in the complexity of the LHom(H) problem, parameterized by the treewidth of the input graph. This problem was investigated by Egri, Marx, and Rzążewski [STACS 2018], who obtained tight complexity bounds for the special case of reflexive graphs H, i.e., if every vertex has a loop. In this paper we extend and generalize their results for all relevant graphs H, i.e., those, for which the LHom(H) problem is NP-hard. For every such H we find a constant k = k(H), such that the LHom(H) problem on instances G with n vertices and treewidth t - can be solved in time k^t ⋅ n^𝒪(1), provided that G is given along with a tree decomposition of width t, - cannot be solved in time (k-ε)^t ⋅ n^𝒪(1), for any ε > 0, unless the SETH fails. For some graphs H the value of k(H) is much smaller than the trivial upper bound, i.e., |V(H)|. Obtaining matching upper and lower bounds shows that the set of algorithmic tools that we have discovered cannot be extended in order to obtain faster algorithms for LHom(H) in bounded-treewidth graphs. Furthermore, neither the algorithm, nor the proof of the lower bound, is very specific to treewidth. We believe that they can be used for other variants of the LHom(H) problem, e.g. with different parameterizations.

Cite as

Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski. Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 74:1-74:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{okrasa_et_al:LIPIcs.ESA.2020.74,
  author =	{Okrasa, Karolina and Piecyk, Marta and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Full Complexity Classification of the List Homomorphism Problem for Bounded-Treewidth Graphs}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{74:1--74:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.74},
  URN =		{urn:nbn:de:0030-drops-129402},
  doi =		{10.4230/LIPIcs.ESA.2020.74},
  annote =	{Keywords: list homomorphisms, fine-grained complexity, SETH, treewidth}
}
Document
Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization

Authors: László Egri, Dániel Marx, and Pawel Rzazewski

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)


Abstract
In the list homomorphism problem, the input consists of two graphs G and H, together with a list L(v) \subseteq V(H) for every vertex v \in V(G). The task is to find a homomorphism phi:V(G) -> V(H) respecting the lists, that is, we have that phi(v) \in L(v) for every v \in V(H) and if u and v are adjacent in G, then phi(u) and phi(v) are adjacent in H. If H is a fixed graph, then the problem is denoted LHom(H). We consider the reflexive version of the problem, where we assume that every vertex in H has a self-loop. If is known that reflexive LHom(H) is polynomial-time solvable if H is an interval graph and it is NP-complete otherwise [Feder and Hell, JCTB 1998]. We explore the complexity of the problem parameterized by the treewidth tw(G) of the input graph G. If a tree decomposition of G of width tw(G) is given in the input, then the problem can be solved in time |V(H)|^{tw(G)} n^{O(1)} by naive dynamic programming. Our main result completely reveals when and by exactly how much this naive algorithm can be improved. We introduce a simple combinatorial invariant i^*(H), which is based on the existence of decompositions and incomparable sets, and show that this number should appear as the base of the exponent in the best possible running time. Specifically, we prove for every fixed non-interval graph H that * If a tree decomposition of width tw(G) is given in the input, then the problem can be solved in time i^*(H)^{tw(G)} n^{O(1)}. * Assuming the Strong Exponential-Time Hypothesis (SETH), the probem cannot be solved in time (i^*(H)-epsilon)^{tw(G)} n^{O(1)} for any epsilon>0. Thus by matching upper and lower bounds, our result exactly characterizes for every fixed H the complexity of reflexive LHom(H) parameterized by treewidth.

Cite as

László Egri, Dániel Marx, and Pawel Rzazewski. Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{egri_et_al:LIPIcs.STACS.2018.27,
  author =	{Egri, L\'{a}szl\'{o} and Marx, D\'{a}niel and Rzazewski, Pawel},
  title =	{{Finding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf 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.2018.27},
  URN =		{urn:nbn:de:0030-drops-84867},
  doi =		{10.4230/LIPIcs.STACS.2018.27},
  annote =	{Keywords: graph homomorphism, list homomorphism, reflexive graph, treewidth}
}
Document
Fixed-Parameter Approximability of Boolean MinCSPs

Authors: Édouard Bonnet, László Egri, and Dániel Marx

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)


Abstract
The minimum unsatisfiability version of a constraint satisfaction problem (CSP) asks for an assignment where the number of unsatisfied constraints is minimum possible, or equivalently, asks for a minimum-size set of constraints whose deletion makes the instance satisfiable. For a finite set Gamma of constraints, we denote by CSP(Gamma) the restriction of the problem where each constraint is from Gamma. The polynomial-time solvability and the polynomial-time approximability of CSP(Gamma) were fully characterized by [Khanna et al. SICOMP 2000]. Here we study the fixed-parameter (FP-) approximability of the problem: given an instance and an integer k, one has to find a solution of size at most g(k) in time f(k)n^{O(1)} if a solution of size at most k exists. We especially focus on the case of constant-factor FP-approximability. Our main result classifies each finite constraint language Gamma into one of three classes: (1) CSP(Gamma) has a constant-factor FP-approximation; (2) CSP(Gamma) has a (constant-factor) FP-approximation if and only if Nearest Codeword has a (constant-factor) FP-approximation; (3) CSP(Gamma) has no FP-approximation, unless FPT=W[P]. We show that problems in the second class do not have constant-factor FP-approximations if both the Exponential-Time Hypothesis (ETH) and the Linear PCP Conjecture (LPC) hold. We also show that such an approximation would imply the existence of an FP-approximation for the k-Densest Subgraph problem with ratio 1-epsilon for any epsilon>0.

Cite as

Édouard Bonnet, László Egri, and Dániel Marx. Fixed-Parameter Approximability of Boolean MinCSPs. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ESA.2016.18,
  author =	{Bonnet, \'{E}douard and Egri, L\'{a}szl\'{o} and Marx, D\'{a}niel},
  title =	{{Fixed-Parameter Approximability of Boolean MinCSPs}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.18},
  URN =		{urn:nbn:de:0030-drops-63694},
  doi =		{10.4230/LIPIcs.ESA.2016.18},
  annote =	{Keywords: constraint satisfaction problems, approximability, fixed-parameter tractability}
}
Document
On Constraint Satisfaction Problems below P*

Authors: László Egri

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)


Abstract
Symmetric Datalog, a fragment of the logic programming language Datalog, is conjectured to capture all constraint satisfaction problems (CSP) in L. Therefore developing tools that help us understand whether or not a CSP can be defined in symmetric Datalog is an important task. It is widely known that a CSP is definable in Datalog and linear Datalog iff that CSP has bounded treewidth and bounded pathwidth duality, respectively. In the case of symmetric Datalog, Bulatov, Krokhin and Larose ask for such a duality [2008]. We provide two such dualities, and give applications. In particular, we give a short and simple new proof of the result of Dalmau and Larose that "Maltsev + Datalog -> symmetric Datalog" [2008]. In the second part of the paper, we provide some evidence for the conjecture of Dalmau [2002] that every CSP in NL is definable in linear Datalog. Our results also show that a wide class of CSPs ---CSPs which do not have bounded pathwidth duality (e.g. the P-complete Horn-3Sat problem)--- cannot be defined by any polynomial size family of monotone read-once nondeterministic branching programs. We consider the following restrictions of the previous models: read-once linDat(suc) (1-linDat(suc)), and monotone readonce nondeterministic branching programs (mnBP1). Although restricted, these models can still define NL-complete problems such as directed st-Connectivity, and also nontrivial problems in NL which are not definable in linear Datalog. We show that any CSP definable by a 1-linDat(suc) program or by a poly-size family of mnBP1s can also be defined by a linear Datalog program. It also follows that a wide class of CSPs ---CSPs which do not have bounded pathwidth duality (e.g. the P-complete Horn-3Sat problem)--- cannot be defined by any 1-linDat(suc) program or by any poly-size family of mnBP1s.

Cite as

László Egri. On Constraint Satisfaction Problems below P*. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 203-217, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{egri:LIPIcs.CSL.2011.203,
  author =	{Egri, L\'{a}szl\'{o}},
  title =	{{On Constraint Satisfaction Problems below P*}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{203--217},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.203},
  URN =		{urn:nbn:de:0030-drops-32320},
  doi =		{10.4230/LIPIcs.CSL.2011.203},
  annote =	{Keywords: constraint satisfaction problems, complexity classes, Datalog fragments}
}
Document
The Complexity of the List Homomorphism Problem for Graphs

Authors: László Egri, Andrei Krokhin, Benoit Larose, and Pascal Tesson

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)


Abstract
We completely classify the computational complexity of the list $\bH$-colouring problem for graphs (with possible loops) in combinatorial and algebraic terms: for every graph $\bH$ the problem is either NP-complete, NL-complete, L-complete or is first-order definable; descriptive complexity equivalents are given as well via Datalog and its fragments. Our algebraic characterisations match important conjectures in the study of constraint satisfaction problems.

Cite as

László Egri, Andrei Krokhin, Benoit Larose, and Pascal Tesson. The Complexity of the List Homomorphism Problem for Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 335-346, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)


Copy BibTex To Clipboard

@InProceedings{egri_et_al:LIPIcs.STACS.2010.2467,
  author =	{Egri, L\'{a}szl\'{o} and Krokhin, Andrei and Larose, Benoit and Tesson, Pascal},
  title =	{{The Complexity of the List Homomorphism Problem for Graphs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{335--346},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2467},
  URN =		{urn:nbn:de:0030-drops-24675},
  doi =		{10.4230/LIPIcs.STACS.2010.2467},
  annote =	{Keywords: Graph homomorphism, constraint satisfaction problem, complexity, universal algebra, Datalog}
}
  • Refine by Author
  • 4 Egri, László
  • 2 Marx, Dániel
  • 1 Bonnet, Édouard
  • 1 Krokhin, Andrei
  • 1 Larose, Benoit
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph coloring
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 2 constraint satisfaction problems
  • 2 treewidth
  • 1 Datalog
  • 1 Datalog fragments
  • 1 Graph homomorphism
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2010
  • 1 2011
  • 1 2016
  • 1 2018
  • 1 2020

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