Search

A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f (u) and f (v) of H whenever there is an edge between vertices u and v of G. The H-Colouring problem is to decide if a graph G allows a homomorphism to a fixed graph H. We continue a study on a variant of this problem, namely the SurjectiveH-Colouring problem, which imposes the homomorphism to be vertex-surjective. We build upon previous results and show that this problem is NP -complete for every connected graph H that has exactly two vertices with a self-loop as long as these two vertices are not adjacent. As a result, we can classify the computational complexity of SurjectiveH-Colouring for every graph H on at most four vertices. [ABSTRACT FROM AUTHOR]

The Secluded Path problem models a situation where sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of a selected path is its exposure cost, which is the total cost of vertices in its closed neighborhood. The task is to select a secluded path, i.e., a path with a small exposure cost. Similarly, the Secluded Steiner Tree problem is to find a tree in a graph connecting a given set of terminals such that the exposure cost of the tree is minimized. In this paper we present a systematic study of the parameterized complexity of Secluded Steiner Tree. In particular, we establish the tractability of Secluded Path being parameterized by 'above guarantee' value, which in this case is the length of a shortest path between vertices. We also show how to extend this result for Secluded Steiner Tree, in this case we parameterize above the size of an optimal Steiner tree and the number of terminals. We also consider various parameterization of the problems such as by the treewidth, the size of a vertex cover, feedback vertex set, or the maximum vertex degree and establish kernelization complexity of the problem subject to different choices of parameters. [ABSTRACT FROM AUTHOR]

For a positive integer k, a k- coloring of a graph [ABSTRACT FROM AUTHOR]

For a fixed graph H , the H - Minor Edit problem takes as input a graph G and an integer k and asks whether G can be modified into H by a total of at most k edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex dissolutions yields the H - Topological Minor Edit problem. For each problem we show polynomial-time solvable and NP -complete cases depending on the choice of H . Moreover, when G is AT-free, chordal or planar, we show that H - Minor Edit is polynomial-time solvable for all graphs H . [ABSTRACT FROM AUTHOR]

The cyclability of a graph is the maximum integer k for which every k vertices lie on a cycle. The algorithmic version of the problem, given a graph G and a nonnegative integer k, decide whether the cyclability of G is at least k, is NP-hard. We study the parametrized complexity of this problem. We prove that this problem, parameterized by k, is co-W[1]-hard and that it does not admit a polynomial kernel on planar graphs, unless NP ⊆ co-NP=poly. On the positive side, we give an FPT algorithm for planar graphs that runs in time 22O(k2 log k). n2. Our algorithm is based on a series of graph-theoretical results on cyclic linkages in planar graphs. [ABSTRACT FROM AUTHOR]

A multicast game is a network design game modelling how selfish non-cooperative agents build and maintain one-to-many network communication. There is a special source node and a collection of agents located at corresponding terminals. Each agent is interested in selecting a route from the special source to its terminal minimizing the cost. The mutual influence of the agents is determined by a cost sharing mechanism, which evenly splits the cost of an edge among all the agents using it for routing. In this paper we provide several algorithmic and complexity results on finding a Nash equilibrium minimizing the value of Rosenthal potential. Let n be the number of agents and G be the communication network. We show that for a given strategy profile s and integer k ≥ 0, there is a local search algorithm which in time n⋅| G| finds a better strategy profile, if there is any, in a k-exchange neighbourhood of s. In other words, the algorithm decides if Rosenthal potential can be decreased by changing strategies of at most k agents. The running time of our local search algorithm is essentially tight: unless F P T = W[1], for any function f( k), searching of the k-neighbourhood cannot be done in time f( k)⋅| G|. We also show that an equilibrium with minimum potential can be found in 3⋅| G| time. [ABSTRACT FROM AUTHOR]

Vertex elimination is a graph operation that turns the neighborhood of a vertex into a clique and removes the vertex itself. It has widely known applications within sparse matrix computations. We define the Elimination problem as follows: given two graphs G and H, decide whether H can be obtained from G by | V( G)|−| V( H)| vertex eliminations. We show that Elimination is $\mathsf {W[1]} $-hard when parameterized by | V( H)|, even if both input graphs are split graphs, and $\mathsf {W[2]} $-hard when parameterized by | V( G)|−| V( H)|, even if H is a complete graph. On the positive side, we show that Elimination admits a kernel with at most 5| V( H)| vertices in the case when G is connected and H is a complete graph, which is in sharp contrast to the $\mathsf {W[1]} $-hardness of the related Clique problem. We also study the case when either G or H is tree. The computational complexity of the problem depends on which graph is assumed to be a tree: we show that Elimination can be solved in polynomial time when H is a tree, whereas it remains NP-complete when G is a tree. [ABSTRACT FROM AUTHOR]

The Coloring problem is to test whether a given graph can be colored with at most k colors for some given k , such that no two adjacent vertices receive the same color. The complexity of this problem on graphs that do not contain some graph H as an induced subgraph is known for each fixed graph H . A natural variant is to forbid a graph H only as a subgraph. We call such graphs strongly H -free and initiate a complexity classification of Coloring for strongly H -free graphs. We show that Coloring is NP -complete for strongly H -free graphs, even for k = 3 , when H contains a cycle, has maximum degree at least 5, or contains a connected component with two vertices of degree 4. We also give three conditions on a forest H of maximum degree at most 4 and with at most one vertex of degree 4 in each of its connected components, such that Coloring is NP -complete for strongly H -free graphs even for k = 3 . Finally, we classify the computational complexity of Coloring on strongly H -free graphs for all fixed graphs H up to seven vertices. In particular, we show that Coloring is polynomial-time solvable when H is a forest that has at most seven vertices and maximum degree at most 4. [ABSTRACT FROM AUTHOR]

For any graph class $$\mathcal{H}$$ , the $$\mathcal{H}$$ - Contraction problem takes as input a graph $$G$$ and an integer $$k$$ , and asks whether there exists a graph $$H\in \mathcal{H}$$ such that $$G$$ can be modified into $$H$$ using at most $$k$$ edge contractions. We study the parameterized complexity of $$\mathcal{H}$$ - Contraction for three different classes $$\mathcal{H}$$ : the class $$\mathcal{H}_{\le d}$$ of graphs with maximum degree at most $$d$$ , the class $$\mathcal{H}_{=d}$$ of $$d$$ -regular graphs, and the class of $$d$$ -degenerate graphs. We completely classify the parameterized complexity of all three problems with respect to the parameters $$k$$ , $$d$$ , and $$d+k$$ . Moreover, we show that $$\mathcal{H}$$ - Contraction admits an $$O(k)$$ vertex kernel on connected graphs when $$\mathcal{H}\in \{\mathcal{H}_{\le 2},\mathcal{H}_{=2}\}$$ , while the problem is $$\mathsf{W}[2]$$ -hard when $$\mathcal{H}$$ is the class of $$2$$ -degenerate graphs and hence is expected not to admit a kernel at all. In particular, our results imply that $$\mathcal{H}$$ - Contraction admits a linear vertex kernel when $$\mathcal{H}$$ is the class of cycles. [ABSTRACT FROM AUTHOR]

The Contractibility problem takes as input two graphs G and H, and the task is to decide whether H can be obtained from G by a sequence of edge contractions. The Induced Minor and Induced Topological Minor problems are similar, but the first allows both edge contractions and vertex deletions, whereas the latter allows only vertex deletions and vertex dissolutions. All three problems are NP-complete, even for certain fixed graphs H. We show that these problems can be solved in polynomial time for every fixed H when the input graph G is chordal. Our results can be considered tight, since these problems are known to be W[ 1]-hard on chordal graphs when parameterized by the size of H. To solve Contractibility and Induced Minor, we define and use a generalization of the classic Disjoint Paths problem, where we require the vertices of each of the k paths to be chosen from a specified set. We prove that this variant is NP-complete even when k=2, but that it is polynomial-time solvable on chordal graphs for every fixed k. Our algorithm for Induced Topological Minor is based on another generalization of Disjoint Paths called Induced Disjoint Paths, where the vertices from different paths may no longer be adjacent. We show that this problem, which is known to be NP-complete when k=2, can be solved in polynomial time on chordal graphs even when k is part of the input. Our results fit into the general framework of graph containment problems, where the aim is to decide whether a graph can be modified into another graph by a sequence of specified graph operations. Allowing combinations of the four well-known operations edge deletion, edge contraction, vertex deletion, and vertex dissolution results in the following ten containment relations: (induced) minor, (induced) topological minor, (induced) subgraph, (induced) spanning subgraph, dissolution, and contraction. Our results, combined with existing results, settle the complexity of each of the ten corresponding containment problems on chordal graphs. [ABSTRACT FROM AUTHOR]

Abstract: A list assignment of a graph is a function that assigns a list of so-called admissible colors to each . The List Coloring problem is that of testing whether a given graph has a coloring that respects a given list assignment , i.e., whether has a mapping such that (i) whenever and (ii) for all . If a graph has no induced subgraph isomorphic to some graph of a pair , then is called -free. We completely characterize the complexity of List Coloring for -free graphs. [Copyright &y& Elsevier]

Abstract: A colouring of a graph is a mapping such that if ; if then c is a k-colouring. The Colouring problem is that of testing whether a given graph has a k-colouring for some given integer k. If a graph contains no induced subgraph isomorphic to any graph in some family , then it is called -free. The complexity of Colouring for -free graphs with has been completely classified. When , the classification is still wide open, although many partial results are known. We continue this line of research and forbid induced subgraphs , where we allow to have a single edge and to have a single non-edge. Instead of showing only polynomial-time solvability, we prove that Colouring on such graphs is fixed-parameter tractable when parameterized by . As a by-product, we obtain the same result both for the problem of determining a maximum independent set and for the problem of determining a maximum clique. [Copyright &y& Elsevier]

Abstract: In 2011, Cai an Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs: for a given graph G and integer k, the task is to decide if G contains a (connected) subgraph with k vertices (edges) with all vertices of even (odd) degrees. They succeed to establish the parameterized complexity of all cases except two, when we ask about: [•] a connected k-edge subgraph with all vertices of odd degrees, the problem known as k-Edge Connected Odd Subgraph; and [•] a connected k-vertex induced subgraph with all vertices of even degrees, the problem known as k-Vertex Eulerian Subgraph. We show that k-Edge Connected Odd Subgraph is FPT and k-Vertex Eulerian Subgraph is -hard. Our FPT algorithm is based on a novel combinatorial result on the treewidth of minimal connected odd graphs with even amount of edges. [Copyright &y& Elsevier]

Abstract: We give tight algorithmic lower and upper bounds for some double-parameterized subgraph problems when the clique-width of the input graph is one of the parameters. Let be an arbitrary input graph on vertices with clique-width at most . We prove the following results. [•] The Dense (Sparse) -Subgraph problem, which asks whether there exists an induced subgraph of with vertices and at least edges (at most edges, respectively), can be solved in time , but it cannot be solved in time unless the Exponential Time Hypothesis (ETH) fails. [•] The -Regular Induced Subgraph problem, which asks whether there exists a -regular induced subgraph of , and the Minimum Subgraph of Minimum Degree at least problem, which asks whether there exists a subgraph of with vertices and minimum degree at least , can be solved in time , but they cannot be solved in time unless ETH fails. [Copyright &y& Elsevier]

Abstract: The Degree Contractibility problem is to test whether a given graph can be modified to a graph of minimum degree at least by using at most contractions. We prove the following three results. First, Degree Contractibility is NP-complete even when . Second, it is fixed-parameter tractable when parameterized by and . Third, it is -hard when parameterized by . We also study its variant where the input graph is weighted, i.e., has some edge weighting and the contractions preserve these weights. The Weighted Degree Contractibility problem is to test if a weighted graph can be contracted to a weighted graph of minimum weighted degree at least by using at most weighted contractions. We show that this problem is NP-complete and that it is fixed-parameter tractable when parameterized by . In addition, we pinpoint a relationship with the problem of finding a minimal edge-cut of maximum size in a graph and study the parameterized complexity of this problem and its variants. [Copyright &y& Elsevier]

Abstract: A homomorphism from a graph to a graph is a vertex mapping such that and form an edge in whenever and form an edge in . The -Coloring problem is that of testing whether a graph allows a homomorphism to a given graph . A well-known result of Hell and Nešetřil determines the computational complexity of this problem for any fixed graph . We study a natural variant of this problem, namely the Surjective -Coloring problem, which is that of testing whether a graph allows a homomorphism to a graph that is (vertex-)surjective. We classify the computational complexity of this problem for when is any fixed partially reflexive tree. Thus we identify the first class of target graphs for which the computational complexity of Surjective -Coloring can be determined. For the polynomial-time solvable cases we show a number of parameterized complexity results, including in particular ones on graph classes with (locally) bounded expansion. [Copyright &y& Elsevier]

The S urjective H omomorphism problem is to test whether a given graph G called the guest graph allows a vertex-surjective homomorphism to some other given graph H called the host graph. The bijective and injective homomorphism problems can be formulated in terms of spanning subgraphs and subgraphs, and as such their computational complexity has been extensively studied. What about the surjective variant? Because this problem is NP-complete in general, we restrict the guest and the host graph to belong to graph classes $${{\mathcal G}}$$ and $${{\mathcal H}}$$, respectively. We determine to what extent a certain choice of $${{\mathcal G}}$$ and $${{\mathcal H}}$$ influences its computational complexity. We observe that the problem is polynomial-time solvable if $${{\mathcal H}}$$ is the class of paths, whereas it is NP-complete if $${{\mathcal G}}$$ is the class of paths. Moreover, we show that the problem is even NP-complete on many other elementary graph classes, namely linear forests, unions of complete graphs, cographs, proper interval graphs, split graphs and trees of pathwidth at most 2. In contrast, we prove that the problem is fixed-parameter tractable in k if $${{\mathcal G}}$$ is the class of trees and $${{\mathcal H}}$$ is the class of trees with at most k leaves, or if $${{\mathcal G}}$$ and $${{\mathcal H}}$$ are equal to the class of graphs with vertex cover number at most k. [ABSTRACT FROM AUTHOR]

Cops and robber is a classical pursuit-evasion game on undirected graphs, where the task is to identify the minimum number of cops sufficient to catch the robber. In this paper, we investigate the changes in problem's complexity and combinatorial properties with constraining the following natural game parameters: fuel, the number of steps each cop can make; cost, the total sum of steps along edges all cops can make; and time, the number of rounds of the game. [ABSTRACT FROM AUTHOR]

Abstract: Given two sets of non-negative integers, a set of vertices of a graph is -dominating if for every vertex , and for every . This concept, introduced by Telle in 1990’s, generalizes and unifies several variants of graph domination studied separately before. We study the parameterized complexity of -domination in this general setting. Among other results, we show that the existence of a -dominating set of size (and at most ) are W[1]-complete problems (when parameterized by ) for any pair of finite sets and . We further present results on dual parameterization by , and results on certain infinite sets (in particular for being the sets of even and odd integers). [Copyright &y& Elsevier]

Abstract: We give a linear-time algorithm for computing the edge search number of cographs, thereby resolving the computational complexity of edge searching on this graph class. To achieve this we give a characterization of the edge search number of the join of two graphs. With our result, the knowledge on graph searching of cographs is now complete: node, mixed, and edge search numbers of cographs can all be computed efficiently. Furthermore, we are one step closer to computing the edge search number of permutation graphs. [Copyright &y& Elsevier]

Abstract: A graph is -free if it does not contain an induced subgraph isomorphic to the graph . The graph denotes a path on vertices. The -Coloring problem is the problem to decide whether a graph can be colored with at most colors such that adjacent vertices receive different colors. We show that 4-Coloring is NP-complete for -free graphs. This improves a result of Le, Randerath, and Schiermeyer, who showed that 4-Coloring is NP-complete for -free graphs, and a result of Woeginger and Sgall, who showed that 5-Coloring is NP-complete for -free graphs. Additionally, we prove that the precoloring extension version of -Coloring is NP-complete for -free graphs, but that the precoloring extension version of -Coloring can be solved in polynomial time for -free graphs, a subclass of -free graphs. Here denotes the disjoint union of a and a . We denote the disjoint union of copies of a by and involve Ramsey numbers to prove that the precoloring extension version of -Coloring can be solved in polynomial time for -free graphs for any fixed . Combining our last two results with known results yields a complete complexity classification of (precoloring extension of) 3-Coloring for -free graphs when is a fixed graph on at most 6 vertices: the problem is polynomial-time solvable if is a linear forest; otherwise it is NP-complete. [Copyright &y& Elsevier]

Abstract: We compare the fixed parameter complexity of various variants of coloring problems (including List Coloring, Precoloring Extension, Equitable Coloring, -Labeling and Channel Assignment) when parameterized by treewidth and by vertex cover number. In most (but not all) cases we conclude that parametrization by the vertex cover number provides a significant drop in the complexity of the problems. [Copyright &y& Elsevier]

Abstract: We study the parameterized complexity of two families of problems: the bounded length disjoint paths problem and the bounded length cut problem. From Menger’s theorem both problems are equivalent (and computationally easy) in the unbounded case for single source, single target paths. However, in the bounded case, they are combinatorially distinct and are both NP-hard, even to approximate. Our results indicate that a more refined landscape appears when we study these problems with respect to their parameterized complexity. For this, we consider several parameterizations (with respect to the maximum length of paths, the number of paths or the size of a cut, and the treewidth of the input graph) of all variants of both problems (edge/vertex-disjoint paths or cuts, directed/undirected). We provide FPT-algorithms (for all variants) when parameterized by both and and hardness results when the parameter is only one of and . Our results indicate that the bounded length disjoint-path variants are structurally harder than their bounded length cut counterparts. Also, it appears that the edge variants are harder than their vertex-disjoint counterparts when parameterized by the treewidth of the input graph. [Copyright &y& Elsevier]

Abstract: Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the -th class have pairwise distance greater than . The main result of this paper is a solution of an open problem of Goddard et al. showing that the decision whether a tree allows a packing coloring with at most classes is NP-complete. We further discuss specific cases when this problem allows an efficient algorithm. Namely, we show that it is decideable in polynomial time for graphs of bounded treewidth and diameter, and fixed parameter tractable for chordal graphs. We accompany these results by several observations on a closely related variant of the packing coloring problem, where the lower bounds on the distances between vertices inside color classes are determined by an infinite nondecreasing sequence of bounded integers. [Copyright &y& Elsevier]

Abstract: The Cops and Robbers game as originally defined independently by Quilliot and by Nowakowski and Winkler in the 1980s has been much studied, but very few results pertain to the algorithmic and complexity aspects of it. In this paper we prove that computing the minimum number of cops that are guaranteed to catch a robber on a given graph is NP-hard and that the parameterized version of the problem is W[2]-hard; the proof extends to the case where the robber moves time faster than the cops. We show that on split graphs, the problem is polynomially solvable if but is NP-hard if . We further prove that on graphs of bounded cliquewidth the problem is polynomially solvable for . Finally, we show that for planar graphs the minimum number of cops is unbounded if the robber is faster than the cops. [Copyright &y& Elsevier]

We show that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are W[1]-hard parameterized by clique-width. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, that is, solvable in time g(k) ∙ nO(1) on n-vertex graphs of clique-width k, where g is some function of k only. Our results imply that the running time O(nf(k)) of many clique-widthbased algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely FPT ≠ W[1]). [ABSTRACT FROM AUTHOR]

We show that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are W[1]-hard parameterized by clique-width. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, that is, solvable in time g(k) · nO(1) on η-vertex graphs of clique-width k, where g is some function of k only. Our results imply that the running time O(nf(k)) of many clique-widthbased algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely FPT ≠ W[1]). [ABSTRACT FROM AUTHOR]

k -means and k -median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependencies on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian, and Frost proposed an elegant model of explainable k -means and k -median clustering in ICML 2020. In this model, a decision tree with k leaves provides a straightforward characterization of the data set into clusters. We study two natural algorithmic questions about explainable clustering. (1) For a given clustering, how to find the "best explanation" by using a decision tree with k leaves? (2) For a given set of points, how to find a decision tree with k leaves minimizing the k -means/median objective of the resulting explainable clustering? To address the first question, we introduce a new model of explainable clustering. Our model, inspired by the notion of outliers in robust statistics, is the following. We are seeking a small number of points (outliers) whose removal makes the existing clustering well-explainable. For addressing the second question, we initiate the study of the model of Moshkovitz et al. from the perspective of multivariate complexity. Our rigorous algorithmic analysis sheds some light on the influence of parameters like the input size, dimension of the data, the number of outliers, the number of clusters, and the approximation ratio, on the computational complexity of explainable clustering. [ABSTRACT FROM AUTHOR]

We consider the Directed Anchored k -Core problem, where the task is for a given directed graph G and integers b , k and p , to find an induced subgraph H with at least p vertices (the core) such that all but at most b vertices (the anchors) of H have in-degree at least k . We undertake a systematic analysis of the computational complexity of the Directed Anchored k -Core problem. [ABSTRACT FROM AUTHOR]

Abstract: We prove three complexity results on vertex coloring problems restricted to -free graphs, i.e., graphs that do not contain a path on vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring remains NP-complete when restricted to -free graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on -free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for -free graphs. This implies a simpler algorithm for checking the 3-colorability of -free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for -free graphs. This problem was known to be polynomially solvable for -free graphs and NP-complete for -free graphs, so there remains one open case. [Copyright &y& Elsevier]

Abstract: A t-spanner of a graph G is a spanning subgraph S in which the distance between every pair of vertices is at most t times their distance in G. If S is required to be a tree then S is called a tree t-spanner of G. In 1998, Fekete and Kremer showed that on unweighted planar graphs deciding whether G admits a tree t-spanner is polynomial time solvable for and is NP-complete when t is part of the input. They also left as an open problem if the problem is polynomial time solvable for every fixed . In this work we resolve the open question of Fekete and Kremer by proving much more general results: [•] The problem of finding a t-spanner of treewidth at most k in a given planar graph G is fixed parameter tractable parameterized by k and t. Moreover, for every fixed t and k, the running time of our algorithm is linear. [•] Our technique allows to extend the result from planar graphs to much more general classes of graphs. An apex graph is a graph that can be made planar by the removal of a single vertex. We prove that the problem of finding a t-spanner of treewidth k is fixed parameter tractable on graphs that do not contain some fixed apex graph as a minor, i.e. on apex-minor-free graphs. The class of apex-minor-free graphs contains planar graphs and graphs of bounded genus. [•] Finally, we show that the tractability border of the t-spanner problem cannot be extended beyond the class of apex-minor-free graphs and in this sense our results are tight. In particular, for every , the problem of finding a tree t-spanner is NP-complete on -minor-free graphs. [Copyright &y& Elsevier]

Abstract: A -spanner of a graph is its spanning subgraph such that the distance between every pair of vertices in is at most times their distance in . The sparsest -spanner problem asks to find, for a given graph and an integer , a -spanner of with the minimum number of edges. The problem is known to be NP-hard for all , and, even more, it is NP-hard to approximate it with ratio for every . For , the problem remains NP-hard for planar graphs and the approximability status of the problem on planar graphs was open. We resolve this open issue by showing that the sparsest -spanner problem admits the efficient polynomial time approximation scheme (EPTAS) for every . Our result holds for a much wider class of graphs, namely, the class of apex-minor-free graphs, which contains the classes of planar and bounded genus graphs. Moreover, it is possible to extend our results to weighted apex-minor free graphs, when the maximum edge weight is bounded by some constant. [ABSTRACT FROM AUTHOR]