93 Search Results for "Agrawal, Akanksha"

Volume

LIPIcs, Volume 358

20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

IPEC 2025, Warsaw, Poland, September 17-19, 2025

Editors: Akanksha Agrawal and Erik Jan van Leeuwen

Document
DOI: 10.4230/LIPIcs.SWAT.2026.25
Parameterized Critical Node Cut Revisited

Authors: Dušan Knop, Nikolaos Melissinos, and Manolis Vasilakis

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We study how to sparsify connectivity in graphs under a tight deletion budget. Given a graph G and integers k,x ≥ 0, Critical Node Cut (CNC) asks whether we can delete at most k vertices so that the number of remaining unordered pairs of connected vertices is at most x. CNC generalizes Vertex Cover (the case x = 0) and models tasks in network design, epidemiology, and social network analysis. We comprehensively map the structural parameterized complexity landscape for Critical Node Cut. First, we prove W[1]-hardness for the combined parameter k + fes + Δ + pw, where fes is the feedback edge set number, Δ the maximum degree, and pw the pathwidth of the input graph, respectively. This significantly improves over the known W[1]-hardness for k+tw, where tw denotes the treewidth, and is tight in that tree-depth together with maximum degree trivially yields FPT. Second, we give new positive results. Specifically, we identify three structural parameters-max-leaf number, vertex integrity, and modular-width-that render the problem fixed-parameter tractable, and develop a polynomial-time algorithm for graphs of constant clique-width. Third, leveraging a technique introduced by Lampis [ICALP '14], we develop an FPT approximation scheme that, for any ε > 0, computes a (1+ε)-approximate solution in time (tw / ε)^{𝒪(tw)} n^{𝒪(1)}. Finally, we show that CNC admits no polynomial kernel when parameterized by vertex cover number, unless standard assumptions fail. Together, these results substantially sharpen the known complexity landscape for CNC.
Cite as

Dušan Knop, Nikolaos Melissinos, and Manolis Vasilakis. Parameterized Critical Node Cut Revisited. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{knop_et_al:LIPIcs.SWAT.2026.25,
  author =	{Knop, Du\v{s}an and Melissinos, Nikolaos and Vasilakis, Manolis},
  title =	{{Parameterized Critical Node Cut Revisited}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.25},
  URN =		{urn:nbn:de:0030-drops-260617},
  doi =		{10.4230/LIPIcs.SWAT.2026.25},
  annote =	{Keywords: Critical Node Cut, Parameterized Complexity, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.24
On the Complexity of the Maker-Breaker Happy Vertex Game

Authors: Mathieu Hilaire, Perig Montfort, and Nacim Oijid

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
Given a c-colored graph G, a vertex v of G is said to be happy if it has the same color as all its neighbors. The notion of happy vertices was introduced by Zhang and Li [Peng Zhang and Angsheng Li, 2015] to compute the homophily of a graph. Eto, Fujimoto, Kiya, Matsushita, Miyano, Murao and Saitoh [Hiroshi Eto et al., 2025] introduced the Maker-Maker version of the Happy vertex game, where two players compete to claim more happy vertices than their opponent. We introduce here the Maker-Breaker happy vertex game: two players, Maker and Breaker, alternately color the vertices of a graph with their respective colors. Maker aims to maximize the number of happy vertices at the end, while Breaker aims to prevent her. This game is also a scoring version of the Maker-Breaker domination game introduced by Duchene, Gledel, Parreau and Renault [Duchene et al., 2020], as a happy vertex corresponds exactly to a vertex that is not dominated in the domination game. Therefore, this game is a very natural game on graphs and can be studied within the scope of scoring positional games [Bagan et al., 2024]. We initiate here the complexity study of this game, by proving that computing its score is PSPACE-complete on trees, NP-hard on caterpillars, and polynomial on subdivided stars. Finally, we provide the exact value of the score on graphs of maximum degree 2, and we provide an FPT-algorithm to compute the score on graphs of bounded neighborhood diversity. An important contribution of the paper is that, to achieve our hardness results, we introduce a new type of incidence graph called the literal-clause incidence graph for 2-SAT formulas. We prove that QMAX 2-SAT remains PSPACE-complete even if this graph is acyclic, and that MAX 2-SAT remains NP-complete, even if this graph is acyclic and has maximum degree 2, i.e. is a union of paths. We demonstrate the importance of this contribution by proving that Incidence, the scoring positional game played on a graph is also PSPACE-complete when restricted to forests.
Cite as

Mathieu Hilaire, Perig Montfort, and Nacim Oijid. On the Complexity of the Maker-Breaker Happy Vertex Game. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hilaire_et_al:LIPIcs.FUN.2026.24,
  author =	{Hilaire, Mathieu and Montfort, Perig and Oijid, Nacim},
  title =	{{On the Complexity of the Maker-Breaker Happy Vertex Game}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{24:1--24:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.24},
  URN =		{urn:nbn:de:0030-drops-257434},
  doi =		{10.4230/LIPIcs.FUN.2026.24},
  annote =	{Keywords: Maker-Breaker game, Domination game, happy vertex game, scoring game, complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.73
Colouring Probe H-Free Graphs

Authors: Daniël Paulusma, Johannes Rauch, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
The NP-complete problems Colouring and k-Colouring (k ≥ 3) are well studied on H-free graphs, i.e., graphs that do not contain some fixed graph H as an induced subgraph. We research to what extent the known polynomial-time algorithms for H-free graphs can be generalized if we only know some of the edges of the input graph. We do this by considering the classical probe graph model introduced in the early nineties. For a graph H, a partitioned probe H-free graph (G,P,N) consists of a graph G = (V,E), together with a set P ⊆ V of probes and an independent set N = V ⧵ P of non-probes, such that G+F is H-free for some edge set F ⊆ binom(N,2). We show the following: - We fully classify Colouring on partitioned probe H-free graphs and show that the obtained complexity dichotomy differs from the known dichotomy of Colouring for H-free graphs. - We fully classify 3-Colouring on partitioned probe P_t-free graphs: we prove polynomial-time solvability for t ≤ 5 and NP-completeness for t ≥ 6. In contrast, 3-Colouring on P_t-free graphs is known to be polynomial-time solvable for t ≤ 7 and quasi-polynomial-time solvable for t ≥ 8. Our main result is our polynomial-time algorithm for 3-Colouring on partitioned P₅-free graphs. For this result, and also for all our other polynomial-time results, we do not need to know the edge set F; we only need to know its existence. Moreover, the class of probe P₅-free graphs includes not only paths of arbitrary length but even all bipartite graphs and is much richer than the class of P₅-free graphs. The latter is also evidenced by the fact that there exist graph problems, such as Matching Cut, that are known to be polynomial-time solvable for P₅-free graphs but NP-complete for partitioned probe P₅-free graphs. In particular, unlike the class of 3-colourable P₅-free graphs, the class of 3-colourable probe P₅-free graphs has unbounded mim-width. Hence, our polynomial-time result for 3-Colouring for probe P₅-free graphs suggests that there may be another, deeper overarching reason why 3-Colouring is polynomial-time solvable for P₅-free graphs.
Cite as

Daniël Paulusma, Johannes Rauch, and Erik Jan van Leeuwen. Colouring Probe H-Free Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{paulusma_et_al:LIPIcs.STACS.2026.73,
  author =	{Paulusma, Dani\"{e}l and Rauch, Johannes and van Leeuwen, Erik Jan},
  title =	{{Colouring Probe H-Free Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{73:1--73:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.73},
  URN =		{urn:nbn:de:0030-drops-255621},
  doi =		{10.4230/LIPIcs.STACS.2026.73},
  annote =	{Keywords: colouring, probe graph, forbidden induced subgraph, complexity dichotomy}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2025.37
PACE Solver Description: Minimum Hitting Set Computation via Core-Guided MaxSAT Solving

Authors: André Schidler

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
This paper describes our hybrid MaxSAT and mixed integer programming approach for finding minimum hitting sets as submitted to the 2025 PACE challenge. We also discuss hitting set specific challenges, lower bounds, preprocessing and design choices.
Cite as

André Schidler. PACE Solver Description: Minimum Hitting Set Computation via Core-Guided MaxSAT Solving. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 37:1-37:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schidler:LIPIcs.IPEC.2025.37,
  author =	{Schidler, Andr\'{e}},
  title =	{{PACE Solver Description: Minimum Hitting Set Computation via Core-Guided MaxSAT Solving}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{37:1--37:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.37},
  URN =		{urn:nbn:de:0030-drops-251692},
  doi =		{10.4230/LIPIcs.IPEC.2025.37},
  annote =	{Keywords: hitting set, maxsat, core-guided}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2025.38
PACE Solver Description: HitS&DoSeS - Exact and Heuristic Solvers for the Dominating Set and Hitting Set Problems

Authors: Sylwester Swat

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
This article briefly describes the most important algorithms and techniques used in HitS&DoSeS, a dominating set and hitting set solver submitted to the PACE 2025 contest (10th Parameterized Algorithms and Computational Experiments Challenge). Used approaches for the exact and heuristic tracks are described, for both the dominating set and the hitting set problems.
Cite as

Sylwester Swat. PACE Solver Description: HitS&DoSeS - Exact and Heuristic Solvers for the Dominating Set and Hitting Set Problems. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 38:1-38:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{swat:LIPIcs.IPEC.2025.38,
  author =	{Swat, Sylwester},
  title =	{{PACE Solver Description: HitS\&DoSeS - Exact and Heuristic Solvers for the Dominating Set and Hitting Set Problems}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{38:1--38:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.38},
  URN =		{urn:nbn:de:0030-drops-251705},
  doi =		{10.4230/LIPIcs.IPEC.2025.38},
  annote =	{Keywords: dominating set, hitting set, exact algorithms, heuristic algorithms, large graphs, combinatorial optimization}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2025.40
PACE Solver Description: Weighting-Based Local Search Heuristic for the Hitting Set Problem

Authors: Canhui Luo, Qingyun Zhang, Zhouxing Su, and Zhipeng Lü

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We present a unified heuristic solver for the PACE 2025 challenge, addressing both the dominating set and hitting set problems by reducing them to the unicost set covering problem. Our solver applies standard reduction rules, a multi-round frequency-based greedy initializer, and a local search guided by adaptive element weights. Additional techniques, such as component-level exact solving and swap restriction, further enhance performance. In the final official evaluation, our proposed solver achieved second place in the heuristic track for the dominating set problem of the PACE 2025 challenge, while securing first place in the heuristic track for the hitting set problem.
Cite as

Canhui Luo, Qingyun Zhang, Zhouxing Su, and Zhipeng Lü. PACE Solver Description: Weighting-Based Local Search Heuristic for the Hitting Set Problem. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 40:1-40:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{luo_et_al:LIPIcs.IPEC.2025.40,
  author =	{Luo, Canhui and Zhang, Qingyun and Su, Zhouxing and L\"{u}, Zhipeng},
  title =	{{PACE Solver Description: Weighting-Based Local Search Heuristic for the Hitting Set Problem}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{40:1--40:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.40},
  URN =		{urn:nbn:de:0030-drops-251728},
  doi =		{10.4230/LIPIcs.IPEC.2025.40},
  annote =	{Keywords: PACE 2025, Dominating Set, Hitting Set, Heuristic Optimization, Weighted Local Search}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2025.39
PACE Solver Description: UzL Solver for Dominating Set and Hitting Set

Authors: Max Bannach, Florian Chudigiewitsch, and Marcel Wienöbst

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
This document contains a short description of our solver for the dominating set and hitting set problems that we submitted to the exact tracks of the PACE Challenge 2025. The solver is based on a straightforward MaxSAT formulation supplemented by hitting-set-based reduction rules. It utilizes a clique solver if the reduced instance is a (small) input for the vertex cover problem and tries to match certain lower bounds by expressing the reduced instance as a sat problem.
Cite as

Max Bannach, Florian Chudigiewitsch, and Marcel Wienöbst. PACE Solver Description: UzL Solver for Dominating Set and Hitting Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 39:1-39:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bannach_et_al:LIPIcs.IPEC.2025.39,
  author =	{Bannach, Max and Chudigiewitsch, Florian and Wien\"{o}bst, Marcel},
  title =	{{PACE Solver Description: UzL Solver for Dominating Set and Hitting Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{39:1--39:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.39},
  URN =		{urn:nbn:de:0030-drops-251710},
  doi =		{10.4230/LIPIcs.IPEC.2025.39},
  annote =	{Keywords: exact algorithms, dominating set, hitting set}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.29
Hitting Geodesic Intervals in Structurally Restricted Graphs

Authors: Tatsuya Gima, Yasuaki Kobayashi, Yuto Okada, Yota Otachi, and Hayato Takaike

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Given a graph G = (V,E), a set T of vertex pairs, and an integer k, Hitting Geodesic Intervals asks whether there is a set S ⊆ V of size at most k such that for each terminal pair {u,v} ∈ T, the set S intersects at least one shortest u-v path. Aravind and Saxena [WALCOM 2024] introduced this problem and showed several parameterized complexity results. In this paper, we extend the known results in both negative and positive directions and present sharp complexity contrasts with respect to structural graph parameters. We first show that the problem is NP-complete even on graphs with highly restricted shortest-path structures. More precisely, we show the NP-completeness on graphs obtained by adding a single vertex to a disjoint union of 5-vertex paths. By modifying the proof of this result, we also show the NP-completeness on graphs obtained from a path by adding one vertex and on graphs obtained from a disjoint union of triangles by adding one universal vertex. Furthermore, we show the NP-completeness on graphs of bandwidth 4 and maximum degree 5 by replacing the universal vertex in the last case with a long path. Under standard complexity assumptions, these negative results rule out fixed-parameter algorithms for most of the structural parameters studied in the literature (if the solution size k is not part of the parameter). We next present fixed-parameter algorithms parameterized by k plus modular-width and by k plus vertex integrity. The algorithm for the latter case does indeed solve a more general setting that includes the parameterization by the minimum vertex multiway-cut size of the terminal vertices. We show that this is tight in the sense that the problem parameterized by the minimum vertex multicut size of the terminal pairs is W[2]-complete. We then modify the proof of this intractability result and show that the problem is W[2]-complete parameterized by k even in the setting where T = binom(Q,2) for some Q ⊆ V.
Cite as

Tatsuya Gima, Yasuaki Kobayashi, Yuto Okada, Yota Otachi, and Hayato Takaike. Hitting Geodesic Intervals in Structurally Restricted Graphs. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gima_et_al:LIPIcs.IPEC.2025.29,
  author =	{Gima, Tatsuya and Kobayashi, Yasuaki and Okada, Yuto and Otachi, Yota and Takaike, Hayato},
  title =	{{Hitting Geodesic Intervals in Structurally Restricted Graphs}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.29},
  URN =		{urn:nbn:de:0030-drops-251618},
  doi =		{10.4230/LIPIcs.IPEC.2025.29},
  annote =	{Keywords: Terminal monitoring set, Structural graph parameter, Geodesic interval}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.30
A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers

Authors: Jesse Beisegel, Katharina Klost, Kristin Knorr, Fabienne Ratajczak, and Robert Scheffler

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We consider the problem of finding a Hamiltonian path or cycle with precedence constraints in the form of a partial order on the vertex set. We study the complexity for graph width parameters for which the ordinary problems Hamiltonian Path and Hamiltonian Cycle are in FPT. In particular, we focus on parameters that describe how many vertices and edges have to be deleted to become a member of a certain graph class. We show that the problems are W[1]-hard for such restricted cases as vertex distance to path and vertex distance to clique. We complement these results by showing that the problems can be solved in XP time for vertex distance to outerplanar and vertex distance to block. Furthermore, we present some FPT algorithms, e.g., for edge distance to block. Additionally, we prove para-NP-hardness when considered with the edge clique cover number.
Cite as

Jesse Beisegel, Katharina Klost, Kristin Knorr, Fabienne Ratajczak, and Robert Scheffler. A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beisegel_et_al:LIPIcs.IPEC.2025.30,
  author =	{Beisegel, Jesse and Klost, Katharina and Knorr, Kristin and Ratajczak, Fabienne and Scheffler, Robert},
  title =	{{A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.30},
  URN =		{urn:nbn:de:0030-drops-251623},
  doi =		{10.4230/LIPIcs.IPEC.2025.30},
  annote =	{Keywords: Hamiltonian path, Hamiltonian cycle, partial order, graph width parameter, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.32
The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set

Authors: Mario Grobler and Sebastian Siebertz

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
The 10th iteration of the of the Parameterized Algorithms and Computational Experiments challenge (PACE) 2025 was devoted to engineer algorithms solving the Dominating Set problem as well as the Hitting Set problem. In contrast to the last iterations, these problems are (under standard assumptions) not fixed-parameter tractable (fpt) in general. However, restricting the structure of the input (e.g. to planar graphs or degenerate graphs for Dominating Set, or to set systems with sets of bounded size for Hitting Set) renders these problems fpt. Following the spirit of the last iterations of the PACE challenge, there is an exact track and a heuristic track for each problem; each track coming with a benchmark set of 100 public instances and 100 private instances. Overall, the PACE 2025 had 71 participants from 25 teams, 13 countries, and 3 continents. In this report, we briefly describe the setup of the challenge, the selection of benchmark instances, as well as the ranking of the participating teams. We also briefly outline the approaches used in the submitted solvers.
Cite as

Mario Grobler and Sebastian Siebertz. The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grobler_et_al:LIPIcs.IPEC.2025.32,
  author =	{Grobler, Mario and Siebertz, Sebastian},
  title =	{{The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating Set and Hitting Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.32},
  URN =		{urn:nbn:de:0030-drops-251644},
  doi =		{10.4230/LIPIcs.IPEC.2025.32},
  annote =	{Keywords: PACE 2025 Report, Dominating Set, Hitting Set, Algorithm Engineering, FPT, Heuristics}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2025.34
PACE Solver Description: Shadoks Approach to Minimum Hitting Set and Dominating Set

Authors: Guilherme D. da Fonseca, Fabien Feschet, and Yan Gerard

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Description of the solvers used by the Shadoks team in the PACE 2025 challenge. The challenge considers solvers for the minimum dominating set and hitting set problems. For the heuristic challenge, we respectively won third and fourth place for hitting set and dominating set. For the exact challenge, we won fifth place on both problems.
Cite as

Guilherme D. da Fonseca, Fabien Feschet, and Yan Gerard. PACE Solver Description: Shadoks Approach to Minimum Hitting Set and Dominating Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 34:1-34:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dafonseca_et_al:LIPIcs.IPEC.2025.34,
  author =	{da Fonseca, Guilherme D. and Feschet, Fabien and Gerard, Yan},
  title =	{{PACE Solver Description: Shadoks Approach to Minimum Hitting Set and Dominating Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{34:1--34:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.34},
  URN =		{urn:nbn:de:0030-drops-251660},
  doi =		{10.4230/LIPIcs.IPEC.2025.34},
  annote =	{Keywords: Optimization, heuristic, hitting set, dominating set}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2025.35
PACE Solver Description: Bad Dominating Set Maker

Authors: Alexander Dobler, Simon Dominik Fink, and Mathis Rocton

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Dominating Set and Hitting Set are two well-known NP-hard problems on graphs and hypergraphs, respectively. For Dominating Set, we seek a subset S of vertices of minimum size, such that every vertex has a neighbor in S. For Hitting Set, we require that this minimum size subset S intersects each hyperedge. We present Bad Dominating Set Maker, our solver for both problems posed in the exact tracks of the 2025 PACE Challenge. It uses reduction rules, dynamic programming on tree decompositions, and external Vertex Cover and SAT solvers.
Cite as

Alexander Dobler, Simon Dominik Fink, and Mathis Rocton. PACE Solver Description: Bad Dominating Set Maker. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 35:1-35:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dobler_et_al:LIPIcs.IPEC.2025.35,
  author =	{Dobler, Alexander and Fink, Simon Dominik and Rocton, Mathis},
  title =	{{PACE Solver Description: Bad Dominating Set Maker}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{35:1--35:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.35},
  URN =		{urn:nbn:de:0030-drops-251673},
  doi =		{10.4230/LIPIcs.IPEC.2025.35},
  annote =	{Keywords: Dominating Set, Hitting Set, Pace Challenge}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.26
Complexity of Local Search for CSPs Parameterized by Constraint Difference

Authors: Aditya Anand, Vincent Cohen-Addad, Tommaso D'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi, and Sijin Peng

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
In this paper, we study the parameterized complexity of local search, whose goal is to find a good nearby solution from the given current solution. Formally, given an optimization problem where the goal is to find the largest feasible subset S of a universe U, the new input consists of a current solution P (not necessarily feasible) as well as an ordinary input for the problem. Given the existence of a feasible solution S^*, the goal is to find a feasible solution as good as S^* in parameterized time f(k)⋅n^O(1), where k denotes the distance |PΔ S^*|. This model generalizes numerous classical parameterized optimization problems whose parameter k is the minimum number of elements removed from U to make it feasible, which corresponds to the case P = U. We apply this model to widely studied Constraint Satisfaction Problems (CSPs), where U is the set of constraints, and a subset U' of constraints is feasible if there is an assignment to the variables satisfying all constraints in U'. We give a complete characterization of the parameterized complexity of all boolean-alphabet symmetric CSPs, where the predicate’s acceptance depends on the number of true literals.
Cite as

Aditya Anand, Vincent Cohen-Addad, Tommaso D'Orsi, Anupam Gupta, Euiwoong Lee, Debmalya Panigrahi, and Sijin Peng. Complexity of Local Search for CSPs Parameterized by Constraint Difference. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.IPEC.2025.26,
  author =	{Anand, Aditya and Cohen-Addad, Vincent and D'Orsi, Tommaso and Gupta, Anupam and Lee, Euiwoong and Panigrahi, Debmalya and Peng, Sijin},
  title =	{{Complexity of Local Search for CSPs Parameterized by Constraint Difference}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.26},
  URN =		{urn:nbn:de:0030-drops-251586},
  doi =		{10.4230/LIPIcs.IPEC.2025.26},
  annote =	{Keywords: Constraint Satisfaction Problems, Parameterized Local Search, Optimization}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.28
Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number

Authors: Prafullkumar Tale

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
In the Geodetic Set problem, the input consists of a graph G and a positive integer k. The goal is to determine whether there exists a subset S of vertices of size k such that every vertex in the graph is included in a shortest path between two vertices in S. Kellerhals and Koana [IPEC 2020; J. Graph Algorithms Appl 2022] proved that the problem is W[1]-hard when parameterized by the pathwidth or the feedback vertex set number of the input graph. They posed the question of whether the problem admits an XP-algorithm when parameterized by the combination of these two parameters. We answer this in the negative by proving that the problem remains NP-hard even on graphs of constant pathwidth and feedback vertex set number.
Cite as

Prafullkumar Tale. Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{tale:LIPIcs.IPEC.2025.28,
  author =	{Tale, Prafullkumar},
  title =	{{Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{28:1--28:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.28},
  URN =		{urn:nbn:de:0030-drops-251601},
  doi =		{10.4230/LIPIcs.IPEC.2025.28},
  annote =	{Keywords: Geodetic Sets, NP-hardness, Constant Treewidth}
}
  • Refine by Type
  • 92 Document/PDF
  • 57 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 3 2026
  • 59 2025
  • 2 2024
  • 2 2023
  • 3 2022
  • Show More...

  • Refine by Author
  • 35 Agrawal, Akanksha
  • 24 Saurabh, Saket
  • 11 Zehavi, Meirav
  • 10 Lokshtanov, Daniel
  • 5 Mouawad, Amer E.
  • Show More...

  • Refine by Series/Journal
  • 90 LIPIcs
  • 2 DagRep

  • Refine by Classification
  • 40 Theory of computation → Parameterized complexity and exact algorithms
  • 19 Theory of computation → Fixed parameter tractability
  • 11 Mathematics of computing → Graph algorithms
  • 11 Theory of computation → Graph algorithms analysis
  • 8 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 11 parameterized complexity
  • 9 Parameterized Complexity
  • 8 Kernelization
  • 8 Parameterized complexity
  • 6 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