Found 2 Possible Name Variants:

Document

**Published in:** LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

We study DOMINATED CLUSTER DELETION. Therein, we are given an undirected graph G = (V,E) and integers k and d and the task is to find a set of at most k vertices such that removing these vertices results in a graph in which each connected component has a dominating set of size at most d. We also consider the special case where d is a constant. We show an almost complete tetrachotomy in terms of para-NP-hardness, containment in XP, containment in FPT, and admitting a polynomial kernel with respect to parameterizations that are a combination of k,d,c, and Δ, where c and Δ are the degeneracy and the maximum degree of the input graph, respectively. As a main contribution, we show that the problem can be solved in f(k,d) ⋅ n^O(d) time, that is, the problem is FPT when parameterized by k when d is a constant. This answers an open problem asked in a recent Dagstuhl seminar (23331). For the special case d = 1, we provide an algorithm with running time 2^𝒪(klog k) nm. Furthermore, we show that even for d = 1, the problem does not admit a polynomial kernel with respect to k + c.

Matthias Bentert, Michael R. Fellows, Petr A. Golovach, Frances A. Rosamond, and Saket Saurabh. Breaking a Graph into Connected Components with Small Dominating Sets. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.MFCS.2024.24, author = {Bentert, Matthias and Fellows, Michael R. and Golovach, Petr A. and Rosamond, Frances A. and Saurabh, Saket}, title = {{Breaking a Graph into Connected Components with Small Dominating Sets}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {24:1--24:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.24}, URN = {urn:nbn:de:0030-drops-205801}, doi = {10.4230/LIPIcs.MFCS.2024.24}, annote = {Keywords: Parameterized Algorithms, Recursive Understanding, Polynomial Kernels, Degeneracy} }

Document

**Published in:** Dagstuhl Reports, Volume 2, Issue 6 (2012)

This report documents the program and the outcomes of Dagstuhl Seminar 12241 ``Data Reduction and Problem Kernels''. 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.

Michael R. Fellows, Jiong Guo, Dániel Marx, and Saket Saurabh. Data Reduction and Problem Kernels (Dagstuhl Seminar 12241). In Dagstuhl Reports, Volume 2, Issue 6, pp. 26-50, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Article{fellows_et_al:DagRep.2.6.26, author = {Fellows, Michael R. and Guo, Jiong and Marx, D\'{a}niel and Saurabh, Saket}, title = {{Data Reduction and Problem Kernels (Dagstuhl Seminar 12241)}}, pages = {26--50}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2012}, volume = {2}, number = {6}, editor = {Fellows, Michael R. and Guo, Jiong and Marx, D\'{a}niel and Saurabh, Saket}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.6.26}, URN = {urn:nbn:de:0030-drops-37297}, doi = {10.4230/DagRep.2.6.26}, annote = {Keywords: Preprocessing, Fixed-parameter tractability, Parameterized algorithmics} }

Document

**Published in:** LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

The Nemhauser-Trotter local optimization theorem applies to the NP-hard \textsc{Vertex Cover} problem and has applications in approximation as well as parameterized algorithmics. We present a framework that generalizes Nemhauser and Trotter's result to vertex deletion and graph packing problems, introducing novel algorithmic strategies based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did).
We exhibit our framework using a generalization of \textsc{Vertex Cover}, called \textrm{\sc Bounded-Degree Deletion}, that has promise to become an important tool in the analysis of gene and other biological networks. For some fixed~$d\geq 0$, \textrm{\sc Bounded-Degree Deletion} asks to delete as few vertices as possible from a graph in order to transform it into a graph with maximum vertex degree at most~$d$. \textsc{Vertex Cover} is the special case of $d=0$. Our generalization of the Nemhauser-Trotter theorem implies that \textrm{\sc Bounded-Degree Deletion} has a problem kernel with a linear number of vertices for every constant~$d$. We also outline an application of our extremal combinatorial approach to the problem of packing stars with a bounded number of leaves. Finally, charting the border between (parameterized) tractability and intractability for \textrm{\sc Bounded-Degree Deletion}, we provide a W[2]-hardness result for \textrm{\sc Bounded-Degree Deletion} in case of unbounded $d$-values.

Michael R. Fellows, Jiong Guo, Hannes Moser, and Rolf Niedermeier. A Generalization of Nemhauser and Trotter's Local Optimization Theorem. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 409-420, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{fellows_et_al:LIPIcs.STACS.2009.1820, author = {Fellows, Michael R. and Guo, Jiong and Moser, Hannes and Niedermeier, Rolf}, title = {{A Generalization of Nemhauser and Trotter's Local Optimization Theorem}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {409--420}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1820}, URN = {urn:nbn:de:0030-drops-18200}, doi = {10.4230/LIPIcs.STACS.2009.1820}, annote = {Keywords: Algorithms, Computational complexity, NP-hard problems, W\lbrack2\rbrack-completeness, Graph problems, Combinatorial optimization, Fixed-parameter tractability, K} }

Document

**Published in:** Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Michael R. Fellows, Michael Hallett, Rold Niedermeier, and Naomi Nishimura. Fixed Parameter Algorithms (Dagstuhl Seminar 03311). Dagstuhl Seminar Report 388, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{fellows_et_al:DagSemRep.388, author = {Fellows, Michael R. and Hallett, Michael and Niedermeier, Rold and Nishimura, Naomi}, title = {{Fixed Parameter Algorithms (Dagstuhl Seminar 03311)}}, pages = {1--7}, ISSN = {1619-0203}, year = {2003}, type = {Dagstuhl Seminar Report}, number = {388}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.388}, URN = {urn:nbn:de:0030-drops-152681}, doi = {10.4230/DagSemRep.388}, }

Document

**Published in:** Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Rodney G. Downey, Michael R. Fellows, Rolf Niedermeier, and Peter Rossmanith. Parameterized Complexity (Dagstuhl Seminar 01311). Dagstuhl Seminar Report 316, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{downey_et_al:DagSemRep.316, author = {Downey, Rodney G. and Fellows, Michael R. and Niedermeier, Rolf and Rossmanith, Peter}, title = {{Parameterized Complexity (Dagstuhl Seminar 01311)}}, pages = {1--28}, ISSN = {1619-0203}, year = {2002}, type = {Dagstuhl Seminar Report}, number = {316}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.316}, URN = {urn:nbn:de:0030-drops-152009}, doi = {10.4230/DagSemRep.316}, }

Document

**Published in:** Dagstuhl Reports, Volume 13, Issue 8 (2024)

This report documents the program and the outcomes of Dagstuhl Seminar 23331 "Recent Trends in Graph Decomposition", which took place from 13. August to 18. August, 2023. The seminar brought together 33 experts from academia and industry to discuss graph decomposition, a pivotal technique for handling massive graphs in applications such as social networks and scientific simulations. The seminar addressed the challenges posed by contemporary hardware designs, the potential of deep neural networks and reinforcement learning in developing heuristics, the unique optimization requirements of large sparse data, and the need for scalable algorithms suitable for emerging architectures. Through presentations, discussions, and collaborative sessions, the event fostered an exchange of innovative ideas, leading to the creation of community notes highlighting key open problems in the field.

George Karypis, Christian Schulz, Darren Strash, Deepak Ajwani, Rob H. Bisseling, Katrin Casel, Ümit V. Çatalyürek, Cédric Chevalier, Florian Chudigiewitsch, Marcelo Fonseca Faraj, Michael Fellows, Lars Gottesbüren, Tobias Heuer, Kamer Kaya, Jakub Lacki, Johannes Langguth, Xiaoye Sherry Li, Ruben Mayer, Johannes Meintrup, Yosuke Mizutani, François Pellegrini, Fabrizio Petrini, Frances Rosamond, Ilya Safro, Sebastian Schlag, Roohani Sharma, Blair D. Sullivan, Bora Uçar, and Albert-Jan Yzelman. Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331). In Dagstuhl Reports, Volume 13, Issue 8, pp. 1-45, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{karypis_et_al:DagRep.13.8.1, author = {Karypis, George and Schulz, Christian and Strash, Darren and Ajwani, Deepak and Bisseling, Rob H. and Casel, Katrin and \c{C}ataly\"{u}rek, \"{U}mit V. and Chevalier, C\'{e}dric and Chudigiewitsch, Florian and Faraj, Marcelo Fonseca and Fellows, Michael and Gottesb\"{u}ren, Lars and Heuer, Tobias and Kaya, Kamer and Lacki, Jakub and Langguth, Johannes and Li, Xiaoye Sherry and Mayer, Ruben and Meintrup, Johannes and Mizutani, Yosuke and Pellegrini, Fran\c{c}ois and Petrini, Fabrizio and Rosamond, Frances and Safro, Ilya and Schlag, Sebastian and Sharma, Roohani and Sullivan, Blair D. and U\c{c}ar, Bora and Yzelman, Albert-Jan}, title = {{Recent Trends in Graph Decomposition (Dagstuhl Seminar 23331)}}, pages = {1--45}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2024}, volume = {13}, number = {8}, editor = {Karypis, George and Schulz, Christian and Strash, Darren}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.8.1}, URN = {urn:nbn:de:0030-drops-198114}, doi = {10.4230/DagRep.13.8.1}, annote = {Keywords: combinatorial optimization, experimental algorithmics, parallel algorithms} }

Document

**Published in:** LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

In the parameterized problem MaxLin2-AA[$k$], we are given a system with variables x_1,...,x_n consisting of equations of the form Product_{i in I}x_i = b, where x_i,b in {-1, 1} and I is a nonempty subset of {1,...,n}, each equation has a positive integral weight, and we are to decide whether it is possible to simultaneously satisfy equations of total weight at least W/2+k, where W is the total weight of all equations and k is the parameter (if k=0, the possibility is assured). We show that MaxLin2-AA[k] has a kernel with at most O(k^2 log k) variables and can be solved in time 2^{O(k log k)}(nm)^{O(1)}. This solves an open problem of Mahajan et al. (2006).
The problem Max-r-Lin2-AA[k,r] is the same as MaxLin2-AA[k] with two
differences: each equation has at most r variables and r is the second parameter. We prove a theorem on Max-$r$-Lin2-AA[k,r] which implies that Max-r-Lin2-AA[k,r] has a kernel with at most (2k-1)r variables, improving a number of results including one by Kim and Williams (2010). The theorem also implies a lower bound on the maximum of a function f that maps {-1,1}^n to the set of reals and whose Fourier expansion (which is a multilinear polynomial) is of degree r. We show applicability of the lower bound by giving a new proof of the Edwards-Erdös bound (each connected graph on n vertices and m edges has a bipartite subgraph with at least m/2 +(n-1)/4 edges) and obtaining a generalization.

Robert Crowston, Michael Fellows, Gregory Gutin, Mark Jones, Frances Rosamond, Stéphan Thomassé, and Anders Yeo. Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 229-240, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{crowston_et_al:LIPIcs.FSTTCS.2011.229, author = {Crowston, Robert and Fellows, Michael and Gutin, Gregory and Jones, Mark and Rosamond, Frances and Thomass\'{e}, St\'{e}phan and Yeo, Anders}, title = {{Simultaneously Satisfying Linear Equations Over F\underline2: MaxLin2 and Max-r-Lin2 Parameterized Above Average}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)}, pages = {229--240}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-34-7}, ISSN = {1868-8969}, year = {2011}, volume = {13}, editor = {Chakraborty, Supratik and Kumar, Amit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.229}, URN = {urn:nbn:de:0030-drops-33416}, doi = {10.4230/LIPIcs.FSTTCS.2011.229}, annote = {Keywords: MaxLin, fixed-parameter tractability, kernelization, pseudo-boolean functions} }

Document

**Published in:** LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Computing the Dodgson Score of a candidate in an election is a hard computational problem, which has been analyzed using classical and parameterized analysis. In this paper we resolve two open problems regarding the parameterized complexity of DODGSON SCORE. We show that DODGSON SCORE parameterized by the target score value $k$ does not have a polynomial kernel unless the polynomial hierarchy collapses to the third level; this complements a result of Fellows, Rosamond and Slinko who obtain a non-trivial kernel of exponential size for a generalization of this problem. We also prove that DODGSON SCORE parameterized by the number $n$ of votes is hard for $W[1]$.

Michael Fellows, Bart M. P. Jansen, Daniel Lokshtanov, Frances A. Rosamond, and Saket Saurabh. Determining the Winner of a Dodgson Election is Hard. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 459-468, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{fellows_et_al:LIPIcs.FSTTCS.2010.459, author = {Fellows, Michael and Jansen, Bart M. P. and Lokshtanov, Daniel and Rosamond, Frances A. and Saurabh, Saket}, title = {{Determining the Winner of a Dodgson Election is Hard}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {459--468}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.459}, URN = {urn:nbn:de:0030-drops-28866}, doi = {10.4230/LIPIcs.FSTTCS.2010.459}, annote = {Keywords: Dodgson Score, Parameterized Complexity, Kernelization Lower Bounds} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail