11 Search Results for "C. M. Gomes, Guilherme"

Document
DOI: 10.4230/LIPIcs.IPEC.2025.23
Enumeration Kernels for Vertex Cover and Feedback Vertex Set

Authors: Marin Bougeret, Guilherme C. M. Gomes, Vinicius F. dos Santos, and Ignasi Sau

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

Abstract
Enumerative kernelization is a recent and promising area sitting at the intersection of parameterized complexity and enumeration algorithms. Its study began with the paper of Creignou et al. [Theory Comput. Syst., 2017], and development in the area has started to accelerate with the work of Golovach et al. [J. Comput. Syst. Sci., 2022]. The latter introduced polynomial-delay enumeration kernels and applied them in the study of structural parameterizations of the Matching Cut problem and some variants. Few other results, mostly on Longest Path and some generalizations of Matching Cut, have also been developed. However, little success has been seen in enumeration versions of Vertex Cover and Feedback Vertex Set, some of the most studied problems in kernelization. In this paper, we address this shortcoming. Our first result is a polynomial-delay enumeration kernel with 2k vertices for Enum Vertex Cover, where we wish to list all solutions with at most k vertices. This is obtained by developing a non-trivial lifting algorithm for the classical crown decomposition reduction rule, and directly improves upon the kernel with 𝒪(k²) vertices derived from the work of Creignou et al. Our other result is a polynomial-delay enumeration kernel with 𝒪(k³) vertices and edges for Enum Feedback Vertex Set; the proof is inspired by some ideas of Thomassé [TALG, 2010], but with a weaker bound on the kernel size due to difficulties in applying the q-expansion technique.
Cite as

Marin Bougeret, Guilherme C. M. Gomes, Vinicius F. dos Santos, and Ignasi Sau. Enumeration Kernels for Vertex Cover and Feedback Vertex Set. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bougeret_et_al:LIPIcs.IPEC.2025.23,
  author =	{Bougeret, Marin and C. M. Gomes, Guilherme and dos Santos, Vinicius F. and Sau, Ignasi},
  title =	{{Enumeration Kernels for Vertex Cover and Feedback Vertex Set}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{23:1--23:18},
  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.23},
  URN =		{urn:nbn:de:0030-drops-251552},
  doi =		{10.4230/LIPIcs.IPEC.2025.23},
  annote =	{Keywords: Kernelization, Enumeration, Vertex cover, Crown decomposition, Feedback vertex set}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.14
A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma

Authors: Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, and Meirav Zehavi

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

Abstract
We present an algorithm for a class of n-fold ILPs whose existing algorithms in literature are often either (1) based on the augmentation framework where one starts with an arbitrary solution and then iteratively moves towards an optimal solution by solving appropriate programs; or (2) require solving a linear relaxation of the program; or (3) are based on decomposition/proximity based arguments. Combinatorial n-fold ILPs is a class of n-fold ILPs introduced and studied by Knop et al. [MP2020] that captures several other problems in a variety of domains. We present a simple and direct algorithm that solves combinatorial n-fold ILPs with unbounded non-negative variables via an application of the Steinitz lemma. Depending on the structure of the input ILP, we also improve upon the existing algorithms in the literature in terms of the running time, thereby showing an improvement that mirrors the one shown by Rohwedder [ICALP2025] contemporaneously and independently.
Cite as

Sushmita Gupta, Pallavi Jain, Sanjay Seetharaman, and Meirav Zehavi. A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.IPEC.2025.14,
  author =	{Gupta, Sushmita and Jain, Pallavi and Seetharaman, Sanjay and Zehavi, Meirav},
  title =	{{A Simple Algorithm for Combinatorial n-Fold ILPs Using the Steinitz Lemma}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{14:1--14: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.14},
  URN =		{urn:nbn:de:0030-drops-251467},
  doi =		{10.4230/LIPIcs.IPEC.2025.14},
  annote =	{Keywords: n-fold integer linear program, parameterized algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.4
Finding d-Cuts in Claw-Free Graphs

Authors: Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, Daniël Paulusma, and Siani Smith

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Matching Cut problem is to decide if the vertex set of a connected graph can be partitioned into two non-empty sets B and R such that the edges between B and R form a matching, that is, every vertex in B has at most one neighbour in R, and vice versa. If for some integer d ≥ 1, we allow every vertex in B to have at most d neighbours in R, and vice versa, we obtain the more general problem d-Cut. It is known that d-Cut is NP-complete for every d ≥ 1. However, for claw-free graphs, it is only known that d-Cut is polynomial-time solvable for d = 1 and NP-complete for d ≥ 3. We resolve the missing case d = 2 by proving NP-completeness. This follows from our more general study, in which we also bound the maximum degree. That is, we prove that for every d ≥ 2, d-Cut, restricted to claw-free graphs of maximum degree p, is constant-time solvable if p ≤ 2d+1 and NP-complete if p ≥ 2d+3. Moreover, in the former case, we can find a d-cut in linear time. We also show how our positive results for claw-free graphs can be generalized to S_{1^t,𝓁}-free graphs where S_{1^t,𝓁} is the graph obtained from a star on t+2 vertices by subdividing one of its edges exactly 𝓁 times.
Cite as

Jungho Ahn, Tala Eagling-Vose, Felicia Lucke, Daniël Paulusma, and Siani Smith. Finding d-Cuts in Claw-Free Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ahn_et_al:LIPIcs.ISAAC.2025.4,
  author =	{Ahn, Jungho and Eagling-Vose, Tala and Lucke, Felicia and Paulusma, Dani\"{e}l and Smith, Siani},
  title =	{{Finding d-Cuts in Claw-Free Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.4},
  URN =		{urn:nbn:de:0030-drops-249121},
  doi =		{10.4230/LIPIcs.ISAAC.2025.4},
  annote =	{Keywords: matching cut, d-cut, claw-free, maximum degree}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.23
Precoloring Extension with Demands on Paths

Authors: Arun Kumar Das, Michal Opler, and Tomáš Valla

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Let G be a graph with a set of precolored vertices, and let us be given an integer distance parameter d and a set of integer demands d₁,… ,d_c. The Distance Precoloring Extension with Demands (DPED) problem is to compute a vertex c-coloring of G such that the following three conditions hold: (i) the resulting coloring respects the colors of the precolored vertices, (ii) the distance of two vertices of the same color is at least d, and (iii) the number of vertices colored by color i is exactly d_i. This problem is motivated by a program scheduling in commercial broadcast channels with constraints on content repetition and placement, which leads precisely to the DPED problem for paths. In this paper, we study DPED on paths and present a polynomial time exact algorithm when precolored vertices are restricted to the two ends of the path and devise an approximation algorithm for DPED with an additive approximation factor polynomially bounded by d and the number of precolored vertices. Then, we prove that the Distance Precoloring Extension problem on paths, a less restrictive version of DPED without the demand constraints, and then DPED itself, is NP-complete. Motivated by this result, we further study the parameterized complexity of DPED on paths. We establish that the DPED problem on paths is W[1]-hard when parameterized by the number of colors and the distance. On the positive side, we devise a fixed parameter tractable (FPT) algorithm for DPED on paths when the number of colors, the distance, and the number of precolored vertices are considered as the parameters. Moreover, we prove that Distance Precoloring Extension is FPT parameterized by the distance. As a byproduct, we also obtain several results for the Distance List Coloring problem on paths.
Cite as

Arun Kumar Das, Michal Opler, and Tomáš Valla. Precoloring Extension with Demands on Paths. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ISAAC.2025.23,
  author =	{Das, Arun Kumar and Opler, Michal and Valla, Tom\'{a}\v{s}},
  title =	{{Precoloring Extension with Demands on Paths}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{23:1--23:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.23},
  URN =		{urn:nbn:de:0030-drops-249319},
  doi =		{10.4230/LIPIcs.ISAAC.2025.23},
  annote =	{Keywords: precoloring extension, distance coloring, FPT, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.110
Faster Exponential Algorithms for Cut Problems via Geometric Data Structures

Authors: László Kozma and Junqi Tan

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
For many hard computational problems, simple algorithms that run in time 2ⁿ ⋅ n^O(1) arise, say, from enumerating all subsets of a size-n set. Finding (exponentially) faster algorithms is a natural goal that has driven much of the field of exact exponential algorithms (e.g., see Fomin and Kratsch, 2010). In this paper we obtain algorithms with running time O(1.9999977ⁿ) on input graphs with n vertices, for the following well-studied problems: - d-Cut: find a proper cut in which no vertex has more than d neighbors on the other side of the cut; - Internal Partition: find a proper cut in which every vertex has at least as many neighbors on its side of the cut as on the other side; and - (α,β)-Domination: given intervals α,β ⊆ [0,n], find a subset S of the vertices, so that for every vertex v ∈ S the number of neighbors of v in S is from α and for every vertex v ∉ S, the number of neighbors of v in S is from β. Our algorithms are exceedingly simple, combining the split and list technique (Horowitz and Sahni, 1974; Williams, 2005) with a tool from computational geometry: orthogonal range searching in the moderate dimensional regime (Chan, 2017). Our technique is applicable to the decision, optimization and counting versions of these problems and easily extends to various generalizations with more fine-grained, vertex-specific constraints, as well as to directed, balanced, and other variants. Algorithms with running times of the form cⁿ, for c < 2, were known for the first problem only for constant d, and for the third problem for certain special cases of α and β; for the second problem we are not aware of such results.
Cite as

László Kozma and Junqi Tan. Faster Exponential Algorithms for Cut Problems via Geometric Data Structures. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 110:1-110:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kozma_et_al:LIPIcs.ESA.2025.110,
  author =	{Kozma, L\'{a}szl\'{o} and Tan, Junqi},
  title =	{{Faster Exponential Algorithms for Cut Problems via Geometric Data Structures}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{110:1--110:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.110},
  URN =		{urn:nbn:de:0030-drops-245796},
  doi =		{10.4230/LIPIcs.ESA.2025.110},
  annote =	{Keywords: graph algorithms, cuts, exponential time, data structures}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.15
Enumerating Minimal Dominating Sets and Variants in Chordal Bipartite Graphs

Authors: Emanuel Castelo, Oscar Defrain, and Guilherme C. M. Gomes

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Enumerating minimal dominating sets with polynomial delay in bipartite graphs is a long-standing open problem. To date, even the subcase of chordal bipartite graphs is open, with the best known algorithm due to Golovach, Heggernes, Kanté, Kratsch, Sæther, and Villanger running in incremental-polynomial time. We improve on this result by providing a polynomial delay and space algorithm enumerating minimal dominating sets in chordal bipartite graphs. Additionally, we show that the total and connected variants admit polynomial and incremental-polynomial delay algorithms, respectively, within the same class. This provides an alternative proof of a result by Golovach et al. for total dominating sets, and answers an open question for the connected variant. Finally, we give evidence that the techniques used in this paper cannot be generalized to bipartite graphs for (total) minimal dominating sets, unless P = NP, and show that enumerating minimal connected dominating sets in bipartite graphs is harder than enumerating minimal transversals in general hypergraphs.
Cite as

Emanuel Castelo, Oscar Defrain, and Guilherme C. M. Gomes. Enumerating Minimal Dominating Sets and Variants in Chordal Bipartite Graphs. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{castelo_et_al:LIPIcs.WADS.2025.15,
  author =	{Castelo, Emanuel and Defrain, Oscar and C. M. Gomes, Guilherme},
  title =	{{Enumerating Minimal Dominating Sets and Variants in Chordal Bipartite Graphs}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.15},
  URN =		{urn:nbn:de:0030-drops-242467},
  doi =		{10.4230/LIPIcs.WADS.2025.15},
  annote =	{Keywords: algorithmic enumeration, minimal dominating sets, connected dominating sets, total dominating sets, chordal bipartite graphs, sequential method, polynomial delay}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.90
Revisiting Directed Disjoint Paths on Tournaments (And Relatives)

Authors: Guilherme de C. M. Gomes, Raul Lopes, and Ignasi Sau

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In the Directed Disjoint Paths problem (k-DDP), we are given a digraph and k pairs of terminals, and the goal is to find k pairwise vertex-disjoint paths connecting each pair of terminals. Bang-Jensen and Thomassen [SIAM J. Discrete Math. 1992] claimed that k-DDP is NP-complete on tournaments, and this result triggered a very active line of research about the complexity of the problem on tournaments and natural superclasses. We identify a flaw in their proof, which has been acknowledged by the authors, and provide a new NP-completeness proof. From an algorithmic point of view, Fomin and Pilipczuk [J. Comb. Theory B 2019] provided an FPT algorithm for the edge-disjoint version of the problem on semicomplete digraphs, and showed that their technique cannot work for the vertex-disjoint version. We overcome this obstacle by showing that the version of k-DDP where we allow congestion c on the vertices is FPT on semicomplete digraphs provided that c is greater than k/2. This is based on a quite elaborate irrelevant vertex argument inspired by the edge-disjoint version, and we show that our choice of c is best possible for this technique, with a counterexample with no irrelevant vertices when c ≤ k/2. We also prove that k-DDP on digraphs that can be partitioned into h semicomplete digraphs is W[1]-hard parameterized by k+h, which shows that the XP algorithm presented by Chudnovsky, Scott, and Seymour [J. Comb. Theory B 2019] is essentially optimal.
Cite as

Guilherme de C. M. Gomes, Raul Lopes, and Ignasi Sau. Revisiting Directed Disjoint Paths on Tournaments (And Relatives). In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 90:1-90:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dec.m.gomes_et_al:LIPIcs.ICALP.2025.90,
  author =	{de C. M. Gomes, Guilherme and Lopes, Raul and Sau, Ignasi},
  title =	{{Revisiting Directed Disjoint Paths on Tournaments (And Relatives)}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{90:1--90:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.90},
  URN =		{urn:nbn:de:0030-drops-234678},
  doi =		{10.4230/LIPIcs.ICALP.2025.90},
  annote =	{Keywords: directed graphs, tournaments, semicomplete digraphs, directed disjoint paths, congestion, parameterized complexity, directed pathwidth}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2024.25
Matching (Multi)Cut: Algorithms, Complexity, and Enumeration

Authors: Guilherme C. M. Gomes, Emanuel Juliano, Gabriel Martins, and Vinicius F. dos Santos

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
A matching cut of a graph is a partition of its vertex set in two such that no vertex has more than one neighbor across the cut. The Matching Cut problem asks if a graph has a matching cut. This problem, and its generalization d-cut, has drawn considerable attention of the algorithms and complexity community in the last decade, becoming a canonical example for parameterized enumeration algorithms and kernelization. In this paper, we introduce and study a generalization of Matching Cut, which we have named Matching Multicut: can we partition the vertex set of a graph in at least 𝓁 parts such that no vertex has more than one neighbor outside its part? We investigate this question in several settings. We start by showing that, contrary to Matching Cut, it is NP-hard on cubic graphs but that, when 𝓁 is a parameter, it admits a quasi-linear kernel. We also show an 𝒪(𝓁^{n/2}) time exact exponential algorithm for general graphs and a 2^{𝒪(tlog t)}n^{𝒪(1)} time algorithm for graphs of treewidth at most t. We then turn our attention to parameterized enumeration aspects of matching multicuts. First, we generalize the quadratic kernel of Golovach et. al for Enum Matching Cut parameterized by vertex cover, then use it to design a quadratic kernel for Enum Matching (Multi)cut parameterized by vertex-deletion distance to co-cluster. Our final contributions are on the vertex-deletion distance to cluster parameterization, where we show an FPT-delay algorithm for Enum Matching Multicut but that no polynomial kernel exists unless NP ⊆ coNP/poly; we highlight that we have no such lower bound for Enum Matching Cut and consider it our main open question.
Cite as

Guilherme C. M. Gomes, Emanuel Juliano, Gabriel Martins, and Vinicius F. dos Santos. Matching (Multi)Cut: Algorithms, Complexity, and Enumeration. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{c.m.gomes_et_al:LIPIcs.IPEC.2024.25,
  author =	{C. M. Gomes, Guilherme and Juliano, Emanuel and Martins, Gabriel and F. dos Santos, Vinicius},
  title =	{{Matching (Multi)Cut: Algorithms, Complexity, and Enumeration}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{25:1--25:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.25},
  URN =		{urn:nbn:de:0030-drops-222514},
  doi =		{10.4230/LIPIcs.IPEC.2024.25},
  annote =	{Keywords: Matching Cut, Matching Multicut, Enumeration, Parameterized Complexity, Exact exponential algorithms}
}
Document
DOI: 10.4230/OASIcs.Tannen.8
AutoML for Explainable Anomaly Detection (XAD)

Authors: Nikolaos Myrtakis, Ioannis Tsamardinos, and Vassilis Christophides

Published in: OASIcs, Volume 119, The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen (2024)

Abstract
Numerous algorithms have been proposed for detecting anomalies (outliers, novelties) in an unsupervised manner. Unfortunately, it is not trivial, in general, to understand why a given sample (record) is labelled as an anomaly and thus diagnose its root causes. We propose the following reduced-dimensionality, surrogate model approach to explain detector decisions: approximate the detection model with another one that employs only a small subset of features. Subsequently, samples can be visualized in this low-dimensionality space for human understanding. To this end, we develop PROTEUS, an AutoML pipeline to produce the surrogate model, specifically designed for feature selection on imbalanced datasets. The PROTEUS surrogate model can not only explain the training data, but also the out-of-sample (unseen) data. In other words, PROTEUS produces predictive explanations by approximating the decision surface of an unsupervised detector. PROTEUS is designed to return an accurate estimate of out-of-sample predictive performance to serve as a metric of the quality of the approximation. Computational experiments confirm the efficacy of PROTEUS to produce predictive explanations for different families of detectors and to reliably estimate their predictive performance in unseen data. Unlike several ad-hoc feature importance methods, PROTEUS is robust to high-dimensional data.
Cite as

Nikolaos Myrtakis, Ioannis Tsamardinos, and Vassilis Christophides. AutoML for Explainable Anomaly Detection (XAD). In The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen. Open Access Series in Informatics (OASIcs), Volume 119, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{myrtakis_et_al:OASIcs.Tannen.8,
  author =	{Myrtakis, Nikolaos and Tsamardinos, Ioannis and Christophides, Vassilis},
  title =	{{AutoML for Explainable Anomaly Detection (XAD)}},
  booktitle =	{The Provenance of Elegance in Computation - Essays Dedicated to Val Tannen},
  pages =	{8:1--8:23},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-320-1},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{119},
  editor =	{Amarilli, Antoine and Deutsch, Alin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Tannen.8},
  URN =		{urn:nbn:de:0030-drops-201049},
  doi =		{10.4230/OASIcs.Tannen.8},
  annote =	{Keywords: Anomaly Explanation, Predictive Explanation, Anomaly Interpretation, Explainable AI}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.9
Minimum Separator Reconfiguration

Authors: Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinicius F. dos Santos, and Tom C. van der Zanden

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
We study the problem of reconfiguring one minimum s-t-separator A into another minimum s-t-separator B in some n-vertex graph G containing two non-adjacent vertices s and t. We consider several variants of the problem as we focus on both the token sliding and token jumping models. Our first contribution is a polynomial-time algorithm that computes (if one exists) a minimum-length sequence of slides transforming A into B. We additionally establish that the existence of a sequence of jumps (which need not be of minimum length) can be decided in polynomial time (by an algorithm that also outputs a witnessing sequence when one exists). In contrast, and somewhat surprisingly, we show that deciding if a sequence of at most 𝓁 jumps can transform A into B is an NP-complete problem. To complement this negative result, we investigate the parameterized complexity of what we believe to be the two most natural parameterized counterparts of the latter problem; in particular, we study the problem of computing a minimum-length sequence of jumps when parameterized by the size k of the minimum s-t-separators and when parameterized by the number 𝓁 of jumps. For the first parameterization, we show that the problem is fixed-parameter tractable, but does not admit a polynomial kernel unless NP ⊆ coNP/poly. We complete the picture by designing a kernel with 𝒪(𝓁²) vertices and edges for the length 𝓁 of the sequence as a parameter.
Cite as

Guilherme C. M. Gomes, Clément Legrand-Duchesne, Reem Mahmoud, Amer E. Mouawad, Yoshio Okamoto, Vinicius F. dos Santos, and Tom C. van der Zanden. Minimum Separator Reconfiguration. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{c.m.gomes_et_al:LIPIcs.IPEC.2023.9,
  author =	{C. M. Gomes, Guilherme and Legrand-Duchesne, Cl\'{e}ment and Mahmoud, Reem and Mouawad, Amer E. and Okamoto, Yoshio and F. dos Santos, Vinicius and C. van der Zanden, Tom},
  title =	{{Minimum Separator Reconfiguration}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.9},
  URN =		{urn:nbn:de:0030-drops-194288},
  doi =		{10.4230/LIPIcs.IPEC.2023.9},
  annote =	{Keywords: minimum separators, combinatorial reconfiguration, parameterized complexity, kernelization}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.19
Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization

Authors: Guilherme C. M. Gomes and Ignasi Sau

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
A matching cut is a partition of the vertex set of a graph into two sets A and B such that each vertex has at most one neighbor in the other side of the cut. The Matching Cut problem asks whether a graph has a matching cut, and has been intensively studied in the literature. Motivated by a question posed by Komusiewicz et al. [IPEC 2018], we introduce a natural generalization of this problem, which we call d-Cut: for a positive integer d, a d-cut is a bipartition of the vertex set of a graph into two sets A and B such that each vertex has at most d neighbors across the cut. We generalize (and in some cases, improve) a number of results for the Matching Cut problem. Namely, we begin with an NP-hardness reduction for d-Cut on (2d+2)-regular graphs and a polynomial algorithm for graphs of maximum degree at most d+2. The degree bound in the hardness result is unlikely to be improved, as it would disprove a long-standing conjecture in the context of internal partitions. We then give FPT algorithms for several parameters: the maximum number of edges crossing the cut, treewidth, distance to cluster, and distance to co-cluster. In particular, the treewidth algorithm improves upon the running time of the best known algorithm for Matching Cut. Our main technical contribution, building on the techniques of Komusiewicz et al. [IPEC 2018], is a polynomial kernel for d-Cut for every positive integer d, parameterized by the distance to a cluster graph. We also rule out the existence of polynomial kernels when parameterizing simultaneously by the number of edges crossing the cut, the treewidth, and the maximum degree. Finally, we provide an exact exponential algorithm slightly faster than the naive brute force approach running in time O^*(2^n).
Cite as

Guilherme C. M. Gomes and Ignasi Sau. Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{c.m.gomes_et_al:LIPIcs.IPEC.2019.19,
  author =	{C. M. Gomes, Guilherme and Sau, Ignasi},
  title =	{{Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.19},
  URN =		{urn:nbn:de:0030-drops-114809},
  doi =		{10.4230/LIPIcs.IPEC.2019.19},
  annote =	{Keywords: matching cut, bounded degree cut, parameterized complexity, FPT algorithm, polynomial kernel, distance to cluster}
}
  • Refine by Type
  • 11 Document/PDF
  • 7 Document/HTML

  • Refine by Publication Year
  • 7 2025
  • 2 2024
  • 1 2023
  • 1 2019

  • Refine by Author
  • 5 C. M. Gomes, Guilherme
  • 3 Sau, Ignasi
  • 2 F. dos Santos, Vinicius
  • 1 Ahn, Jungho
  • 1 Bougeret, Marin
  • Show More...

  • Refine by Series/Journal
  • 10 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 5 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Computing methodologies → Anomaly detection
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Enumeration
  • Show More...

  • Refine by Keyword
  • 3 parameterized complexity
  • 2 Enumeration
  • 2 matching cut
  • 1 Anomaly Explanation
  • 1 Anomaly Interpretation
  • 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