4 Search Results for "van Rooij, Iris"

Document
DOI: 10.4230/LIPIcs.MFCS.2025.13
Solving Partial Dominating Set and Related Problems Using Twin-Width

Authors: Jakub Balabán, Daniel Mock, and Peter Rossmanith

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are W[1]-hard on general graphs, they have been shown to be fixed-parameter tractable on many sparse graph classes, including nowhere-dense classes. In this paper, we demonstrate that these problems are also fixed-parameter tractable with respect to the twin-width of a graph. Indeed, we establish a more general result: every graph property that can be expressed by a logical formula of the form ϕ≡∃ x₁⋯ ∃ x_k ∑_{α ∈ I} #y ψ_α(x₁,…,x_k,y) ≥ t, where ψ_α is a quantifier-free formula for each α ∈ I, t is an arbitrary number, and #y is a counting quantifier, can be evaluated in time f(d,k)n, where n is the number of vertices and d is the width of a contraction sequence that is part of the input. In addition to the aforementioned problems, this includes also connected partial dominating set and independent partial dominating set.
Cite as

Jakub Balabán, Daniel Mock, and Peter Rossmanith. Solving Partial Dominating Set and Related Problems Using Twin-Width. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.MFCS.2025.13,
  author =	{Balab\'{a}n, Jakub and Mock, Daniel and Rossmanith, Peter},
  title =	{{Solving Partial Dominating Set and Related Problems Using Twin-Width}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.13},
  URN =		{urn:nbn:de:0030-drops-241203},
  doi =		{10.4230/LIPIcs.MFCS.2025.13},
  annote =	{Keywords: Partial Dominating Set, Partial Vertex Cover, meta-algorithm, counting logic, twin-width}
}
Document
DOI: 10.4230/DagRep.4.8.45
Resource-bounded Problem Solving (Dagstuhl Seminar 14341)

Authors: Yll Haxhimusa, Iris van Rooij, Sashank Varma, and Todd Wareham

Published in: Dagstuhl Reports, Volume 4, Issue 8 (2015)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14341 'Resource-bounded Problem Solving'. This seminar is a successor to Dagstuhl Seminar 11351: 'Computer Science & Problem Solving: New Foundations', held in August 2011, which was the first Dagstuhl event to bring together computer scientists and psychologists to exchange perspectives on problem solving in general. The current seminar built on the previous seminar by (1) narrowing the focus to issues related to resource-bounded problem solving and (2) broadening the range of perspectives on the specific topic by including a balanced number of attendees with expertise in computer science, psychology, artificial intelligence, and cognitive neuroscience.
Cite as

Yll Haxhimusa, Iris van Rooij, Sashank Varma, and Todd Wareham. Resource-bounded Problem Solving (Dagstuhl Seminar 14341). In Dagstuhl Reports, Volume 4, Issue 8, pp. 45-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{haxhimusa_et_al:DagRep.4.8.45,
  author =	{Haxhimusa, Yll and van Rooij, Iris and Varma, Sashank and Wareham, Todd},
  title =	{{Resource-bounded Problem Solving (Dagstuhl Seminar 14341)}},
  pages =	{45--72},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{8},
  editor =	{Haxhimusa, Yll and van Rooij, Iris and Varma, Sashank and Wareham, Todd},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.8.45},
  URN =		{urn:nbn:de:0030-drops-47989},
  doi =		{10.4230/DagRep.4.8.45},
  annote =	{Keywords: complexity theory, problem solving, cognitive psychology, computational trade-offs}
}
Document
DOI: 10.4230/DagRep.1.8.96
Computer Science & Problem Solving: New Foundations (Dagstuhl Seminar 11351)

Authors: Iris van Rooij, Yll Haxhimusa, Zygmunt Pizlo, and Georg Gottlob

Published in: Dagstuhl Reports, Volume 1, Issue 8 (2011)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 11351 ``Computer Science & Problem Solving: New Foundations''. This seminar was the first Dagstuhl seminar that brought together a balanced group of computer scientists and psychologists to exchange perspectives on problem solving. In the 1950s the seminal work of Allen Newell and Herbert Simon laid the theoretical foundations for problem solving research as we know it today, but the field had since become disconnected from contemporary computer science. The aim of this seminar was to promote theoretical progress in problem solving research by renewing the connection between psychology and computer science in this area.
Cite as

Iris van Rooij, Yll Haxhimusa, Zygmunt Pizlo, and Georg Gottlob. Computer Science & Problem Solving: New Foundations (Dagstuhl Seminar 11351). In Dagstuhl Reports, Volume 1, Issue 8, pp. 96-124, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{vanrooij_et_al:DagRep.1.8.96,
  author =	{van Rooij, Iris and Haxhimusa, Yll and Pizlo, Zygmunt and Gottlob, Georg},
  title =	{{Computer Science \& Problem Solving: New Foundations (Dagstuhl Seminar 11351)}},
  pages =	{96--124},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{8},
  editor =	{van Rooij, Iris and Haxhimusa, Yll and Pizlo, Zygmunt and Gottlob, Georg},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.8.96},
  URN =		{urn:nbn:de:0030-drops-33169},
  doi =		{10.4230/DagRep.1.8.96},
  annote =	{Keywords: Problem solving, Cognitive psychology, Cognitive systems, Vision Representations, Computational complexity}
}
Document
DOI: 10.4230/DagSemProc.07281.3
Approximating Solution Structure

Authors: Iris van Rooij, Matthew Hamilton, Moritz Müller, and Todd Wareham

Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)

Abstract
hen it is hard to compute an optimal solution $y in optsol(x)$ to an instance $x$ of a problem, one may be willing to settle for an efficient algorithm $A$ that computes an approximate solution $A(x)$. The most popular type of approximation algorithm in Computer Science (and indeed many other applications) computes solutions whose value is within some multiplicative factor of the optimal solution value, {em e.g.}, $max(frac{val(A(x))}{optval(x)}, frac{optval(x)}{val(A(x))}) leq h(|x|)$ for some function $h()$. However, an algorithm might also produce a solution whose structure is ``close'' to the structure of an optimal solution relative to a specified solution-distance function $d$, {em i.e.}, $d(A(x), y) leq h(|x|)$ for some $y in optsol(x)$. Such structure-approximation algorithms have applications within Cognitive Science and other areas. Though there is an extensive literature dating back over 30 years on value-approximation, there is to our knowledge no work on general techniques for assessing the structure-(in)approximability of a given problem. In this talk, we describe a framework for investigating the polynomial-time and fixed-parameter structure-(in)approximability of combinatorial optimization problems relative to metric solution-distance functions, {em e.g.}, Hamming distance. We motivate this framework by (1) describing a particular application within Cognitive Science and (2) showing that value-approximability does not necessarily imply structure-approximability (and vice versa). This framework includes definitions of several types of structure approximation algorithms analogous to those studied in value-approximation, as well as structure-approximation problem classes and a structure-approximability-preserving reducibility. We describe a set of techniques for proving the degree of structure-(in)approximability of a given problem, and summarize all known results derived using these techniques. We also list 11 open questions summarizing particularly promising directions for future research within this framework. vspace*{0.15in} oindent (co-presented with Todd Wareham) vspace*{0.15in} jointwork{Hamilton, Matthew; M"{u}ller, Moritz; van Rooij, Iris; Wareham, Todd}
Cite as

Iris van Rooij, Matthew Hamilton, Moritz Müller, and Todd Wareham. Approximating Solution Structure. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{vanrooij_et_al:DagSemProc.07281.3,
  author =	{van Rooij, Iris and Hamilton, Matthew and M\"{u}ller, Moritz and Wareham, Todd},
  title =	{{Approximating Solution Structure}},
  booktitle =	{Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7281},
  editor =	{Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.3},
  URN =		{urn:nbn:de:0030-drops-12345},
  doi =		{10.4230/DagSemProc.07281.3},
  annote =	{Keywords: Approximation Algorithms, Solution Structure}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2014
  • 1 2011
  • 1 2007

  • Refine by Author
  • 3 van Rooij, Iris
  • 2 Haxhimusa, Yll
  • 2 Wareham, Todd
  • 1 Balabán, Jakub
  • 1 Gottlob, Georg
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 2 DagRep
  • 1 DagSemProc

  • Refine by Classification
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Cognitive psychology
  • 1 Cognitive systems
  • 1 Computational complexity
  • 1 Partial Dominating Set
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact