EDBT 2026 Demo / reviewers in the wild / expert
Johannes Rauch
dblp:02/10867
· DBLP profile ↗
2ranked-venue papers in the field
2as first author
2since 2021 · last 2025
0000-0002-6925-8830ORCID · corroborated
Domains — venue-derived; a paper can count in several
Other / Interdisciplinary · 2 (2 first)
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2025 | On conflict-free cuts: Algorithms and complexityabstractOne way to define the Matching Cut problem is: Given a graph G, is there an edge-cut M of G such that M is an independent set in the line graph of G? We propose the more general Conflict-Free Cut problem: Together with the graph G, we are given a so-called conflict graph Gˆ on the edges of G, and we ask for an edge-cutset M of G that is independent in Gˆ. Since conflict-free settings are popular generalizations of classical optimization problems and Conflict-Free Cut was not considered in the literature so far, we start the study of the problem. We show that the problem is NP-complete even when the maximum degree of G is 5 and Gˆ is 1-regular. The same reduction implies an exponential lower bound on the solvability based on the Exponential Time Hypothesis. We also give parameterized complexity results: We show that the problem is fixed-parameter tractable with the vertex cover number of G as a parameter, and we show W[1]-hardness even when G has a feedback vertex set of size one, and the clique cover number of Gˆ is the parameter. Since the clique cover number of Gˆ is an upper bound on the independence number of Gˆ and thus the solution size, this implies W[1]-hardness when parameterized by the cut size. We list polynomial-time solvable cases and interesting open problems. At last, we draw a connection to a symmetric variant of SAT. Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza |
Inf. Process. Lett. | 1 |
| 2023 | Efficiently recognizing graphs with equal independence and annihilation numbers
Johannes Rauch, Dieter Rautenbach |
Inf. Process. Lett. | 1 |