Dieter Rautenbach

dblp:61/1118 · DBLP profile ↗
← Back
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)
YearPublicationVenuePosition
2025 On conflict-free cuts: Algorithms and complexity
abstract
One 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