This paper continues the study of a new variant of graph coloring with a connectivity constraint recently introduced by Hsieh et al. (2024). A path in a vertex-colored graph is called conflict-free if there is a color that appears exactly once on its vertices. A connected graph is said to be strongly conflict-free vertex-connection k -colorable if it admits a (proper) vertex k -coloring such that any two distinct vertices are connected by a conflict-free shortest path. Among others, we show that deciding, for a given graph G and an integer k , whether G is strongly conflict-free vertex-connection k -colorable is fixed-parameter tractable when parameterized by the vertex cover number. But under the standard complexity-theoretic assumption NP ⊈ coNP/poly , deciding, for a given graph G , whether G is strongly conflict-free vertex-connection 3-colorable does not admit a polynomial kernel, even for bipartite graphs. This kernel lower bound is in stark contrast to the ordinal k - coloring problem which is known to admit a polynomial kernel when parameterized by the vertex cover number.

A stable cutset in a graph G is a set S ⊆ V ( G ) such that vertices of S are pairwise non-adjacent and such that G − S is disconnected, i.e., it is both stable (or independent) set and a cutset (or separator). Unlike general cutsets, it is NP -complete to determine whether a given graph G has any stable cutset. Recently, Rauch et al. [FCT 2023 & JCSS 2025] gave a number of fixed-parameter tractable (FPT) algorithms, running in time f ( k ) ⋅ | V ( G ) | c , for Stable Cutset under a variety of parameters k such as the size of a (given) dominating set, the size of an odd cycle transversal, or the deletion distance to P 5 -free graphs. Earlier works imply FPT algorithms relative to clique-width and relative to solution size. We complement these findings by giving the first results on the existence of polynomial kernelizations for Stable Cutset , i.e., efficient preprocessing algorithms that return an equivalent instance of size polynomial in the parameter value. Under the standard assumption that NP ⊈ coNP/poly , we show that no polynomial kernelization is possible relative to the deletion distance to a single path, generalizing deletion distance to various graph classes, nor by the size of a (given) dominating set. We also show that under the same assumption no polynomial kernelization is possible relative to solution size, i.e., given ( G , k ) answering whether there is a stable cutset of size at most k . On the positive side, we show polynomial kernelizations for parameterization by modulators to a single clique, to a cluster or a co-cluster graph, and by twin cover.

In a graph, a (perfect) matching cut is an edge cut that is a (perfect) matching. matching cut ( mc ), respectively, perfect matching cut ( pmc ), is the problem of deciding whether a given graph has a matching cut, respectively, a perfect matching cut. The disconnected perfect matching problem ( dpm ) is to decide if a graph has a perfect matching that contains a matching cut. Solving an open problem posed in [Lucke, Paulusma, Ries (ISAAC 2022, Algorithmica 2023)], we show that pmc is NP -complete in graphs without induced 14-vertex path P 14 . Our reduction also works simultaneously for mc and dpm , improving the previous hardness results of mc on P 15 -free graphs and of dpm on P 19 -free graphs to P 14 -free graphs for both problems. Actually, we prove a slightly stronger result: within P 14 -free 8-chordal graphs (graphs without chordless cycles of length at least 9), it is hard to distinguish between those without matching cuts (respectively, perfect matching cuts, disconnected perfect matchings) and those in which every matching cut is a perfect matching cut. Moreover, assuming the Exponential Time Hypothesis, none of these problems can be solved in 2 o ( n ) time for n -vertex P 14 -free 8-chordal graphs. On the positive side, we show that, as for mc [Moshi (JGT 1989)], dpm and pmc are polynomially solvable when restricted to 4-chordal graphs. Together with the negative results, this partly answers an open question on the complexity of pmc in k -chordal graphs asked in [Le, Telle (WG 2021, TCS 2022) & Lucke, Paulusma, Ries (MFCS 2023, TCS 2024)].

Abstract The well-known Cluster Vertex Deletion problem (cluster-vd) asks for a given graph G and an integer k whether it is possible to delete a set S of at most k vertices of G such that the resulting graph $$G-S$$ G - S is a cluster graph (a disjoint union of cliques). We give a complete characterization of graphs H for which cluster-vd on H-free graphs is polynomially solvable and for which it is $$\textsf{NP}$$ NP -complete. Moreover, in the $$\textsf{NP}$$ NP -completeness cases, cluster-vd cannot be solved in sub-exponential time in the vertex number of the H-free input graphs unless the Exponential-Time Hypothesis fails. We also consider the connected variant of cluster-vd, the Connected Cluster Vertex Deletion problem (connected cluster-vd), in which the set S has to induce a connected subgraph of G. It turns out that connected cluster-vd admits the same complexity dichotomy for H-free graphs. Our results enlarge a list of rare dichotomy theorems for well-studied problems on H-free graphs.

An enumeration kernel as defined by Creignou et al. (2017) [11] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a solution-lifting algorithm that efficiently enumerates all solutions from the set of the solutions of the kernel. We propose to consider two new versions of enumeration kernels by asking that the solutions of the original instance can be enumerated in polynomial time or with polynomial delay from the kernel solutions. Using the NP-hard Matching Cut problem parameterized by structural parameters such as the vertex cover number or the cyclomatic number of the input graph, we show that the new enumeration kernels present a useful notion of data reduction for enumeration problems which allows to compactly represent the set of feasible solutions.

Abstract In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be $${\mathsf {NP}}$$ NP -complete. While Matching Cut is trivial for graphs with minimum degree at most one, it is $${\mathsf {NP}}$$ NP -complete on graphs with minimum degree two. In this paper, we show that, for any given constant $$c>1$$ c > 1 , Matching Cut is $${\mathsf {NP}}$$ NP -complete in the class of graphs with minimum degree c and this restriction of Matching Cut has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant $$\epsilon >0$$ ϵ > 0 , Matching Cut remains $${\mathsf {NP}}$$ NP -complete in the class of n-vertex (bipartite) graphs with unbounded minimum degree $$\delta >n^{1-\epsilon }$$ δ > n 1 - ϵ . We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree $$\delta \ge 3$$ δ ≥ 3 in $$O^*(\lambda ^n)$$ O ∗ ( λ n ) time, where $$\lambda$$ λ is the positive root of the polynomial $$x^{\delta +1}-x^{\delta }-1$$ x δ + 1 - x δ - 1 . Despite the hardness results, this is a very fast exact exponential-time algorithm for Matching Cut on graphs with large minimum degree; for instance, the running time is $$O^*(1.0099^n)$$ O ∗ ( 1 . 0099 n ) on graphs with minimum degree $$\delta \ge 469$$ δ ≥ 469 . Complementing our hardness results, we show that, for any two fixed constants $$1< c <4$$ 1 < c < 4 and $$c^{\prime }\ge 0$$ c ′ ≥ 0 , Matching Cut is solvable in polynomial time for graphs with large minimum degree $$\delta \ge \frac{1}{c}n-c^{\prime }$$ δ ≥ 1 c n - c ′ .

In a graph, a matching cut is an edge cut that is a matching. Matching Cut, which is known to be NP-complete, is the problem of deciding whether or not a given graph G has a matching cut. In this paper we show that Matching Cut admits a quadratic-vertex kernel for the parameter distance to cluster and a linear-vertex kernel for the parameter distance to clique. We further provide an O^*(2^{dc(G)}) time and an O^*(2^{dc^-}(G)}) time FPT algorithm for Matching Cut, where dc(G) and dc^-(G) are the distance to cluster and distance to co-cluster, respectively. We also improve the running time of the best known branching algorithm to solve Matching Cut from O^*(1.4143^n) to O^*(1.3803^n). Moreover, we point out that, unless NP subseteq coNP/poly, Matching Cut does not admit a polynomial kernel when parameterized by treewidth.

The square of a graph H, denoted H^2, is obtained from H by adding new edges between two distinct vertices whenever their distance in H is two. The half-squares of a bipartite graph B=(X,Y,E_B) are the subgraphs of B^2 induced by the color classes X and Y, B^2[X] and B^2[Y]. For a given graph G=(V,E_G), if G=B^2[V] for some bipartite graph B=(V,W,E_B), then B is a representation of G and W is the set of points in B. If in addition B is planar, then G is also called a map graph and B is a witness of G [Chen, Grigni, Papadimitriou. Map graphs. J. ACM , 49 (2) (2002) 127-138]. \nWhile Chen, Grigni, Papadimitriou proved that any map graph G=(V,E_G) has a witness with at most 3|V|-6 points, we show that, given a map graph G and an integer k, deciding if G admits a witness with at most k points is NP-complete. As a by-product, we obtain NP-completeness of edge clique partition on planar graphs; until this present paper, the complexity status of edge clique partition for planar graphs was previously unknown. \nWe also consider half-squares of tree-convex bipartite graphs and prove the following complexity dichotomy: Given a graph G=(V,E_G) and an integer k, deciding if G=B^2[V] for some tree-convex bipartite graph B=(V,W,E_B) with |W|<=k points is NP-complete if G is non-chordal dually chordal and solvable in linear time otherwise. Our proof relies on a characterization of half-squares of tree-convex bipartite graphs, saying that these are precisely the chordal and dually chordal graphs.

In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP-complete even when restricted to bipartite graphs. It has been proved that Matching Cut is polynomially solvable for graphs of diameter two. In this paper, we show that, for any fixed integer d geq 4, Matching Cut is NP-complete in the class of graphs of diameter d. This almost resolves an open problem posed by Borowiecki and Jesse-Józefczyk in [Matching cutsets in graphs of diameter 2, Theoretical Computer Science 407 (2008) 574-582]. We then show that, for any fixed integer d geq 5, Matching Cut is NP-complete even when restricted to the class of bipartite graphs of diameter d. Complementing the hardness results, we show that Matching Cut is in polynomial-time solvable in the class of bipartite graphs of diameter at most three, and point out a new and simple polynomial-time algorithm solving Matching Cut in graphs of diameter 2.

Graph $G$ is the square of graph $H$ if two vertices $x,y$ have an edge in $G$ if and only if $x,y$ are of distance at most two in $H$. Given $H$ it is easy to compute its square $H^2$, however Motwani and Sudan proved that it is NP-complete to determine if a given graph $G$ is the square of some graph $H$ (of girth $3$). In this paper we consider the characterization and recognition problems of graphs that are squares of graphs of small girth, i.e. to determine if $G=H^2$ for some graph $H$ of small girth. The main results are the following. \begin{itemize} \item There is a graph theoretical characterization for graphs that are squares of some graph of girth at least $7$. A corollary is that if a graph $G$ has a square root $H$ of girth at least $7$ then $H$ is unique up to isomorphism. \item There is a polynomial time algorithm to recognize if $G=H^2$ for some graph $H$ of girth at least $6$. \item It is NP-complete to recognize if $G=H^2$ for some graph $H$ of girth $4$. \end{itemize} These results almost provide a dichotomy theorem for the complexity of the recognition problem in terms of girth of the square roots. The algorithmic and graph theoretical results generalize previous results on tree square roots, and provide polynomial time algorithms to compute a graph square root of small girth if it exists. Some open questions and conjectures will also be discussed.

A graph G is the k-leaf power of a tree T if its vertices are leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most k . Then T is a k-leaf root of G . This notion was introduced and studied by Nishimura, Ragde, and Thilikos [2002], motivated by the search for underlying phylogenetic trees. Their results imply an O ( n 3 )-time recognition algorithm for 4-leaf powers. Recently, Rautenbach [2006] as well as Dom et al. [2005] characterized 4-leaf powers without true twins in terms of forbidden subgraphs. We give new characterizations for 4-leaf powers and squares of trees by a complete structural analysis. As a consequence, we obtain a conceptually simple linear-time recognition of 4-leaf powers.

Two graphs G and H with the same vertex set Vare P 4 -isomorphic if every four vertices {a,b,c,d} \subseteq V$ induce a chordless path (denoted by P 4 ) in G if and only if they induce a P 4 in H. We call a graph split-perfect if it is P 4 -isomorphic to a split graph (i.e., a graph being partitionable into a clique and a stable set). This paper characterizes the new class of split-perfect graphs using the concepts of homogeneous sets and p-connected graphs and leads to a linear time recognition algorithm for split-perfect graphs, as well as efficient algorithms for classical optimization problems on split-perfect graphs based on the primeval decomposition of graphs. The optimization results considerably extend previous ones on smaller classes such as P 4 --sparse graphs, P 4 -lite graphs, P 4 --laden graphs, and (7,3)-graphs. Moreover, split-perfect graphs form a new subclass of brittle graphs containing the superbrittle graphs for which a new characterization is obtained leading to linear time recognition.

In a graph coloring, each color class induces a disjoint union of isolated vertices. A graph subcoloring generalizes this concept, since here each color class induces a disjoint union of complete graphs. Erdos and, independently, Albertson et al., proved that every graph of maximum degree at most 3 has a 2-subcoloring. We point out that this fact is best possible with respect to degree constraints by showing that the problem of recognizing 2-subcolorable graphs with maximum degree 4 is NP-complete, even when restricted to triangle-free planar graphs. Moreover, in general, for fixed k, recognizing k-subcolorable graphs is NP-complete on graphs with maximum degree at most k 2 . In contrast, we show that, for arbitrary k, k-SUBCOLORABILITY can be decided in linear time on graphs with bounded treewidth and on graphs with bounded cliquewidth (including cographs as a specific case).

A graph is a split graph if its vertices can be partitioned into a clique and a stable set. A graph is a k-split graph if its vertices can be partitioned into k sets, each of which induces a split graph. We show that the strong perfect graph conjecture is true for 2-split graphs and we design a polynomial algorithm to recognize a perfect 2-split graph.

In a graph G, a spanning tree T is called a tree t-spanner of G if the distance between any two vertices in T is at most t times their distance in G. While the complexity of finding a tree t-spanner of a given graph is known for any fixed t ≠ 3, the case t = 3 still remains open. In this article, we show that each directed path graph G has a tree 3-spanner T by means of a linear-time algorithm constructing T. Moreover, the output tree 3-spanner T is optimal in the sense that G has a tree 2-spanner if and only if T is a tree 2-spanner of G. © 1999 John Wiley & Sons, Inc. Networks 34: 81–87, 1999