تقرير
On Conflict-Free Cuts: Algorithms and Complexity
| العنوان: | On Conflict-Free Cuts: Algorithms and Complexity |
|---|---|
| المؤلفون: | Rauch, Johannes, Rautenbach, Dieter, Souza, Uéverton S. |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Mathematics - Combinatorics, 05C85, 68Q25, 68R10, F.2.2, G.2.2 |
| الوصف: | 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 $\hat{G}$ on the edges of $G$, and we ask for an edge-cutset $M$ of $G$ that is independent in $\hat{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 $\textsf{NP}$-complete even when the maximum degree of $G$ is 5 and $\hat{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 $\textsf{W[1]}$-hardness even when $G$ has a feedback vertex set of size one, and the clique cover number of $\hat{G}$ is the parameter. Since the clique cover number of $\hat{G}$ is an upper bound on the independence number of $\hat{G}$ and thus the solution size, this implies $\textsf{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. Comment: 13 pages, 3 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2311.01077 |
| رقم الأكسشن: | edsarx.2311.01077 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |