EDBT 2026 Demo / reviewers in the wild / expert
Dieter Rautenbach
dblp:61/1118
· DBLP profile ↗
14ranked-venue papers in the field
2as first author
2since 2021 · last 2025
0000-0002-7214-042XORCID · verified
Domains — venue-derived; a paper can count in several
Other / Interdisciplinary · 14 (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. | 2 |
| 2023 | Efficiently recognizing graphs with equal independence and annihilation numbers
Johannes Rauch, Dieter Rautenbach |
Inf. Process. Lett. | 2 |
| 2018 | On the hardness of finding the geodetic number of a subcubic graph
Letícia Rodrigues Bueno, Lucia Draque Penso, Fábio Protti, Victor R. Ramos, Dieter Rautenbach, Uéverton S. Souza |
Inf. Process. Lett. | 5 |
| 2018 | On some graphs with a unique perfect matching
Steven Chaplick, Maximilian Fürst, Frédéric Maffray, Dieter Rautenbach |
Inf. Process. Lett. | 4 |
| 2017 | Decycling with a matching
Carlos V. G. C. Lima, Dieter Rautenbach, Uéverton S. Souza, Jayme Luiz Szwarcfiter |
Inf. Process. Lett. | 2 |
| 2014 | Graphs of interval count two with a given partition
Felix Joos, Christian Löwenstein, Fabiano de S. Oliveira, Dieter Rautenbach, Jayme Luiz Szwarcfiter |
Inf. Process. Lett. | 4 |
| 2012 | Characterization and recognition of Radon-independent sets in split graphs
Mitre Costa Dourado, Dieter Rautenbach, Vinícius Fernandes dos Santos, Jayme Luiz Szwarcfiter |
Inf. Process. Lett. | 2 |
| 2010 | The repeater tree construction problem
Christoph Bartoschek, Stephan Held, Jens Maßberg, Dieter Rautenbach, Jens Vygen |
Inf. Process. Lett. | 4 |
| 2009 | Binary trees with choosable edge lengths
Jens Maßberg, Dieter Rautenbach |
Inf. Process. Lett. | 2 |
| 2009 | An Omega(nlogn) lower bound for computing the sum of even-ranked elements
Marc Mörig, Dieter Rautenbach, Michiel H. M. Smid, Jan Tusch |
Inf. Process. Lett. | 2 |
| 2009 | On packing shortest cycles in graphs
Dieter Rautenbach, Friedrich Regen |
Inf. Process. Lett. | 1 |
| 2005 | Lower bounds on treespan
Dieter Rautenbach |
Inf. Process. Lett. | 1 |
| 2004 | Note on the connectivity of line graphs
Angelika Hellwig, Dieter Rautenbach, Lutz Volkmann |
Inf. Process. Lett. | 2 |
| 2003 | Some results on graphs without long induced paths
Vadim V. Lozin, Dieter Rautenbach |
Inf. Process. Lett. | 2 |