8 Search Results for "Pieterse, Astrid"

Document
DOI: 10.4230/LIPIcs.ISAAC.2020.58
Sparsification Lower Bounds for List H-Coloring

Authors: Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, and Paweł Rzążewski

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
We investigate the List H-Coloring problem, the generalization of graph coloring that asks whether an input graph G admits a homomorphism to the undirected graph H (possibly with loops), such that each vertex v ∈ V(G) is mapped to a vertex on its list L(v) ⊆ V(H). An important result by Feder, Hell, and Huang [JGT 2003] states that List H-Coloring is polynomial-time solvable if H is a so-called bi-arc graph, and NP-complete otherwise. We investigate the NP-complete cases of the problem from the perspective of polynomial-time sparsification: can an n-vertex instance be efficiently reduced to an equivalent instance of bitsize 𝒪(n^(2-ε)) for some ε > 0? We prove that if H is not a bi-arc graph, then List H-Coloring does not admit such a sparsification algorithm unless NP ⊆ coNP/poly. Our proofs combine techniques from kernelization lower bounds with a study of the structure of graphs H which are not bi-arc graphs.
Cite as

Hubie Chen, Bart M. P. Jansen, Karolina Okrasa, Astrid Pieterse, and Paweł Rzążewski. Sparsification Lower Bounds for List H-Coloring. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 58:1-58:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2020.58,
  author =	{Chen, Hubie and Jansen, Bart M. P. and Okrasa, Karolina and Pieterse, Astrid and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{Sparsification Lower Bounds for List H-Coloring}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{58:1--58:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.58},
  URN =		{urn:nbn:de:0030-drops-134027},
  doi =		{10.4230/LIPIcs.ISAAC.2020.58},
  annote =	{Keywords: List H-Coloring, Sparsification, Constraint Satisfaction Problem}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.60
Approximate Turing Kernelization for Problems Parameterized by Treewidth

Authors: Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse

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

Abstract
We extend the notion of lossy kernelization, introduced by Lokshtanov et al. [STOC 2017], to approximate Turing kernelization. An α-approximate Turing kernel for a parameterized optimization problem is a polynomial-time algorithm that, when given access to an oracle that outputs c-approximate solutions in 𝒪(1) time, obtains an α ⋅ c-approximate solution to the considered problem, using calls to the oracle of size at most f(k) for some function f that only depends on the parameter. Using this definition, we show that Independent Set parameterized by treewidth 𝓁 has a (1+ε)-approximate Turing kernel with 𝒪(𝓁²/ε) vertices, answering an open question posed by Lokshtanov et al. [STOC 2017]. Furthermore, we give (1+ε)-approximate Turing kernels for the following graph problems parameterized by treewidth: Vertex Cover, Edge Clique Cover, Edge-Disjoint Triangle Packing and Connected Vertex Cover. We generalize the result for Independent Set and Vertex Cover, by showing that all graph problems that we will call friendly admit (1+ε)-approximate Turing kernels of polynomial size when parameterized by treewidth. We use this to obtain approximate Turing kernels for Vertex-Disjoint H-packing for connected graphs H, Clique Cover, Feedback Vertex Set and Edge Dominating Set.
Cite as

Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse. Approximate Turing Kernelization for Problems Parameterized by Treewidth. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 60:1-60:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hols_et_al:LIPIcs.ESA.2020.60,
  author =	{Hols, Eva-Maria C. and Kratsch, Stefan and Pieterse, Astrid},
  title =	{{Approximate Turing Kernelization for Problems Parameterized by Treewidth}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{60:1--60:23},
  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.60},
  URN =		{urn:nbn:de:0030-drops-129261},
  doi =		{10.4230/LIPIcs.ESA.2020.60},
  annote =	{Keywords: Approximation, Turing kernelization, Graph problems, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.36
Elimination Distances, Blocking Sets, and Kernels for Vertex Cover

Authors: Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
The Vertex Cover problem plays an essential role in the study of polynomial kernelization in parameterized complexity, i.e., the study of provable and efficient preprocessing for NP-hard problems. Motivated by the great variety of positive and negative results for kernelization for Vertex Cover subject to different parameters and graph classes, we seek to unify and generalize them using so-called blocking sets. A blocking set is a set of vertices such that no optimal vertex cover contains all vertices in the blocking set, and the study of minimal blocking sets played implicit and explicit roles in many existing results. We show that in the most-studied setting, parameterized by the size of a deletion set to a specified graph class ?, bounded minimal blocking set size is necessary but not sufficient to get a polynomial kernelization. Under mild technical assumptions, bounded minimal blocking set size is showed to allow an essentially tight efficient reduction in the number of connected components. We then determine the exact maximum size of minimal blocking sets for graphs of bounded elimination distance to any hereditary class ?, including the case of graphs of bounded treedepth. We get similar but not tight bounds for certain non-hereditary classes ?, including the class ?_{LP} of graphs where integral and fractional vertex cover size coincide. These bounds allow us to derive polynomial kernels for Vertex Cover parameterized by the size of a deletion set to graphs of bounded elimination distance to, e.g., forest, bipartite, or ?_{LP} graphs.
Cite as

Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse. Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hols_et_al:LIPIcs.STACS.2020.36,
  author =	{Hols, Eva-Maria C. and Kratsch, Stefan and Pieterse, Astrid},
  title =	{{Elimination Distances, Blocking Sets, and Kernels for Vertex Cover}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{36:1--36:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.36},
  URN =		{urn:nbn:de:0030-drops-118974},
  doi =		{10.4230/LIPIcs.STACS.2020.36},
  annote =	{Keywords: Vertex Cover, kernelization, blocking sets, elimination distance, structural parameters}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.15
Best-Case and Worst-Case Sparsifiability of Boolean CSPs

Authors: Hubie Chen, Bart M. P. Jansen, and Astrid Pieterse

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
We continue the investigation of polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number of constraints in a problem instance without changing the answer, such that a bound on the number of resulting constraints can be given in terms of the number of variables n. We investigate how the worst-case sparsification size depends on the types of constraints allowed in the problem formulation (the constraint language). Two algorithmic results are presented. The first result essentially shows that for any arity k, the only constraint type for which no nontrivial sparsification is possible has exactly one falsifying assignment, and corresponds to logical OR (up to negations). Our second result concerns linear sparsification, that is, a reduction to an equivalent instance with O(n) constraints. Using linear algebra over rings of integers modulo prime powers, we give an elegant necessary and sufficient condition for a constraint type to be captured by a degree-1 polynomial over such a ring, which yields linear sparsifications. The combination of these algorithmic results allows us to prove two characterizations that capture the optimal sparsification sizes for a range of Boolean CSPs. For NP-complete Boolean CSPs whose constraints are symmetric (the satisfaction depends only on the number of 1 values in the assignment, not on their positions), we give a complete characterization of which constraint languages allow for a linear sparsification. For Boolean CSPs in which every constraint has arity at most three, we characterize the optimal size of sparsifications in terms of the largest OR that can be expressed by the constraint language.
Cite as

Hubie Chen, Bart M. P. Jansen, and Astrid Pieterse. Best-Case and Worst-Case Sparsifiability of Boolean CSPs. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.IPEC.2018.15,
  author =	{Chen, Hubie and Jansen, Bart M. P. and Pieterse, Astrid},
  title =	{{Best-Case and Worst-Case Sparsifiability of Boolean CSPs}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.15},
  URN =		{urn:nbn:de:0030-drops-102169},
  doi =		{10.4230/LIPIcs.IPEC.2018.15},
  annote =	{Keywords: constraint satisfaction problems, kernelization, sparsification, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.48
Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations

Authors: Bart M. P. Jansen and Astrid Pieterse

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of graphs F, the F-Deletion problem is the following: given a graph G and integer k, is it possible to delete k vertices from G to ensure the resulting graph does not contain any graph from F as a minor? Earlier work by Fomin, Lokshtanov, Misra, and Saurabh [FOCS'12] showed that when F contains a planar graph, an instance (G,k) can be reduced in polynomial time to an equivalent one of size k^{O(1)}. In this work we focus on structural measures of the complexity of an instance, with the aim of giving nontrivial preprocessing guarantees for instances whose solutions are large. Motivated by several impossibility results, we parameterize the F-Deletion problem by the size of a vertex modulator whose removal results in a graph of constant treedepth eta. We prove that for each set F of connected graphs and constant eta, the F-Deletion problem parameterized by the size of a treedepth-eta modulator has a polynomial kernel. Our kernelization is fully explicit and does not depend on protrusion reduction or well-quasi-ordering, which are sources of algorithmic non-constructivity in earlier works on F-Deletion. Our main technical contribution is to analyze how models of a forbidden minor in a graph G with modulator X, interact with the various connected components of G-X. Using the language of labeled minors, we analyze the fragments of potential forbidden minor models that can remain after removing an optimal F-Deletion solution from a single connected component of G-X. By bounding the number of different types of behavior that can occur by a polynomial in |X|, we obtain a polynomial kernel using a recursive preprocessing strategy. Our results extend earlier work for specific instances of F-Deletion such as Vertex Cover and Feedback Vertex Set. It also generalizes earlier preprocessing results for F-Deletion parameterized by a vertex cover, which is a treedepth-one modulator.
Cite as

Bart M. P. Jansen and Astrid Pieterse. Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ESA.2018.48,
  author =	{Jansen, Bart M. P. and Pieterse, Astrid},
  title =	{{Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah 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.2018.48},
  URN =		{urn:nbn:de:0030-drops-95119},
  doi =		{10.4230/LIPIcs.ESA.2018.48},
  annote =	{Keywords: Kernelization, F-minor free deletion, Treedepth modulator, Structural parameterization}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.22
Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials

Authors: Bart M. P. Jansen and Astrid Pieterse

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
The theory of kernelization can be used to rigorously analyze data reduction for graph coloring problems. Here, the aim is to reduce a q-Coloring input to an equivalent but smaller input whose size is provably bounded in terms of structural properties, such as the size of a minimum vertex cover. In this paper we settle two open problems about data reduction for q-Coloring. First, we use a recent technique of finding redundant constraints by representing them as low-degree polynomials, to obtain a kernel of bitsize O(k^(q-1) log k) for q-Coloring parameterized by Vertex Cover for any q >= 3. This size bound is optimal up to k^o(1) factors assuming NP is not a subset of coNP/poly, and improves on the previous-best kernel of size O(k^q). Our second result shows that 3-Coloring does not admit non-trivial sparsification: assuming NP is not a subset of coNP/poly, the parameterization by the number of vertices n admits no (generalized) kernel of size O(n^(2-e)) for any e > 0. Previously, such a lower bound was only known for coloring with q >= 4 colors.
Cite as

Bart M. P. Jansen and Astrid Pieterse. Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 22:1-22:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.IPEC.2017.22,
  author =	{Jansen, Bart M. P. and Pieterse, Astrid},
  title =	{{Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{22:1--22:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.22},
  URN =		{urn:nbn:de:0030-drops-85500},
  doi =		{10.4230/LIPIcs.IPEC.2017.22},
  annote =	{Keywords: graph coloring, kernelization, sparsification}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.71
Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials

Authors: Bart M. P. Jansen and Astrid Pieterse

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
This paper analyzes to what extent it is possible to efficiently reduce the number of clauses in NP-hard satisfiability problems, without changing the answer. Upper and lower bounds are established using the concept of kernelization. Existing results show that if NP is not contained in coNP/poly, no efficient preprocessing algorithm can reduce n-variable instances of CNF-SAT with d literals per clause, to equivalent instances with O(n^{d-epsilon}) bits for any epsilon > 0. For the Not-All-Equal SAT problem, a compression to size tilde-O(n^{d-1}) exists. We put these results in a common framework by analyzing the compressibility of binary CSPs. We characterize constraint types based on the minimum degree of multivariate polynomials whose roots correspond to the satisfying assignments, obtaining (nearly) matching upper and lower bounds in several settings. Our lower bounds show that not just the number of constraints, but also the encoding size of individual constraints plays an important role. For example, for Exact Satisfiability with unbounded clause length it is possible to efficiently reduce the number of constraints to n+1, yet no polynomial-time algorithm can reduce to an equivalent instance with O(n^{2-epsilon}) bits for any epsilon > 0, unless NP is contained in coNP/poly.
Cite as

Bart M. P. Jansen and Astrid Pieterse. Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.MFCS.2016.71,
  author =	{Jansen, Bart M. P. and Pieterse, Astrid},
  title =	{{Optimal Sparsification for Some Binary CSPs Using Low-Degree Polynomials}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{71:1--71:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.71},
  URN =		{urn:nbn:de:0030-drops-64821},
  doi =		{10.4230/LIPIcs.MFCS.2016.71},
  annote =	{Keywords: constraint satisfaction problem, sparsification, satisfiability, kernelization}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2015.163
Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT

Authors: Bart M. P. Jansen and Astrid Pieterse

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract
We present several sparsification lower and upper bounds for classic problems in graph theory and logic. For the problems 4-Coloring, (Directed) Hamiltonian Cycle, and (Connected) Dominating Set, we prove that there is no polynomial-time algorithm that reduces any n-vertex input to an equivalent instance, of an arbitrary problem, with bitsize O(n^{2-epsilon}) for epsilon > 0, unless NP is a subset of coNP/poly and the polynomial-time hierarchy collapses. These results imply that existing linear-vertex kernels for k-Nonblocker and k-Max Leaf Spanning Tree (the parametric duals of (Connected) Dominating Set) cannot be improved to have O(k^{2-epsilon}) edges, unless NP is a subset of NP/poly. We also present a positive result and exhibit a non-trivial sparsification algorithm for d-Not-All-Equal-SAT. We give an algorithm that reduces an n-variable input with clauses of size at most d to an equivalent input with O(n^{d-1}) clauses, for any fixed d. Our algorithm is based on a linear-algebraic proof of Lovász that bounds the number of hyperedges in critically 3-chromatic d-uniform n-vertex hypergraphs by binom{n}{d-1}. We show that our kernel is tight under the assumption that NP is not a subset of NP/poly.
Cite as

Bart M. P. Jansen and Astrid Pieterse. Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 163-174, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.IPEC.2015.163,
  author =	{Jansen, Bart M. P. and Pieterse, Astrid},
  title =	{{Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{163--174},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.163},
  URN =		{urn:nbn:de:0030-drops-55806},
  doi =		{10.4230/LIPIcs.IPEC.2015.163},
  annote =	{Keywords: sparsification, graph coloring, Hamiltonian cycle, satisfiability}
}
  • Refine by Author
  • 8 Pieterse, Astrid
  • 6 Jansen, Bart M. P.
  • 2 Chen, Hubie
  • 2 Hols, Eva-Maria C.
  • 2 Kratsch, Stefan
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Computing methodologies → Symbolic and algebraic algorithms
  • 1 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 4 kernelization
  • 4 sparsification
  • 2 graph coloring
  • 2 satisfiability
  • 1 Approximation
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 3 2020
  • 2 2018
  • 1 2015
  • 1 2016
  • 1 2019

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