DIKUL - logo
E-viri
Celotno besedilo
Recenzirano Odprti dostop
  • On conflict-free cuts: Algo...
    Rauch, Johannes; Rautenbach, Dieter; Souza, Uéverton S.

    Information processing letters, 01/2025, Letnik: 187
    Journal Article

    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 W1-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 W1-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. •We propose Conflict-Free Cut, which is a very natural generalization of Matching Cut.•Conflict-Free Cut remains NP-complete, even when Δ(G)≤5 and Gˆ is 1-regular.•Conflict-Free Cut is not solvable in 2o(n+m) time unless ETH fails.•We consider parameterized variants of Conflict-Free Cut and give first results.•Conflict-Free Cut is related to SAT and solvable in 1.4769n+o(n)-time.