TL;DR
This paper introduces and analyzes "Class Domination Coloring" (cd-coloring), a graph coloring variant where each color class must be "dominated" by a vertex. The authors provide an exact exponential-time algorithm for finding the cd-chromatic number and establish fixed-parameter tractability (FPT) for this problem on specific graph classes, while also proving NP-hardness for related deletion problems.
What Problem Does This Paper Address?
The paper tackles the problem of "Class Domination Coloring" (cd-coloring) in graphs. A standard graph coloring assigns colors to vertices such that adjacent vertices have different colors. In cd-coloring, an additional constraint is imposed: for every color used, the set of vertices assigned that color (the color class) must be "dominated" by at least one vertex. Domination here means that there exists a vertex that is adjacent to all vertices in that color class. The minimum number of colors needed for such a coloring is called the cd-chromatic number, denoted $\chi_{cd}(G)$.
The authors investigate two main problems related to cd-coloring:
- Finding the cd-chromatic number: Given a graph $G$, what is $\chi_{cd}(G)$?
- CD-PARTIZATION: Given a graph $G$ and integers $k$ and $q$, can we delete at most $k$ vertices from $G$ such that the resulting graph has a cd-chromatic number of at most $q$?
These problems are explored through the lens of exact exponential-time algorithms and parameterized complexity, aiming to find efficient solutions for NP-hard problems by leveraging specific parameters.
Methods
The paper employs a combination of algorithmic techniques and theoretical computer science concepts:
- Exact Exponential-Time Algorithm: For finding the cd-chromatic number of a general graph, the authors present an algorithm with a running time of $O(2^n n^4 \log n)$. This approach utilizes polynomial multiplication via Fast Fourier Transform and concepts related to characteristic polynomials of set families.
- Fixed-Parameter Tractability (FPT): The authors demonstrate that CD-COLORING is FPT with respect to the number of colors $q$ on chordal graphs and graphs of girth at least 5. This means that for these graph classes, efficient algorithms exist when $q$ is small, even if the graph is large. They also show that CD-COLORING is FPT when parameterized by both the number of colors and the treewidth of the graph, using Courcelle's theorem and MSO logic.
- Kernelization: For graphs of girth at least 5, they show that CD-COLORING admits a polynomial kernel of size $O(q^3)$, meaning the problem instance can be reduced to a smaller size without losing solvability, parameterized by $q$.
- NP-Hardness Proofs: For the CD-PARTIZATION problem, they prove NP-hardness for general graphs when $q \ge 2$. They also establish NP-hardness for split graphs.
- Reduction Techniques: The NP-hardness proofs often involve reductions from known NP-hard problems like SET COVER, VERTEX COVER, and ODD CYCLE TRANSVERSAL.
- Specialized Algorithms for Deletion Problems: For the CD-PARTIZATION problem, particularly for $q \in \{2,3\}$, they develop algorithms that leverage existing FPT algorithms for VERTEX COVER and ODD CYCLE TRANSVERSAL as subroutines. These algorithms are designed to handle specific types of graph structures that result from deleting vertices.
Datasets
Not discussed in the paper. The paper focuses on theoretical algorithms and complexity analysis on general graph classes, not on empirical evaluation using specific datasets.
Key Insights and Ideas
- CD-Coloring is distinct from standard coloring: The domination constraint adds significant complexity, making problems related to it behave differently from standard graph coloring.
- FPT on restricted graph classes: While CD-COLORING is NP-hard in general, it becomes tractable on structured graph classes like chordal graphs and graphs with large girth, highlighting the importance of graph structure in algorithmic design.
- Kernelization for specific graph classes: The existence of a polynomial kernel for graphs with girth at least 5 is a strong theoretical result, indicating efficient preprocessing is possible for this problem on these graphs.
- CD-PARTIZATION is hard: The deletion problem (CD-PARTIZATION) is shown to be NP-hard for general graphs and split graphs, even for small values of $q$, suggesting that removing vertices doesn't easily simplify the cd-coloring problem.
- Leveraging existing FPT tools: The paper effectively demonstrates how established FPT algorithms for problems like Vertex Cover and Odd Cycle Transversal can be adapted and combined to solve new parameterized problems.
Key Results
- Exact Algorithm: An $O(2^n n^4 \log n)$ time algorithm for computing the cd-chromatic number of a graph.
- FPT Results:
- CD-COLORING is FPT with respect to the number of colors $q$ on chordal graphs.
- CD-COLORING is FPT with respect to the number of colors $q$ and treewidth on general graphs.
- CD-COLORING on graphs with girth at least 5 admits a polynomial kernel of size $O(q^3)$.
- CD-PARTIZATION is FPT with respect to $q \in \{2,3\}$ and the deletion set size $k$ on general graphs.
- CD-PARTIZATION on split graphs is FPT with respect to parameters $q$ and $k$.
- NP-Hardness Results:
- CD-PARTIZATION is NP-complete for $q \in \{2,3\}$ on general graphs.
- CD-PARTIZATION is NP-hard on split graphs.
- CD-COLORING is NP-hard on chordal graphs.
Limitations and Future Work
- Kernelization Complexity: The paper notes that while CD-COLORING admits a polynomial kernel on graphs with girth at least 5, it is unlikely to admit a polynomial kernel on split graphs when parameterized by $q$ and $k$, suggesting further investigation into kernelization complexity on different graph classes.
- Treewidth Parameterization: The authors suggest exploring exact algorithms parameterized by treewidth and the number of colors, which could lead to more efficient solutions for graphs with bounded treewidth.
- Generalization of FPT: Investigating FPT for CD-COLORING parameterized by treewidth alone (without the number of colors) is mentioned as a future direction.
- Heriditary Properties: The paper points out that the class of graphs with cd-chromatic number at most $q$ is not hereditary, which limits the direct application of some general complexity results.
Summary updated