Search

In this paper, we study the Harmless Set problem from a parameterized complexity perspective. Given a graph G = (V , E) , a threshold function t : V → N and an integer k, we study Harmless Set, where the goal is to find a subset of vertices S ⊆ V of size at least k such that every vertex v ∈ V has fewer than t(v) neighbours in S. On the positive side, we obtain fixed-parameter algorithms for the problem when parameterized by the neighbourhood diversity, the twin-cover number and the vertex integrity of the input graph. We complement two of these results from the negative side. On dense graphs, we show that the problem is W[1]-hard parameterized by cluster vertex deletion number—a natural generalization of the twin-cover number. We show that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, and treedepth—a natural generalization of the vertex integrity. We thereby resolve one open question stated by Bazgan and Chopin (Discrete Optim 14(C):170–182, 2014) concerning the complexity of Harmless Set parameterized by the treewidth of the input graph. We also show that Harmless Set for a special case where each vertex has the threshold set to half of its degree (the so-called Majority Harmless Set problem) is W[1]-hard when parameterized by the treewidth of the input graph. Given a graph G and an irredundant c-expression of G, we prove that Harmless Set can be solved in XP-time when parameterized by clique-width. [ABSTRACT FROM AUTHOR]

Given an n-vertex m-edge graph G of clique-width at most k, and a corresponding k-expression, we present algorithms for computing some well-known centrality indices (eccentricity and closeness) that run in O (2 O (k) (n + m) 1 + ϵ) time for any ϵ > 0 . Doing so, we can solve various distance problems within the same amount of time, including: the diameter, the center, the Wiener index and the median set. Our run-times match conditional lower bounds of Coudert et al. (SODA'18) under the Strong Exponential-Time Hypothesis. On our way, we get a distance-labeling scheme for n-vertex m-edge graphs of clique-width at most k, using O (k log 2 n) bits per vertex and constructible in O ~ (k (n + m)) time from a given k-expression. Doing so, we match the label size obtained by Courcelle and Vanicat (DAM 2016), while we considerably improve the dependency on k in their scheme. As a corollary, we get an O ~ (k n 2) -time algorithm for computing All-Pairs Shortest-Paths on n-vertex graphs of clique-width at most k, being given a k-expression. This partially answers an open question of Kratsch and Nelles (STACS'20). Our algorithms work for graphs with non-negative vertex-weights, under two different types of distances studied in the literature. For that, we introduce a new type of orthogonal range query as a side contribution of this work, that might be of independent interest. [ABSTRACT FROM AUTHOR]

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 ≥ 2 , we give an O ⋆ (q tw) -time algorithm when the input graph is given together with one of its tree decompositions of width 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 XP parameterized by clique-width. [ABSTRACT FROM AUTHOR]

The cut-set ∂ (S) of a graph G = (V , E) is the set of edges that have one endpoint in S ⊂ V and the other endpoint in V \ S , and whenever G[S] is connected, the cut [ S , V \ S ] of G is called a connected cut. A bond of a graph G is an inclusion-wise minimal disconnecting set of G, i.e., bonds are cut-sets that determine cuts [ S , V \ S ] of G such that G[S] and G [ V \ S ] are both connected. Contrasting with a large number of studies related to maximum cuts, there exist very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond, and the maximum connected cut of a graph. Although cuts and bonds are similar, we remark that computing the largest bond and the maximum connected cut of a graph tends to be harder than computing its maximum cut. We show that it does not exist a constant-factor approximation algorithm to compute the largest bond, unless P = NP . Also, we show that Largest Bond and Maximum Connected Cut are NP-hard even for planar bipartite graphs, whereas Maximum Cut is trivial on bipartite graphs and polynomial-time solvable on planar graphs. In addition, we show that Largest Bond and Maximum Connected Cut are NP-hard on split graphs, and restricted to graphs of clique-width w they can not be solved in time f (w) n o (w) unless the Exponential Time Hypothesis fails, but they can be solved in time f (w) n O (w) . Finally, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, the treewidth, and the twin-cover number. [ABSTRACT FROM AUTHOR]

We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs H 1 and H 2 for all but six pairs (H 1 , H 2) . Schweitzer had previously shown that the number of open cases was finite, but without specifying the open cases. Grohe and Schweitzer proved that Graph Isomorphism is polynomial-time solvable on graph classes of bounded clique-width. Our work combines known results such as these with new results. By exploiting a relationship between Graph Isomorphism and clique-width, we simultaneously reduce the number of open cases for boundedness of clique-width for (H 1 , H 2) -free graphs to five. [ABSTRACT FROM AUTHOR]

In this paper, we prove that, given a clique-width k-expression of an n-vertex graph, Hamiltonian Cycle can be solved in time n O (k) . This improves the naive algorithm that runs in time n O (k 2) by Espelage et al. (Graph-theoretic concepts in computer science, vol 2204. Springer, Berlin, 2001), and it also matches with the lower bound result by Fomin et al. that, unless the Exponential Time Hypothesis fails, there is no algorithm running in time n o (k) (Fomin et al. in SIAM J Comput 43:1541–1563, 2014). We present a technique of representative sets using two-edge colored multigraphs on k vertices. The essential idea is that, for a two-edge colored multigraph, the existence of an Eulerian trail that uses edges with different colors alternately can be determined by two information: the number of colored edges incident with each vertex, and the connectedness of the multigraph. With this idea, we avoid the bottleneck of the naive algorithm, which stores all the possible multigraphs on k vertices with at most n edges. [ABSTRACT FROM AUTHOR]

The notion of clique-width for graphs offers many research topics and has received considerable attention in the past decade. A graph has clique-width k if it can be represented as an algebraic expression on k labels associated with its vertices. Many computationally hard problems can be solved in polynomial time for graphs of bounded clique-width. Interestingly also, many graph families have bounded clique-width. In this paper, we consider the problem of preprocessing a graph of size n and clique-width k to build space-efficient data structures that support basic graph navigation queries. First, by way of a counting argument, which is of interest in its own right, we prove the space requirement of any representation is Ω(kn). Then we present a navigation oracle which answers adjacency query in constant time and neighborhood queries in constant time per neighbor. This oracle uses O(kn) space (i.e., O(kn) bits). We also present a degree query which reports the degree of each given vertex in O(klog∗(n)) time using O(knlog∗(n)) bits. [ABSTRACT FROM AUTHOR]

Given two graphs G and H, we say that G contains H as an induced minor if a graph isomorphic to H can be obtained from G by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph H that Graph Isomorphism is polynomial-time solvable on H-induced-minor-free graphs or that it is GI-complete. Additionally, we classify those graphs H for which H-induced-minor-free graphs have bounded clique-width. These two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor, or subgraph. [ABSTRACT FROM AUTHOR]

For a set S of intervals, the clique-interva I S is defined as the interval obtained from the intersection of all the intervals in S , and the clique-width quantity w S is defined as the length of I S . Given a set S of intervals, it is straightforward to compute its clique-interval and clique-width. In this paper we study the problem of partitioning a set of intervals in order to maximize the sum of the clique-widths of the partitions. We present an O(n log n) time algorithm for the balanced bipartitioning problem, and an O(k n 2 ) time algorithm for the k -way unbalanced partitioning problem. [ABSTRACT FROM AUTHOR]