Simultaneous Feedback Edge Set: A Parameterized Perspective

Akanksha Agrawal, Fahad Panolan, Saket Saurabh, Meirav ZehaviAlgorithmica 2021 · OpenReview

TL;DR

This paper introduces and analyzes the "Simultaneous Feedback Edge Set" (Sim-FES) problem, a graph problem where we aim to remove a small number of edges to make multiple edge-colored subgraphs acyclic. They provide an FPT algorithm for the general case and show it's NP-hard for just three colors, while also developing a polynomial-time algorithm for two colors and a kernelization technique.

What Problem Does This Paper Address?

The paper tackles a variation of a classic graph problem called "Feedback Edge Set" (FES). In the standard FES problem, you're given a graph and an integer $k$, and you need to determine if you can remove at most $k$ edges to make the graph acyclic (a forest). This is important in areas like circuit design and database normalization.

This paper generalizes FES to "edge-colored" graphs. Imagine a graph where each edge has a set of "colors" assigned to it. For each color $i$, we can form a subgraph $G_i$ containing only the edges colored with $i$. The "Simultaneous Feedback Edge Set" (Sim-FES) problem asks: can we find a set of at most $k$ edges to remove from the original graph such that every subgraph $G_i$ becomes acyclic? This is a more complex scenario because removing one edge might break cycles in multiple subgraphs simultaneously, or it might only affect one. The authors note that for a single color ($\alpha=1$), this problem is easy (polynomial time), but it becomes much harder as the number of colors increases.

Methods

The core of the paper's algorithmic contributions lies in reducing Sim-FES to the $\alpha$-Matroid Parity problem. Matroids are a powerful combinatorial structure, and the Matroid Parity problem is a well-studied problem within parameterized complexity. The authors construct specific matroids (elongated co-graphic matroids) based on the input graph and its colorings.

  • FPT Algorithm: They design an FPT (Fixed-Parameter Tractable) algorithm for Sim-FES parameterized by $k$ (the number of edges to remove) and $\alpha$ (the number of colors). This algorithm runs in time $O(2^{\omega k \alpha + \alpha \log k} n^{O(1)})$, where $\omega$ is the matrix multiplication exponent. This means the runtime grows exponentially with $k$ and $\alpha$, but polynomially with the graph size $n$.
  • Polynomial Time for $\alpha=2$: A key insight is that their general FPT algorithm simplifies to a polynomial-time algorithm when $\alpha=2$.
  • NP-Hardness for $\alpha=3$: They prove that Sim-FES is NP-hard for $\alpha=3$ by reducing it from the Vertex Cover problem on cubic graphs. This also implies that no subexponential-time algorithm (unless ETH fails) exists for this case.
  • Kernelization: The authors develop a kernelization algorithm, which is a preprocessing step that reduces the size of the input instance while preserving its solvability. They show that Sim-FES admits a kernel with $(k\alpha)^{O(\alpha)}$ vertices.
  • Maximum Simultaneous Acyclic Subgraph: They also address a related problem, "Maximum Simultaneous Acyclic Subgraph," which asks for the largest set of edges that forms a simultaneous forest. They provide an FPT algorithm for this as well.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Matroid Parity as a Unifying Tool: The paper demonstrates the power of $\alpha$-Matroid Parity as a versatile tool for solving problems involving multiple constraints (here, multiple acyclicity requirements for different color classes).
  • Sharp Transition in Hardness: The fact that Sim-FES is polynomial for $\alpha=2$ but NP-hard for $\alpha=3$ highlights a critical threshold in the problem's complexity based on the number of colors.
  • Parameterization is Crucial: The FPT approach is essential here. The problem is intractable in general, but by parameterizing with respect to the number of edges to remove ($k$) and the number of colors ($\alpha$), they achieve efficient algorithms for many practical scenarios.
  • Edge Deletion vs. Vertex Deletion: The paper contrasts Sim-FES with its vertex-deletion counterpart (Sim-FVS), noting that Sim-FES is simpler for $\alpha=1$ but exhibits different hardness properties for higher $\alpha$.

Key Results

  • FPT Algorithm: An algorithm for Sim-FES running in $O(2^{\omega k \alpha + \alpha \log k} n^{O(1)})$ time.
  • Polynomial Time for $\alpha=2$: Sim-FES is solvable in polynomial time when $\alpha=2$.
  • NP-Hardness for $\alpha=3$: Sim-FES is NP-hard for $\alpha=3$.
  • Subexponential Lower Bound: Unless ETH fails, Sim-FES for $\alpha=3$ cannot be solved in $O^*(2^{o(k)})$ time.
  • Kernel: A kernel with $(k\alpha)^{O(\alpha)}$ vertices is provided.
  • Maximum Simultaneous Acyclic Subgraph: An FPT algorithm running in $O(2^{\omega q \alpha} n^{O(1)})$ time, where $q$ is the size of the output subgraph.

Limitations and Future Work

  • Parameter Dependency: The FPT algorithm's runtime depends exponentially on $\alpha$. The authors' lower bound results suggest this dependency might be inherent, especially for $\alpha=3$. Future work could explore whether the $\alpha$ dependency can be improved for specific cases or if tighter lower bounds can be established for general $\alpha$.
  • W[1]/W[2]-Hardness: The paper also establishes W[1] and W[2] hardness for Sim-FES parameterized by $k$ when $\alpha$ is related to $|V(G)|$ or $\log|V(G)|$. This indicates that the problem is likely not fixed-parameter tractable with respect to these parameters either, suggesting limitations for algorithms that rely solely on these parameters.
  • Practical Performance: While the algorithms are theoretically efficient (FPT), their practical performance on large graphs with many colors would depend on the constants hidden in the big-O notation and the specific values of $k$ and $\alpha$. Empirical studies could be valuable.

Summary updated

Abstract

Agrawal et al. (ACM Trans Comput Theory 10(4):18:1–18:25, 2018. https://doi.org/10.1145/3265027) studied a simultaneous variant of the classic Feedback Vertex Set problem, called Simultaneous Feedback Vertex Set (Sim-FVS). Here, we consider the edge variant of the problem, namely, Simultaneous Feedback Edge Set (Sim-FES). In this problem, the input is an n-vertex graph G, a positive integer k, and a coloring function col:\(E(G) \rightarrow 2^{[\alpha ]}\), and the objective is to check whether there is an edge subset S of cardinality k in G such that for each \(i \in [\alpha ]\), \(G_i - S\) is acyclic. Unlike the vertex variant of the problem, when \(\alpha =1\), the problem is equivalent to finding a maximal spanning forest and hence it is polynomial time solvable. We show that for \(\alpha =3\), Sim-FES is NP-hard, and does not admit an algorithm of running time \(2^{o(k)}n^{{{\mathcal {O}}}(1)}\) unless ETH fails. This hardness result is complimented by an FPT algorithm for Sim-FES running in time \(2^{\omega k \alpha +\alpha \log k} n^{{{\mathcal {O}}}(1)}\) where \(\omega\) is the exponent in the running time of matrix multiplication. The same algorithm gives a polynomial time algorithm for the case when \(\alpha =2\). We also give a kernel for Sim-FES with \((k\alpha )^{{\mathcal {O}}(\alpha )}\) vertices. Finally, we consider a “dual” version of the problem called Maximum Simultaneous Acyclic Subgraph and give an FPT algorithm with running time \(2^{\omega q \alpha }n^{{\mathcal {O}}(1)}\), where q is the number of edges in the output subgraph.
BibTeX
@inproceedings{agrawal2021simultaneous,
  author = {Akanksha Agrawal and Fahad Panolan and Saket Saurabh and Meirav Zehavi},
  title = {{Simultaneous Feedback Edge Set: A Parameterized Perspective}},
  booktitle = {Algorithmica},
  year = {2021},
  url = {https://openreview.net/forum?id=otFfHPzyCA},
}
Figure