Binary networked public goods games model situations in which players can choose whether to participate in an action at some cost which benefits players in their immediate vicinity within some typically social or infrastructural network. An important underlying assumption for this model is that participation in an action impacts the entire vicinity of participating players. However, there are numerous natural settings in which participation influences only a subset of the neighbors and is in fact more "interaction-specific''. In this work, we introduce a type of game that is more appropriate in such settings. We initiate the investigation of these games, by studying the complexity of deciding existence of their Nash equilibria in general and with respect to well-motivated structural restrictions on the network. The outcome is a comprehensive understanding of the complexity of computing Nash equilibria with respect to any combination of three natural properties of the network structure.

The Upper Clique Transversal (UCT) problem asks for the size of the largest minimal set of vertices intersecting all the maximal cliques of the input graph. This problem was recently introduced by Milanič and Uno [WG 2023], who studied its complexity on several graph classes. They showed that the problem is NP-hard on chordal graphs, and gave polynomial-time algorithms for UCT on split and on proper interval graphs. They left open the complexity of UCT on interval graphs. In this work we settle this question by giving a polynomial-time algorithm for UCT on interval graphs. We show that even on the more general class of rooted directed path graphs, which can be understood as a "tree-like version" of interval graphs, the problem remains polynomial-time solvable. On the negative side, we observe as consequences of the NP-hardness proof for chordal graphs due to Milanič and Uno that the problem is NP-hard on graphs of path-independence number two (interval graphs have path-independence number one) and on well-partitioned chordal graphs which lie between split and chordal graphs.

Given a graph and a colouring of its vertices, a rainbow path is a path such that all its internal nodes are coloured distinctly. A graph is rainbow vertex-connected if between every pair of vertices there exists a rainbow path. We study the problem of deciding whether a graph can be coloured using k colours such that it is rainbow vertex-connected. Heggernes et al. (MFCS, 2018) conjectured that if every induced subgraph in G has a dominating diametral path, then G can always be rainbow coloured with diam ( G ) − 1 colours. We confirm their conjecture for chordal, bipartite and claw-free diametral path graphs. We complement these results by showing the conjecture does not hold without the condition on every induced subgraph. In this case, even though diam ( G ) colours are enough, it is NP-complete to determine whether a graph with a dominating diametral path of length three can be rainbow coloured with two colours.

We study a generalization of the classic Global Min-Cut problem, called Global Label Min-Cut (or sometimes Global Hedge Min-Cut ): the edges of the input (multi)graph are labeled (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost. While the \(st\) -cut version of the problem is known to be \(\mathsf{NP}\) -hard, the above global cut version is known to admit a quasi-polynomial randomized \(n^{\mathcal{O}(\log\mathrm{OPT})}\) -time algorithm due to Ghaffari, Karger, and Panigrahi [SODA 2017]. They consider this as “strong evidence that this problem is in P ” . We show that this is actually not the case. We complete the study of the complexity of the Global Label Min-Cut problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time \((np)^{o(\log n/(\log\log n)^{2})}\) would contradict the Exponential Time Hypothesis, where \(n\) is the number of vertices, and \(p\) is the number of labels in the input. The key step for the lower bound is a proof that Global Label Min-Cut is \(\mathsf{W}\) [1]-hard when parameterized by the number of uncut labels . In other words, the problem is difficult in the regime where almost all labels need to be cut to disconnect the graph.

F-branchwidth is a framework for width measures of graphs, recently introduced by Eiben et al. [ITCS 2022], that captures tree-width, co-tree-width, clique-width, and mim-width, and several of their generalizations and interpolations. In this work, we search for algorithmic applications of F-branchwidth measures that do not have an equivalent counterpart in the literature so far. Our first contribution is a minimal set of eleven F-branchwidth measures such that each of the infinitely many F-branchwidth measures is equivalent to one of the eleven. We observe that for the FO Model Checking problem, each F-branchwidth is either equivalent to clique-width (and therefore has an FPT-algorithm by formula length plus the width) or the problem remains as hard as on general graphs even on graphs of constant width. Next, we study the number of equivalence classes of the neighborhood equivalence in a decomposition, which upper bounds the run time of the model checking algorithm for ACDN logic recently introduced by Bergougnoux et al. [SODA 2023]. We give structural lower bounds that show that for each F-branchwidth, an efficient model checking algorithm was already known or cannot be obtained via this method. Lastly, we classify the complexity of Independent Set parameterized by any F-branchwidth except for one open case. Also here, our contributions are lower bounds. In this context, we also prove that Independent Set on graphs of mim-width w cannot be solved in time n^o(w) unless the Exponential Time Hypothesis fails, answering an open question in the literature.

We show that, for every fixed positive integers $r$ and $k$, \textsc{Max-Weight List $r$-Colorable Induced Subgraph} admits a polynomial-time algorithm on $kP_3$-free graphs. This problem is a common generalization of \textsc{Max-Weight Independent Set}, \textsc{Odd Cycle Transversal} and \textsc{List $r$-Coloring}, among others. Our result has several consequences. First, it implies that, for every fixed $r \geq 5$, assuming $\mathsf{P}\neq \mathsf{NP}$, \textsc{Max-Weight List $r$-Colorable Induced Subgraph} is polynomial-time solvable on $H$-free graphs if and only if $H$ is an induced subgraph of either $kP_3$ or $P_5+kP_1$, for some $k \geq 1$. Second, it makes considerable progress toward a complexity dichotomy for \textsc{Odd Cycle Transversal} on $H$-free graphs, allowing to answer a question of Agrawal, Lima, Lokshtanov, Rz{ą}{ż}ewski, Saurabh, and Sharma [TALG 2024]. Third, it gives a short and self-contained proof of the known result of Chudnovsky, Hajebi, and Spirkl [Combinatorica 2024] that \textsc{List $r$-Coloring} on $kP_3$-free graphs is polynomial-time solvable for every fixed $r$ and $k$. We also consider two natural distance-$d$ generalizations of \textsc{Max-Weight Independent Set} and \textsc{List $r$-Coloring} and provide polynomial-time algorithms on $kP_3$-free graphs for every fixed integers $r$, $k$, and $d \geq 6$.

Abstract In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies W[t]-hardness for all t. It also indicates, via a conjecture by Pilipczuk and Wrochna (ACM Trans Comput Theory 9:1–36, 2018), that any XP algorithm for such problems is likely to require XP space. In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are Independent Set, Dominating Set, Odd Cycle Transversal, ( q -)Coloring, Max Cut, Maximum Regular Induced Subgraph, Feedback Vertex Set, Capacitated (Red-Blue) Dominating Set, Capacitated Vertex Cover and Bipartite Bandwidth.

An independent set in a graph \(G\) is a set of pairwise non-adjacent vertices. A graph \(G\) is bipartite if its vertex set can be partitioned into two independent sets. In the Odd Cycle Transversal problem, the input is a graph \(G\) along with a weight function w associating a rational weight with each vertex, and the task is to find a minimum weight vertex subset \(S\) in \(G\) such that \(G-S\) is bipartite; the weight of \(S\) , \(\text{w}(S)=\sum_{v\in S}\text{w}(v)\) . We show that Odd Cycle Transversal is polynomial-time solvable on graphs excluding \(P_{5}\) (a path on five vertices) as an induced subgraph. The problem was previously known to be polynomial-time solvable on \(P_{4}\) -free graphs and NP -hard on \(P_{6}\) -free graphs [Dabrowski, Feghali, Johnson, Paesani, Paulusma and Rzążewski, Algorithmica 2020]. Bonamy, Dabrowski, Feghali, Johnson and Paulusma [Algorithmica 2019] posed the existence of a polynomial-time algorithm on \(P_{5}\) -free graphs as an open problem. This was later re-stated by Rzążewski [Dagstuhl Reports, 9(6): 2019], by Chudnovsky, King, Pilipczuk, Rzążewski, and Spirkl [SIDMA 2021] who gave an algorithm with running time \(n^{O(\sqrt{n})}\) for the problem, and by Agrawal, Lima, Lokshtanov, Saurabh, and Sharma [SODA 2024] who gave a quasi-polynomial time algorithm.

For a tree decomposition $\mathcal{T}$ of a graph $G$, by $μ(\mathcal{T})$ we denote the size of a largest induced matching in $G$ all of whose edges intersect one bag of $\mathcal{T}$. Induced matching treewidth of a graph $G$ is the minimum value of $μ(\mathcal{T})$ over all tree decompositions $\mathcal{T}$ of $G$. Yolov [SODA 2018] proved that Max Weight Independent Set can be solved in polynomial time for graphs of bounded induced matching treewidth. In this paper we explore what other problems are tractable in such classes of graphs. As our main result, we give a polynomial-time algorithm for Min Weight Feedback Vertex Set. We also provide some positive results concerning packing induced subgraphs, which in particular imply a PTAS for the problem of finding a largest induced subgraph of bounded treewidth. These results suggest that in graphs of bounded induced matching treewidth, one could find in polynomial time a maximum-weight induced subgraph of bounded treewidth satisfying a given CMSO$_2$ formula. We conjecture that such a result indeed holds and prove it for graphs of bounded tree-independence number, which form a rich and important family of subclasses of graphs of bounded induced matching treewidth. We complement these algorithmic results with a number of complexity and structural results concerning induced matching treewidth.

An independent set in a graph G is a set of pairwise non-adjacent vertices. A graph G is bipartite if its vertex set can be partitioned into two independent sets. In the Odd Cycle Transversal problem, the input is a graph G along with a weight function w associating a rational weight with each vertex, and the task is to find a smallest weight vertex subset S in G such that G — S is bipartite; the weight of . We show that Odd Cycle Transversal admits an algorithm with running time on graphs excluding P5 (a path on five vertices) as an induced subgraph. The problem was previously known to be polynomial time solvable on P4-free graphs and NP-hard on P6-free graphs [Dabrowski, Feghali, Johnson, Paesani, Paulusma and Rzążewski, Algorithmica 2020]. Bonamy, Dabrowski, Feghali, Johnson and Paulusma [Algorithmica 2019] posed the existence of a polynomial time algorithm on P5-free graphs as an open problem, this was later re-stated by Rzążewski [Dagstuhl Reports, 9(6): 2019] and by Chudnovsky, King, Pilipczuk, Rzążewski, and Spirkl [SIDMA 2021], who gave an algorithm with running time . While our time algorithm falls short of completely resolving the complexity status of Odd Cycle Transversal on P5-free graphs it shows that the problem is not NP-hard unless every problem in NP is solvable in quasi-polynomial time.

Abstract We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by Campos and Silva (Algorithmica 80(1), 104–115, 2018) and Bonomo et al. (Graphs and Combinatorics 25(2), 153–167, 2009). This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is $$\textsf{FPT}$$ FPT when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the Fall Coloring problem within the same runtime bound. The running times of the clique-width based algorithms for $$b$$ b -Coloring and Fall Coloring are tight under the Exponential Time Hypothesis.

Abstract. We confirm a conjecture of Gartland and Lokshtanov [SODA 2023]: if for a hereditary graph class [Formula: see text] there exists a constant [Formula: see text] such that no member of [Formula: see text] contains a [Formula: see text]-creature as an induced subgraph or a [Formula: see text]-skinny-ladder as an induced minor, then there exists a polynomial [Formula: see text] such that every [Formula: see text] contains at most [Formula: see text] minimal separators. By a result of Fomin, Todinca, and Villanger [ SIAM J. Comput., 44 (2015), pp. 54–87] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from [Formula: see text]. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).

The b-Coloring problem, which given a graph G and an integer k asks whether G has a proper k-coloring such that each color class has a vertex adjacent to all color classes except its own, is known to be FPT parameterized by the vertex cover number and XP and 𝖶[1]-hard parameterized by clique-width. Its complexity when parameterized by the treewidth of the input graph remained an open problem. We settle this question by showing that b-Coloring is XNLP-complete when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexity of this problem, this implies that b-Coloring parameterized by pathwidth is 𝖶[t]-hard for all t, and resolves the parameterized complexity of b-Coloring parameterized by treewidth. We complement this result by showing that b-Coloring is FPT when parameterized by neighborhood diversity and by twin cover, two parameters that generalize vertex cover to more dense graphs, but are incomparable to pathwidth.

In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new and simpler proof of the NP-completeness of treewidth, and show that Treewidth remains NP-complete on subcubic induced subgraphs of the infinite 3-dimensional grid.

We show fixed-parameter tractability of the DIRECTED MULTICUT problem with three terminal pairs (with a randomized algorithm). In this problem we are given a directed graph G, three pairs of vertices (called terminals) (s1, t1), (s2, t2), (s3, t3), and an integer k and we want to find a set of at most k non-terminal vertices in G that intersect all s1t1-paths, all s2t2-paths, and all s3t3-paths. The parameterized complexity of this problem has been open since Chitnis, Hajiaghayi, and Marx proved fixed-parameter tractability of the two-terminal-pairs case at SODA 2012, and Pilipczuk and Wahlström proved the W[1]-hardness of the four-terminal-pairs case at SODA 2016. On the technical side, we use two recent developments in parameterized algorithms. Using the technique of directed flow-augmentation [Kim, Kratsch, Pilipczuk, Wahlström, STOC 2022] we cast the problem as a CSP problem with few variables and constraints over a large ordered domain. We observe that this problem can be in turn encoded as an FO model-checking task over a structure consisting of a few 0-1 matrices. We look at this problem through the lenses of twin-width, a recently introduced structural parameter [Bonnet, Kim, Thomassé, Watrigant, FOCS 2020]: By a recent characterization [Bonnet, Giocanti, Ossona de Mendez, Simon, Thomassé, Toruńczyk, STOC 2022] the said FO model-checking task can be done in FPT time if the said matrices have bounded grid rank. To complete the proof, we show an irrelevant vertex rule: If any of the matrices in the said encoding has a large grid minor, a vertex corresponding to the “middle” box in the grid minor can be proclaimed irrelevant — not contained in the sought solution — and thus reduced. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.07425. The research leading to the results presented in this paper was partially carried out during the Parameterized Algorithms Retreat of the University of Warsaw, PARUW 2022, held in Bedlewo in April 2022. This research is a part of projects that have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme Grant Agreement 714704 (TM, MP) and 648527 (MH), from the Alexander von Humboldt Foundation (MS), from the Research Council of Norway (LJ), and by the Federal Ministry of Education and Research (BMBF) and by a fellowship within the IFI programme of the German Academic Exchange Service (DAAD). (MH).

We study a generalization of the classic GLOBAL MIN-CUT problem, called GLOBAL LABEL MIN-CUT (or sometimes GLOBAL HEDGE MIN-CUT): the edges of the input (multi)graph are labeled (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost. While the st-cut version of the problem is known to be NP-hard, the above global cut version is known to admit a quasi-polynomial randomized nO(log OPT)-time algorithm due to Ghaffari, Karger, and Panigrahi [SODA 2017]. They consider this as “strong evidence that this problem is in P”. We show that this is actually not the case. We complete the study of the complexity of the Global Label Min-Cut problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time (np)o(log n/(log log n)2) would contradict the Randomized Exponential Time Hypothesis, where n is the number of vertices, and p is the number of labels in the input. The key step for the lower bound is a proof that Global Label Min-Cut is W[1]-hard when parameterized by the number of uncut labels. In other words, the problem is difficult in the regime where almost all labels need to be cut to disconnect the graph. To turn this lower bound into a quasi-polynomial-time lower bound, we also needed to revisit the framework due to Marx [Theory Comput. 2010] of proving lower bounds assuming Exponential Time Hypothesis through the SUBGRAPH ISOMORPHISM problem parameterized by the number of edges of the pattern. Here, we provide an alternative simplified proof of the hardness of this problem that is more versatile with respect to the choice of the regimes of the parameters. * This research is a part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme Grant Agreement 714704 (LJ, TM, MP, US) and from the Research Council of Norway (LJ).

Given a graph G on n vertices and two integers k and d, the Contraction(vc) problem asks whether one can contract at most k edges to reduce the vertex cover number of G by at least d. Recently, Lima et al. [JCSS 2021] proved that Contraction(vc) admits an XP algorithm running in time f(d)⋅nO(d). They asked whether this problem is FPT under this parameterization. In this article, we prove that: (i) Contraction(vc) is W[1]-hard parameterized by k+d. Moreover, unless the ETH fails, the problem does not admit an algorithm running in time f(k+d)⋅no(k+d) for any function f. This answers negatively the open question stated in Lima et al. [JCSS 2021]. (ii) Contraction(vc) is NP-hard even when k=d. (iii) Contraction(vc) can be solved in time 2O(d)⋅nk−d+O(1). This improves the algorithm of Lima et al. [JCSS 2021], and shows that when k=d, Contraction(vc) is FPT parameterized by d (or by k).

In this paper, we consider the problem of reducing the semitotal domination number of a given graph by contracting k edges, for some fixed k≥1. We show that this can always be done with at most 3 edge contractions and further characterise those graphs requiring 1, 2 or 3 edge contractions, respectively, to decrease their semitotal domination number. We then study the complexity of the problem for k=1 and obtain in particular a complete complexity dichotomy for monogenic classes.

We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 contains a k-creature as an induced subgraph or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every G ∈ 𝒢 contains at most p(|V(G)|) minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from 𝒢. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).

Given a graph and a colouring of its vertices, a rainbow vertex path is a path between two vertices such that all the internal nodes of the path are coloured distinctly. A graph is rainbow vertex-connected if between every pair of vertices in the graph there exists a rainbow vertex path. We study the problem of deciding whether a given graph can be coloured using k or less colours such that it is rainbow vertex-connected. Note that every graph G needs at least diam(G)-1 colours to be rainbow vertex connected. Heggernes et al. [MFCS, 2018] conjectured that if G is a graph in which every induced subgraph has a dominating diametral path, then G can always be rainbow vertex coloured with diam(G)-1 many colours. In this work, we confirm their conjecture for chordal, bipartite and claw-free diametral path graphs. We complement these results by showing the conjecture does not hold if the condition on every induced subgraph is dropped. In fact we show that, in this case, even though diam(G) many colours are always enough, it is NP-complete to determine whether a graph with a dominating diametral path of length three can be rainbow vertex coloured with two colours.

In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies W[t]-hardness for all t. It also indicates, via a conjecture by Pilipczuk and Wrochna [ToCT 2018], that any XP algorithm for such problems is likely to require XP space. In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are Independent Set, Dominating Set, Odd Cycle Transversal, (q-)Coloring, Max Cut, Maximum Regular Induced Subgraph, Feedback Vertex Set, Capacitated (Red-Blue) Dominating Set, and Bipartite Bandwidth.

International audience

Abstract A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether a given graph has a clique coloring with q colors. For fixed $$q \ge 2$$ q ≥ 2 , we give an $$\mathscr {O}^{\star }(q^{{\mathsf {tw}}})$$ O ⋆ ( q tw ) -time algorithm when the input graph is given together with one of its tree decompositions of width $${\mathsf {tw}} $$ tw . We complement this result with a matching lower bound under the Strong Exponential Time Hypothesis. We furthermore show that (when the number of colors is unbounded) Clique Coloring is $$\mathsf {XP}$$ XP parameterized by clique-width.

We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial-time results on graph classes, and answers open questions posed by Campos and Silva [Algorithmica, 2018] and Bonomo et al. [Graphs Combin., 2009]. This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is FPT when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the Fall Coloring problem within the same runtime bound. The running times of the clique-width based algorithms for b-Coloring and Fall Coloring are tight under the Exponential Time Hypothesis.

Given a vertex-colored graph, we say a path is a rainbow vertex path if all its internal vertices have distinct colors. The graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. In the Rainbow Vertex Coloring (RVC) problem we want to decide whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. This problem is known to be NP-complete even in very restricted scenarios, and very few efficient algorithms are known for it. In this work, we give polynomial-time algorithms for RVC on permutation graphs, powers of trees and split strongly chordal graphs. The algorithm for the latter class also works for the strong variant of the problem, where the rainbow vertex paths between each vertex pair must be shortest paths. We complement the polynomial-time solvability results for split strongly chordal graphs by showing that, for any fixed p≥3 both variants of the problem become NP-complete when restricted to split (S3,…,Sp)-free graphs, where Sq denotes the q-sun graph.

For a graph parameter π, the Contraction(π) problem consists in, given a graph G and two positive integers k,d, deciding whether one can contract at most k edges of G to obtain a graph in which π has dropped by at least d. Galby et al. [ISAAC 2019, MFCS 2019] recently studied the case where π is the size of a minimum dominating set. We focus on graph parameters defined as the minimum size of a vertex set that hits all the occurrences of graphs in a collection ℋ according to a fixed containment relation. We prove co-NP-hardness results under some assumptions on the graphs in ℋ, which in particular imply that Contraction(π) is co-NP-hard even for fixed k = d = 1 when π is the size of a minimum feedback vertex set or an odd cycle transversal. In sharp contrast, we show that when π is the size of a minimum vertex cover, the problem is in XP parameterized by d.

Motivated by the role of triadic closures in social networks, and the importance of finding a maximum subgraph avoiding a fixed pattern, we introduce and initiate the parameterized study of the StrongF-closure problem, where F is a fixed graph. This is a generalization of Strong Triadic Closure, whereas it is a relaxation of F-free Edge Deletion. In StrongF-closure, we want to select a maximum number of edges of the input graph G, and mark them as strong edges, in the following way: whenever a subset of the strong edges forms a subgraph isomorphic to F, then the corresponding induced subgraph of G is not isomorphic to F. Hence, the subgraph of G defined by the strong edges is not necessarily F-free, but whenever it contains a copy of F, there are additional edges in G to forbid that strong copy of F in G. We study StrongF-closure from a parameterized perspective with various natural parameterizations. Our main focus is on the number k of strong edges as the parameter. We show that the problem is FPT with this parameterization for every fixed graph F, whereas it does not admit a polynomial kernel even when $$F =P_3$$ F=P3. In fact, this latter case is equivalent to the Strong Triadic Closure problem, which motivates us to study this problem on input graphs belonging to well known graph classes. We show that Strong Triadic Closure does not admit a polynomial kernel even when the input graph is a split graph, whereas it admits a polynomial kernel when the input graph is planar, and even d-degenerate. Furthermore, on graphs of maximum degree at most 4, we show that Strong Triadic Closure is FPT with the above guarantee parameterization $$k - \mu (G)$$ k-μ(G), where $$\mu (G)$$ μ(G) is the maximum matching size of G. We conclude with some results on the parameterization of StrongF-closure by the number of edges of G that are not selected as strong.

The problem of the intersection of longest paths consists in determining the size of a smallest subset of vertices of a graph such that every longest path contains at least one vertex of the set. Given a graph G, we denote the size of this subset by lpt(G). In this work, we show a number of results that enable us to conclude that lpt(G)=1 if G is a chain graph, a P4-sparse graph, a starlike graph, a (P5,K1,3)-free graph, a graph that is the join of two other graphs or a graph whose blocks are split graphs, interval graphs or graphs with a universal vertex. We also provide upper bounds on lpt(G) for (P5,cricket)-free graphs and graphs that are intersection graphs of subtrees of a spider graph.

Problems related to finding induced subgraphs satisfying given properties form one of the most studied areas within graph algorithms. However, for many applications, it is desirable that the found subgraph has as few connections to the rest of the graph as possible, which gives rise to the Secluded Π- Subgraph problem. Here, input k is the size of the desired subgraph, and input t is a limit on the number of neighbors this subgraph has in the rest of the graph. This problem has been studied from a parameterized perspective, and unfortunately it turns out to be W[1]-hard for many graph properties Π, even when parameterized by k + t . We show that the situation changes when we are looking for a connected induced subgraph satisfying Π. In particular, we show that the Connected Secluded Π -Subgraph problem is FPT when parameterized by just t for many important graph properties Π.

A b-coloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph G has a b-coloring with k colors. The b-chromatic number of a graph G, denoted by χb(G), is the maximum number k such that G admits a b-coloring with k colors. We consider the complexity of the b-Coloring problem, whenever the value of k is close to one of two upper bounds on χb(G): The maximum degree Δ(G) plus one, and the m-degree, denoted by m(G), which is defined as the maximum number i such that G has i vertices of degree at least i−1. We obtain a dichotomy result for all fixed k∈N when k is close to one of the two above mentioned upper bounds. Concretely, we show that if k∈{Δ(G)+1−p,m(G)−p}, the problem is polynomial-time solvable whenever p∈{0,1} and, even when k=3, it is NP-complete whenever p≥2. We furthermore consider parameterizations of the b-Coloring problem that involve the maximum degree Δ(G) of the input graph G and give two FPT-algorithms. First, we show that deciding whether a graph G has a b-coloring with m(G) colors is FPT parameterized by Δ(G). Second, we show that b-Coloring is FPT parameterized by Δ(G)+ℓk(G), where ℓk(G) denotes the number of vertices of degree at least k.

In this paper, we consider the following problem: given a connected graph G, can we reduce the domination number of G by one by using only one edge contraction? We show that the problem is NP-hard when restricted to {P_6,P_4+P_2}-free graphs and that it is coNP-hard when restricted to subcubic claw-free graphs and 2P_3-free graphs. As a consequence, we are able to establish a complexity dichotomy for the problem on H-free graphs when H is connected.

In this paper, we study the following problem: given a connected graph $G$, can we reduce the domination number of $G$ by at least one using $k$ edge contractions, for some fixed integer $k \geq 0$? We present positive and negative results regarding the computational complexity of this problem.

Given a graph with colors on its vertices, a path is called a rainbow vertex path if all its internal vertices have distinct colors. We say that the graph is rainbow vertex-connected if there is a rainbow vertex path between every pair of its vertices. We study the problem of deciding whether the vertices of a given graph can be colored with at most k colors so that the graph becomes rainbow vertex-connected. Although edge-colorings have been studied extensively under similar constraints, there are significantly fewer results on the vertex variant that we consider. In particular, its complexity on structured graph classes was explicitly posed as an open question. We show that the problem remains NP-complete even on bipartite apex graphs and on split graphs. The former can be seen as a first step in the direction of studying the complexity of rainbow coloring on sparse graphs, an open problem which has attracted attention but limited progress. We also give hardness of approximation results for both bipartite and split graphs. To complement the negative results, we show that bipartite permutation graphs, interval graphs, and block graphs can be rainbow vertex-connected optimally in polynomial time.