•For each integer r≥0, s≥0 and t≥1, the class of (Kr,K1,s1,Pt)-free graphs has bounded mim-width.•Given a (Kr,K1,s1,Pt)-free graph, a branch decomposition of bounded mim-width can be computed in ...polynomial time.•Listk-colouring is polynomial-time solvable for (K1,s1,Pt)-free graphs for each s≥1 and t≥1.
A colouring of a graph G=(V,E) is a mapping c:V→{1,2,…} such that c(u)≠c(v) for every two adjacent vertices u and v of G. The Listk-Colouring problem is to decide whether a graph G=(V,E) with a list L(u)⊆{1,…,k} for each u∈V has a colouring c such that c(u)∈L(u) for every u∈V. Let Pt be the path on t vertices and let K1,s1 be the graph obtained from the (s+1)-vertex star K1,s by subdividing each of its edges exactly once.
Recently, Chudnovsky, Spirkl and Zhong (Discrete Math. 2020) proved that List 3-Colouring is polynomial-time solvable for (K1,s1,Pt)-free graphs for every t≥1 and s≥1. We generalize their result to Listk-Colouring for every k≥1. Our result also generalizes the known result that for every k≥1 and s≥0, Listk-Colouring is polynomial-time solvable for (sP1+P5)-free graphs, which was proven for s=0 by Hoàng, Kamiński, Lozin, Sawada and Shu (Algorithmica 2010) and for every s≥1 by Couturier, Golovach, Kratsch and Paulusma (Algorithmica 2015).
We show our result by proving boundedness of an underlying width parameter. Namely, we show that for every k≥1, s≥1, t≥1, the class of (Kk,K1,s1,Pt)-free graphs has bounded mim-width and that a corresponding branch decomposition is “quickly computable” for these graphs.
Logical labeling schemes Chandoo, Maurice
Discrete mathematics,
October 2023, 2023-10-00, Volume:
346, Issue:
10
Journal Article
Peer reviewed
Open access
A labeling scheme is a space-efficient data structure for encoding graphs from a particular graph class. The idea is to assign each vertex of a graph a short label s.t. adjacency of two vertices can ...be algorithmically determined from their labels. For instance, planar and interval graphs have labeling schemes. The algorithm used to determine adjacency—called label decoding algorithm—should be of low complexity since the time it takes to execute corresponds to the time to query an edge in that representation.
What graph classes have a labeling scheme if the label decoding algorithm must be very efficient, e.g. computable in constant time? In order to investigate this question we introduce logical labeling schemes where the label decoding algorithm is expressed as a first-order formula and consider their properties such as the relation to labeling schemes defined in terms of classical complexity classes. Additionally, we introduce a notion of reduction between graph classes in terms of boolean formulas and show completeness results.
We determine the number of labelled chordal planar graphs with n vertices, which is asymptotically g⋅n−5/2γnn! for a constant g>0 and γ≈11.89235. We also determine the number of rooted simple chordal ...planar maps with n edges, which is asymptotically s⋅n−3/2δn, where s>0, δ=1/σ≈6.40375, and σ is an algebraic number of degree 12. The proofs are based on combinatorial decompositions and singularity analysis. Chordal planar graphs (or maps) are a natural example of a subcritical class of graphs in which the class of 3-connected graphs is relatively rich. The 3-connected members are precisely chordal triangulations, those obtained starting from K4 by repeatedly adding vertices adjacent to an existing triangular face.
We consider the classical problems (Edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We show ...a dichotomy for the former problem restricted to (H1,H2)-free graphs and a dichotomy for the latter problem restricted to H-free graphs. We find that there exists an infinite family of graphs H such that Vertex Steiner Tree is polynomial-time solvable for H-free graphs, whereas there exist only two graphs H for which this holds for Edge Steiner Tree (assuming P≠NP). We also find that Edge Steiner Tree is polynomial-time solvable for (H1,H2)-free graphs if and only if the treewidth of the class of (H1,H2)-free graphs is bounded (subject to P≠NP). To obtain the latter result, we determine all pairs (H1,H2) for which the class of (H1,H2)-free graphs has bounded treewidth.
Hard problems that quickly become very easy Martin, Barnaby; Paulusma, Daniël; Smith, Siani
Information processing letters,
March 2022, 2022-03-00, Volume:
174
Journal Article
Peer reviewed
Open access
•NP-hard problems can be constant-time solvable for all other hereditary graph classes.•PSPACE-complete problems can be constant-time solvable for all other hereditary graph ...classes.•NEXPTIME-complete problems can be constant-time solvable for all other hereditary graph classes.
A graph class is hereditary if it is closed under vertex deletion. We give examples of NP-hard, PSPACE-complete and NEXPTIME-complete problems that become constant-time solvable for every hereditary graph class that is not equal to the class of all graphs.
Mim-width and sim-width are among the most powerful graph width parameters, with sim-width more powerful than mim-width, which is in turn more powerful than clique-width. While several NP-hard graph ...problems become tractable for graph classes whose mim-width is bounded and quickly computable, no algorithmic applications of boundedness of sim-width are known. In Kang et al. (2017) 32, it is asked whether Independent Set and 3-Colouring are NP-complete on graphs of sim-width at most 1. We observe that, for each k∈N, Listk-Colouring is polynomial-time solvable for graph classes whose sim-width is bounded and quickly computable. Moreover, we show that if the same holds for Independent Set, then IndependentH-Packing is polynomial-time solvable for graph classes whose sim-width is bounded and quickly computable. This problem is a common generalisation of Independent Set, Induced Matching, Dissociation Set and k-Separator.
We also make progress toward classifying the mim-width of (H1,H2)-free graphs in the case H1 is complete or edgeless. Our results solve some open problems in Brettell et al. (2022) 6.
Let G be a bipartite graph, and let H be a bipartite graph with a fixed bipartition (BH,WH). We consider three different, natural ways of forbidding H as an induced subgraph in G. First, G is ...H-free if it does not contain H as an induced subgraph. Second, G is strongly H-free if no bipartition of G contains an induced copy of H in a way that respects the bipartition of H. Third, G is weakly H-free if G has at least one bipartition that does not contain an induced copy of H in a way that respects the bipartition of H. Lozin and Volz characterized all bipartite graphs H for which the class of strongly H-free bipartite graphs has bounded clique-width. We extend their result by giving complete classifications for the other two variants of H-freeness.
PDF
