Document

**Published in:** LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst. 2017] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a solution-lifting algorithm that efficiently enumerates all solutions from the set of the solutions of the kernel. We propose to consider two new versions of enumeration kernels by asking that the solutions of the original instance can be enumerated in polynomial time or with polynomial delay from the kernel solutions. Using the NP-hard Matching Cut problem parameterized by structural parameters such as the vertex cover number or the cyclomatic number of the input graph, we show that the new enumeration kernels present a useful notion of data reduction for enumeration problems which allows to compactly represent the set of feasible solutions.

Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{golovach_et_al:LIPIcs.STACS.2021.37, author = {Golovach, Petr A. and Komusiewicz, Christian and Kratsch, Dieter and Le, Van Bang}, title = {{Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {37:1--37:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.37}, URN = {urn:nbn:de:0030-drops-136823}, doi = {10.4230/LIPIcs.STACS.2021.37}, annote = {Keywords: enumeration problems, polynomial delay, output-sensitive algorithms, kernelization, structural parameterizations, matching cuts} }

Document

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

In a graph, a matching cut is an edge cut that is a matching. Matching Cut, which is known to be NP-complete, is the problem of deciding whether or not a given graph G has a matching cut. In this paper we show that Matching Cut admits a quadratic-vertex kernel for the parameter distance to cluster and a linear-vertex kernel for the parameter distance to clique. We further provide an O^*(2^{dc(G)}) time and an O^*(2^{dc^-}(G)}) time FPT algorithm for Matching Cut, where dc(G) and dc^-(G) are the distance to cluster and distance to co-cluster, respectively. We also improve the running time of the best known branching algorithm to solve Matching Cut from O^*(1.4143^n) to O^*(1.3803^n). Moreover, we point out that, unless NP subseteq coNP/poly, Matching Cut does not admit a polynomial kernel when parameterized by treewidth.

Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{komusiewicz_et_al:LIPIcs.IPEC.2018.19, author = {Komusiewicz, Christian and Kratsch, Dieter and Le, Van Bang}, title = {{Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {19:1--19: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.19}, URN = {urn:nbn:de:0030-drops-102207}, doi = {10.4230/LIPIcs.IPEC.2018.19}, annote = {Keywords: matching cut, decomposable graph, graph algorithm} }

Document

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

We present space-efficient algorithms for computing cut vertices in a given graph with n vertices and m edges in linear time using O(n+min{m,n log log n}) bits. With the same time and using O(n+m) bits, we can compute the biconnected components of a graph. We use this result to show an algorithm for the recognition of (maximal) outerplanar graphs in O(n log log n) time using O(n) bits.

Frank Kammer, Dieter Kratsch, and Moritz Laudahn. Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kammer_et_al:LIPIcs.MFCS.2016.56, author = {Kammer, Frank and Kratsch, Dieter and Laudahn, Moritz}, title = {{Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {56:1--56: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.56}, URN = {urn:nbn:de:0030-drops-64683}, doi = {10.4230/LIPIcs.MFCS.2016.56}, annote = {Keywords: graph algorithms, space efficiency, cut vertices, maximal outerplanar graphs} }

Document

**Published in:** LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are of distance 2 of each other. The Square Root problem is that of deciding whether a given graph admits a square root. We consider this problem for planar graphs in the context of the "distance from triviality" framework. For an integer k, a planar+kv graph is a graph that can be made planar by the removal of at most k vertices. We prove that the generalization of Square Root, in which we are given two subsets of edges prescribed to be in or out of a square root, respectively, has a kernel of size O(k) for planar+kv graphs, when parameterized by k. Our result is based on a new edge reduction rule which, as we shall also show, has a wider applicability for the Square Root problem.

Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, and Anthony Stewart. A Linear Kernel for Finding Square Roots of Almost Planar Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{golovach_et_al:LIPIcs.SWAT.2016.4, author = {Golovach, Petr A. and Kratsch, Dieter and Paulusma, Dani\"{e}l and Stewart, Anthony}, title = {{A Linear Kernel for Finding Square Roots of Almost Planar Graphs}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {4:1--4:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.4}, URN = {urn:nbn:de:0030-drops-60333}, doi = {10.4230/LIPIcs.SWAT.2016.4}, annote = {Keywords: planar graphs, square roots, linear kernel} }

Document

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

Listing, generating or enumerating objects of specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. We study the enumeration of all minimal connected dominating sets of an input graph from various graph classes of bounded chordality. We establish enumeration algorithms as well as lower and upper bounds for the maximum number of minimal connected dominating sets in such graphs. In particular, we present algorithms to enumerate all minimal connected dominating sets of chordal graphs in time O(1.7159^n), of split graphs in time O(1.3803^n), and of AT-free, strongly chordal, and distance-hereditary graphs in time O^*(3^{n/3}), where n is the number of vertices of the input graph. Our algorithms imply corresponding upper bounds for the number of minimal connected dominating sets for these graph classes.

Petr A. Golovach, Pinar Heggernes, and Dieter Kratsch. Enumerating Minimal Connected Dominating Sets in Graphs of Bounded Chordality. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 307-318, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{golovach_et_al:LIPIcs.IPEC.2015.307, author = {Golovach, Petr A. and Heggernes, Pinar and Kratsch, Dieter}, title = {{Enumerating Minimal Connected Dominating Sets in Graphs of Bounded Chordality}}, booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)}, pages = {307--318}, 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.307}, URN = {urn:nbn:de:0030-drops-55925}, doi = {10.4230/LIPIcs.IPEC.2015.307}, annote = {Keywords: Minimal connected dominating set, exact algorithms, enumeration} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 10441, Exact Complexity of NP-hard Problems (2011)

A decade before NP-completeness became the
lens through which Computer Science views computationally hard
problems, beautiful algorithms were discovered that are much better
than exhaustive search, for example
Bellman's 1962 dynamic programming treatment of the Traveling Salesman problem
and Ryser's 1963 inclusion--exclusion formula for the permanent.

Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, and Gregory B. Sorkin. 10441 Abstracts Collection – Exact Complexity of NP-hard Problems. In Exact Complexity of NP-hard Problems. Dagstuhl Seminar Proceedings, Volume 10441, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{husfeldt_et_al:DagSemProc.10441.1, author = {Husfeldt, Thore and Kratsch, Dieter and Paturi, Ramamohan and Sorkin, Gregory B.}, title = {{10441 Abstracts Collection – Exact Complexity of NP-hard Problems}}, booktitle = {Exact Complexity of NP-hard Problems}, pages = {1--22}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2011}, volume = {10441}, editor = {Thore Husfeldt and Dieter Kratsch and Ramamohan Paturi and Gregory B. Sorkin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10441.1}, URN = {urn:nbn:de:0030-drops-29363}, doi = {10.4230/DagSemProc.10441.1}, annote = {Keywords: Complexity, Algorithms, NP-hard Problems, Exponential Time, SAT, Graphs} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)

From $19/10/2008$ to $24/10/2008$, the Dagstuhl Seminar 08431 ``Moderately Exponential Time Algorithms '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available.

Fedor V. Fomin, Kazuo Iwama, and Dieter Kratsch. 08431 Abstracts Collection – Moderately Exponential Time Algorithms. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:DagSemProc.08431.1, author = {Fomin, Fedor V. and Iwama, Kazuo and Kratsch, Dieter}, title = {{08431 Abstracts Collection – Moderately Exponential Time Algorithms}}, booktitle = {Moderately Exponential Time Algorithms}, pages = {1--22}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8431}, editor = {Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.1}, URN = {urn:nbn:de:0030-drops-18004}, doi = {10.4230/DagSemProc.08431.1}, annote = {Keywords: Algorithms, Exponential time algorithms, Graphs, SAT} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)

The Dagstuhl seminar on Moderately Exponential Time Algorithms took place
from 19.10.08 to 24.10.08. The 54 participants came from 18 countries.
There were 27 talks and 2 open problem sessions. Talks were complemented
by intensive informal discussions, and many new research directions
and open problems will result from these discussions. The warm and encouraging Dagstuhl atmosphere stimulated new research projects.

Fedor V. Fomin, Kazuo Iwama, and Dieter Kratsch. 08431 Executive Summary – Moderately Exponential Time Algorithms. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:DagSemProc.08431.2, author = {Fomin, Fedor V. and Iwama, Kazuo and Kratsch, Dieter}, title = {{08431 Executive Summary – Moderately Exponential Time Algorithms}}, booktitle = {Moderately Exponential Time Algorithms}, pages = {1--2}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8431}, editor = {Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.2}, URN = {urn:nbn:de:0030-drops-17976}, doi = {10.4230/DagSemProc.08431.2}, annote = {Keywords: Algorithms, NP-hard problems, Exact algorithms, Moderately Exponential Time Algorithms} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)

Two problem sessions were part of the seminar on Moderately Exponential Time Algorithms. Some of the open problems presented at those sessions have been collected.

Fedor V. Fomin, Kazuo Iwama, Dieter Kratsch, Petteri Kaski, Mikko Koivisto, Lukasz Kowalik, Yoshio Okamoto, Johan van Rooij, and Ryan Williams. 08431 Open Problems – Moderately Exponential Time Algorithms. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:DagSemProc.08431.3, author = {Fomin, Fedor V. and Iwama, Kazuo and Kratsch, Dieter and Kaski, Petteri and Koivisto, Mikko and Kowalik, Lukasz and Okamoto, Yoshio and van Rooij, Johan and Williams, Ryan}, title = {{08431 Open Problems – Moderately Exponential Time Algorithms}}, booktitle = {Moderately Exponential Time Algorithms}, pages = {1--8}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8431}, editor = {Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.3}, URN = {urn:nbn:de:0030-drops-17986}, doi = {10.4230/DagSemProc.08431.3}, annote = {Keywords: Algorithms, NP-hard problems, Moderately Exponential Time Algorithms} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 7211, Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes (2007)

From May 20 to May 25, 2007, the Dagstuhl Seminar 07211 ``Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes'' was held
in the International Conference and Research Center (IBFI), Schloss Dagstuhl.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available.

Andreas Brandstädt, Klaus Jansen, Dieter Kratsch, and Jeremy P. Spinrad. 07211 Abstracts Collection – Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes. In Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes. Dagstuhl Seminar Proceedings, Volume 7211, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{brandstadt_et_al:DagSemProc.07211.1, author = {Brandst\"{a}dt, Andreas and Jansen, Klaus and Kratsch, Dieter and Spinrad, Jeremy P.}, title = {{07211 Abstracts Collection – Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes}}, booktitle = {Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes}, pages = {1--14}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7211}, editor = {Andreas Brandst\"{a}dt and Klaus Jansen and Dieter Kratsch and Jeremy P. Spinrad}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07211.1}, URN = {urn:nbn:de:0030-drops-12697}, doi = {10.4230/DagSemProc.07211.1}, annote = {Keywords: Graph theory, approximation algorithms, certifying algorithms, exact algorithms} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail