We introduce PASTA (Perceptual Assessment System for explanaTion of Artificial Intelligence), a novel human-centric framework for evaluating eXplainable AI (XAI) techniques in computer vision. Our first contribution is the creation of the PASTA-dataset, the first large-scale benchmark that spans a diverse set of models and both saliency-based and concept-based explanation methods. This dataset enables robust, comparative analysis of XAI techniques based on human judgment. Our second contribution is an automated, data-driven benchmark that predicts human preferences using the PASTA-dataset. This scoring called PASTA-score method offers scalable, reliable, and consistent evaluation aligned with human perception. Additionally, our benchmark allows for comparisons between explanations across different modalities, an aspect previously unaddressed. We then propose to apply our scoring method to probe the interpretability of existing models and to build more human interpretable XAI methods.

Fix a positive integer $r$, and a graph $G$ that is $K_{3,r}$-minor-free. Let $I_s$ and $I_t$ be two independent sets in $G$, each of size $k$. We begin with a ``token'' on each vertex of $I_s$ and seek to move all tokens to $I_t$, by repeated ``token jumping'', removing a single token from one vertex and placing it on another vertex. We require that each intermediate arrangement of tokens again specifies an independent set of size $k$. Given $G$, $I_s$, and $I_t$, we ask whether there exists a sequence of token jumps that transforms $I_s$ into $I_t$. When $k$ is part of the input, this problem is known to be PSPACE-complete. However, it was shown by Ito, Kamiński, and Ono (2014) to be fixed-parameter tractable. That is, the problem can be solved in time $f(k)\cdot Poly(n)$, for some function $f$ and polynomial $Poly(n)$, where $n$ denotes the order of $G$. Here we strengthen the upper bound on the running time in terms of $k$ by showing that the problem has a kernel of size linear in $k$. More precisely, we transform an arbitrary input problem on a $K_{3,r}$-minor-free graph (for some fixed positive integer $r$) into an equivalent problem on a ($K_{3,r}$-minor-free) graph with order $O(k)$. This answers positively a question of Bousquet, Mouawad, Nishimura, and Siebertz (2024) and improves the recent quadratic kernel of Cranston, Mühlenthaler, and Peyrille (2026). For planar graphs, we further strengthen this upper bound to get a kernel of size at most $39k$.

A graph H is an induced minor of G if there exists an induced minor model of H in G , that is, a collection of pairwise disjoint subsets of vertices of G labeled by the vertices of H , each inducing a connected subgraph in G , such that two vertices of H are adjacent if and only if there is an edge in G between the corresponding subsets. In this paper, we investigate structural properties of induced minor models, including bounds on treewidth and chromatic number of the subgraphs induced by minimal induced minor models. As algorithmic applications of our structural results, we make use of recent developments regarding tree-independence number to show that if H is the 4-wheel, the 5-vertex complete graph minus an edge, or a complete bipartite graph K 2 , q , then there is a polynomial-time algorithm to find in a given graph G an induced minor model of H in G , if there is one. We also develop an alternative polynomial-time algorithm for recognizing graphs that do not contain K 2 , 3 as an induced minor, which revolves around the idea of detecting the induced subgraphs whose presence is forced when the input graph contains K 2 , 3 as an induced minor. It turns out that all these induced subgraphs are Truemper configurations.

A dominating set of a graph G = (V,E) is a set of vertices D ⊆ V whose closed neighborhood is V, i.e., N[D] = V. We view a dominating set as a collection of tokens placed on the vertices of D. In the token sliding variant of the Dominating Set Reconfiguration problem (TS-DSR), we seek to transform a source dominating set into a target dominating set in G by sliding tokens along edges, and while maintaining a dominating set all along the transformation. TS-DSR is known to be PSPACE-complete even restricted to graphs of pathwidth w, for some non-explicit constant w and to be XL-complete parameterized by the size k of the solution. The first contribution of this article consists in using a novel approach to provide the first explicit constant for which the TS-DSR problem is PSPACE-complete, a question that was left open in the literature. From a parameterized complexity perspective, the token jumping variant of DSR, i.e., where tokens can jump to arbitrary vertices, is known to be FPT when parameterized by the size of the dominating sets on nowhere dense classes of graphs. But, in contrast, no non-trivial result was known about TS-DSR. We prove that DSR is actually much harder in the sliding model since it is XL-complete when restricted to bounded pathwidth graphs and even when parameterized by k plus the feedback vertex set number of the graph. This gives, for the first time, a difference of behavior between the complexity under token sliding and token jumping for some problem on graphs of bounded treewidth. All our results are obtained using a brand new method, based on the hardness of the so-called Tape Reconfiguration problem, a problem we believe to be of independent interest. We complement these hardness results with a positive result showing that DSR (parameterized by k) in the sliding model is FPT on planar graphs, also answering an open problem from the literature.

An impressive recent line of work has charted the complexity landscape of distributed graph algorithms. For many settings, it has been determined which time complexities exist, and which do not (in the sense that no local problem could have an optimal algorithm with that complexity). In this paper, we initiate the study of the landscape for space complexity of distributed graph algorithms. More precisely, we focus on the local certification setting, where a prover assigns certificates to nodes to certify a property, and where the space complexity is measured by the size of the certificates. Already for anonymous paths and cycles, we unveil a surprising landscape: - There is a gap between complexity $O(1)$ and $Θ(\log \log n)$ in paths. This is the first gap established in local certification. - There exists a property that has complexity $Θ(\log \log n)$ in paths, a regime that was not known to exist for a natural property. - There is a gap between complexity $O(1)$ and $Θ(\log n)$ in cycles, hence a gap that is exponentially larger than for paths. We then generalize our result for paths to the class of trees. Namely, we show that there is a gap between complexity $O(1)$ and $Θ(\log \log d)$ in trees, where $d$ is the diameter. We finally describe some settings where there are no gaps at all. To prove our results we develop a new toolkit, based on various results of automata theory and arithmetic, which is of independent interest.

Abstract. Local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called certificates. For many classic global properties, like checking the acyclicity of the network, the optimal size of the certificates depends on the size of the network, [Formula: see text]. In this paper, we focus on properties for which the size of the certificates does not depend on [Formula: see text] but on other parameters. We focus on three such important properties and prove tight bounds for all of them. Namely, we prove that the optimal certification size is the following: [Formula: see text] for [Formula: see text]-colorability (and even exactly [Formula: see text] bits in the anonymous model while previous works had only proved a 2-bit lower bound); [Formula: see text] for dominating sets at distance [Formula: see text] (an unexpected and tighter-than-usual bound); and [Formula: see text] for perfect matching in graphs of maximum degree [Formula: see text] (the first nontrivial bound parameterized by [Formula: see text]). We also prove some surprising upper bounds; for example, certifying the existence of a perfect matching in a planar graph can be done with only two bits. In addition, we explore various specific cases for these properties, in particular improving our understanding of the trade-off between locality of the verification and certificate size.

In local certification, vertices of a n-vertex graph perform a local verification to check if a given property is satisfied by the graph. This verification is performed thanks to certificates, which are pieces of information that are given to the vertices. In this work, we focus on the local certification of P 5 -freeness, and we prove a O ( n 3 / 2 ) upper bound on the size of the certificates, which is (to our knowledge) the first subquadratic upper bound for this property.

A non-crossing spanning tree of a set of points in the plane is a spanning tree whose edges pairwise do not cross. Avis and Fukuda in 1996 proved that there always exists a flip sequence of length at most $2n-4$ between any pair of non-crossing spanning trees (where $n$ denotes the number of points). Hernando et al. proved that the length of a minimal flip sequence can be of length at least $\frac 32 n$. Two recent results of Aichholzer et al. and Bousquet et al. improved the Avis and Fukuda upper bound by proving that there always exists a flip sequence of length respectively at most $2n - \log n$ and $2n - \sqrt{n}$. We improve the upper bound by a linear factor for the first time in 25 years by proving that there always exists a flip sequence between any pair of non-crossing spanning trees $T_1,T_2$ of length at most $c n$ where $c \approx 1.95$. Our result is actually stronger since we prove that, for any two trees $T_1,T_2$, there exists a flip sequence from $T_1$ to $T_2$ of length at most $c |T_1 \setminus T_2|$. We also improve the best lower bound in terms of the symmetric difference by proving that there exists a pair of trees $T_1,T_2$ such that a minimal flip sequence has length $\frac 53 |T_1 \setminus T_2|$, improving the lower bound of Hernando et al. by considering the symmetric difference instead of the number of vertices. We generalize this lower bound construction to non-crossing flips (where we close the gap between upper and lower bounds) and rotations.

In this paper, we investigate how local rules enforced at every node can influence the topology of a network. More precisely, we establish several results on the diameter of trees as a function of the number of nodes, as listed below. These results have important consequences on the landscape of locally checkable labelings (LCL) on unbounded degree graphs, a case in which our lack of knowledge is in striking contrast with that of bounded degree graphs, that has been intensively studied recently. First, we show that the diameter of a tree can be controlled very precisely by a local checker (that is, a distributed decision algorithm that accepts a graph iff all nodes accept locally), granted that its checkability radius is at least 2 (and that the target diameter is not too close to n). As a corollary, we prove that the gaps in the landscape of LCLs (in bounded-degree graphs) basically disappear in unbounded degree graphs. Second, we prove that for checkers at distance 1, the maximum diameter can only be trivial (constant or linear), while the minimum diameter can in addition be Θ(log n) and Θ(n^(1/k)) for k ∈ ℕ. These functions interestingly coincide with the known regimes for LCLs. Third, we explore computational restrictions of local checkers. In particular, we introduce a class of checkers, that we call degree-myopic, that cannot distinguish perfectly the degrees of their neighbors. With these checkers, we show that the maximum diameter can only be O(1), Θ(√n), Θ((log n)/(log log n)), Θ(log n), or Ω(n). Since gaps do appear in the maximum diameter, one can hope that an interesting LCL landscape exists for restricted local checkers. In addition to the LCL motivation, we hope that our distributed lenses can help give a new point of view on how global structures, such as living beings, can be maintained by local phenomena; understanding the trade-off between the power of the checking and the possible resulting shapes.

In this work, we provide an upper bound for global certification of graph homomorphism, a generalization of graph coloring. In certification, the nodes of a network should decide if the network satisfies a given property, thanks to small pieces of information called certificates. Here, there is only one global certificate which is shared by all the nodes, and the property we want to certify is the existence of a graph homomorphism to a given graph.

Local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called certificates. For many classic global properties, like checking the acyclicity of the network, the optimal size of the certificates depends on the size of the network, $n$. In this paper, we focus on properties for which the size of the certificates does not depend on $n$ but on other parameters. We focus on three such important properties and prove tight bounds for all of them. Namely, we prove that the optimal certification size is: $Θ(\log k)$ for $k$-colorability (and even exactly $\lceil \log k \rceil$ bits in the anonymous model while previous works had only proved a $2$-bit lower bound); $(1/2)\log t+o(\log t)$ for dominating sets at distance $t$ (an unexpected and tighter-than-usual bound) ; and $Θ(\log Δ)$ for perfect matching in graphs of maximum degree $Δ$ (the first non-trivial bound parameterized by $Δ$). We also prove some surprising upper bounds, for example, certifying the existence of a perfect matching in a planar graph can be done with only two bits. In addition, we explore various specific cases for these properties, in particular improving our understanding of the trade-off between locality of the verification and certificate size.

Abstract In the Token Sliding problem we are given a graph G and two independent sets $$I_s$$ I s and $$I_t$$ I t in G of size $$k \ge 1$$ k ≥ 1 . The goal is to decide whether there exists a sequence $$\langle I_1, I_2, \ldots , I_\ell \rangle $$ ⟨ I 1 , I 2 , … , I ℓ ⟩ of independent sets such that for all $$j \in \{1,\ldots , \ell - 1\}$$ j ∈ { 1 , … , ℓ - 1 } the set $$I_j$$ I j is an independent set of size k, $$I_1 = I_s$$ I 1 = I s , $$I_\ell = I_t$$ I ℓ = I t and $$I_j \triangle I_{j + 1} = \{u, v\} \in E(G)$$ I j ▵ I j + 1 = { u , v } ∈ E ( G ) . Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the problem asks whether there exists a sequence of independent sets that transforms $$I_s$$ I s into $$I_t$$ I t where at each step we are allowed to slide one token from a vertex to a neighboring vertex. In this paper, we focus on the parameterized complexity of Token Sliding parameterized by k. As shown by Bartier et al. (Algorithmica 83(9):2914–2951, 2021. https://doi.org/10.1007/s00453-021-00848-1 ), the problem is -hard on graphs of girth four or less, and the authors posed the question of whether there exists a constant $$p \ge 5$$ p ≥ 5 such that the problem becomes fixed-parameter tractable on graphs of girth at least p. We answer their question positively and prove that the problem is indeed fixed-parameter tractable on graphs of girth five or more, which establishes a full classification of the tractability of Token Sliding parameterized by the number of tokens based on the girth of the input graph.

Abstract. The discharging method is a powerful proof technique, especially for graph coloring problems. Its major downside is that it often requires lengthy case analyses, which are sometimes given to a computer for verification. However, it is much less common to use a computer to actively look for a discharging proof. In this paper, we use a linear programming approach to automatically look for a discharging proof. While our system is not entirely autonomous, we manage to make some progress toward Wegner’s conjecture for distance-2 coloring of planar graphs by showing that 12 colors are sufficient to color at distance 2 every planar graph with maximum degree 4.

Given a graph G and two independent sets I_s and I_t of size k, the Independent Set Reconfiguration problem asks whether there exists a sequence of independent sets that transforms I_s to I_t such that each independent set is obtained from the previous one using a so-called reconfiguration step. Viewing each independent set as a collection of k tokens placed on the vertices of a graph G, the two most studied reconfiguration steps are token jumping and token sliding. Over a series of papers, it was shown that the Token Jumping problem is fixed-parameter tractable when restricted to sparse graph classes, such as planar, bounded treewidth, and nowhere-dense graphs. As for the Token Sliding problem almost nothing is known. We remedy this situation by showing that Token Sliding is fixed-parameter tractable on graphs of bounded degree, planar graphs, and chordal graphs of bounded clique number.

Abstract. For a positive integer [Formula: see text], the [Formula: see text]-recoloring graph of a graph [Formula: see text] has as vertex set all proper [Formula: see text]-colorings of [Formula: see text] with two [Formula: see text]-colorings being adjacent if they differ by the color of exactly one vertex. A result of Dyer et al. regarding graphs of bounded degeneracy implies that the 7-recoloring graphs of planar graphs, the 5-recoloring graphs of triangle-free planar graphs and the 4-recoloring graphs planar graphs of girth at least six are connected. On the other hand, there are planar graphs whose 6-recoloring graph is disconnected, triangle-free planar graphs whose 4-recoloring graph is disconnected, and planar graphs of any given girth whose 3-recoloring graph is disconnected. The main result of this paper consists in showing, via a novel application of the discharging method, that the 4-recoloring graph of every planar graph of girth five is connected. This completes the classification of the connectedness of the recoloring graph for planar graphs of given girth. We also prove some theorems regarding the diameter of the recoloring graph of planar graphs.

Local certification consists in assigning labels (called certificates) to the nodes of a network to certify a property of the network or the correctness of a data structure distributed on the network. The verification of this certification must be local: a node typically sees only its neighbors in the network. The main measure of performance of a certification is the size of its certificates.

We investigate the complexity of finding a transformation from a given spanning tree in a graph to another given spanning tree in the same graph via a sequence of edge flips. The exchange property of the matroid bases immediately yields that such a transformation always exists if we have no constraints on spanning trees. In this paper, we wish to find a transformation which passes through only spanning trees satisfying some constraint. Our focus is bounding either the maximum degree or the diameter of spanning trees, and we give the following results. The problem with a lower bound on maximum degree is solvable in polynomial time, while the problem with an upper bound on maximum degree is PSPACE-complete. The problem with a lower bound on diameter is NP-hard, while the problem with an upper bound on diameter is solvable in polynomial time.

This document describes our exact Cluster Editing solver, PaSTEC, which got the third place in the 2021 PACE Challenge.

International audience

One of the fundamental and most-studied algorithmic problems in distributed computing on networks is graph coloring, both in bounded-degree and in general graphs. Recently, the study of this problem has been extended in two directions. First, the problem of recoloring, that is computing an efficient transformation between two given colorings (instead of computing a new coloring), has been considered, both to model radio network updates, and as a useful subroutine for coloring. Second, as it appears that general graphs and bounded-degree graphs do not model real networks very well (with, respectively, pathological worst-case topologies and too strong assumptions), coloring has been studied in more specific graph classes. In this paper, we study the intersection of these two directions: distributed recoloring in two relevant graph classes, interval and chordal graphs. More formally, the question of recoloring a graph is as follows: we are given a network, an input coloring α and a target coloring β, and we want to find a schedule of colorings to reach β starting from α. In a distributed setting, the schedule needs to be found within the LOCAL model, where nodes communicate with their direct neighbors synchronously. The question we want to answer is: how many rounds of communication {are} needed to produce a schedule, and what is the length of this schedule? In the case of interval and chordal graphs, we prove that, if we have less than 2ω colors, ω being the size of the largest clique, extra colors will be needed in the intermediate colorings. For interval graphs, we produce a schedule after O(poly(Δ)log*n) rounds of communication, and for chordal graphs, we need O(ω²Δ²log n) rounds to get one. Our techniques also improve classic coloring algorithms. Namely, we get ω+1-colorings of interval graphs in O(ωlog*n) rounds and of chordal graphs in O(ωlog n) rounds, which improves on previous known algorithms that use ω+2 colors for the same running times.

Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. In the last few years, certification of graph classes received a considerable attention. The goal is to certify that a graph G belongs to a given graph class 𝒢. Such certifications with labels of size O(log n) (where n is the size of the network) exist for trees, planar graphs and graphs embedded on surfaces. Feuilloley et al. ask if this can be extended to any class of graphs defined by a finite set of forbidden minors. In this paper, we develop new decomposition tools for graph certification, and apply them to show that for every small enough minor H, H-minor-free graphs can indeed be certified with labels of size O(log n). We also show matching lower bounds with a new simple proof technique.

In the Token Jumping problem we are given a graph $$G = (V,E)$$ and two independent sets S and T of G, each of size $$k \ge 1$$ . The goal is to determine whether there exists a sequence of k-sized independent sets in G, $$\langle S_0, S_1, \ldots , S_\ell \rangle$$ , such that for every i, $$|S_i| = k$$ , $$S_i$$ is an independent set, $$S = S_0$$ , $$S_\ell = T$$ , and $$|S_i \varDelta S_{i+1}| = 2$$ . In other words, if we view each independent set as a collection of tokens placed on a subset of the vertices of G, then the problem asks for a sequence of independent sets which transforms S to T by individual token jumps which maintain the independence of the sets. This problem is known to be PSPACE-complete on very restricted graph classes, e.g., planar bounded degree graphs and graphs of bounded bandwidth. A closely related problem is the Token Sliding problem, where instead of allowing a token to jump to any vertex of the graph we instead require that a token slides along an edge of the graph. Token Sliding is also known to be PSPACE-complete on the aforementioned graph classes. We investigate the parameterized complexity of both problems on several graph classes, focusing on the effect of excluding certain cycles from the input graph. In particular, we show that both Token Sliding and Token Jumping are fixed-parameter tractable on $$C_4$$ -free bipartite graphs when parameterized by k. For Token Jumping, we in fact show that the problem admits a polynomial kernel on $$\{C_3,C_4\}$$ -free graphs. In the case of Token Sliding, we also show that the problem admits a polynomial kernel on bipartite graphs of bounded degree. We believe both of these results to be of independent interest. We complement these positive results by showing that, for any constant $$p \ge 4$$ , both problems are W[1]-hard on $$\{C_4, \dots , C_p\}$$ -free graphs and Token Sliding remains W[1]-hard even on bipartite graphs.

Abstract We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs $$ H_{1} $$ H 1 and $$H_2$$ H 2 for all but six pairs $$(H_1,H_2)$$ ( 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)$$ ( H 1 , H 2 ) -free graphs to five.

A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for M AXIMUM C LIQUE on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics ’90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time 2 Õ( n 2/3 ) for M AXIMUM C LIQUE on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for M AX C LIQUE on disk and unit ball graphs. M AX C LIQUE on unit ball graphs is equivalent to finding, given a collection of points in R 3 , a maximum subset of points with diameter at most some fixed value. In stark contrast, M AXIMUM C LIQUE on ball graphs and unit 4-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we show that, for all those problems, there is a constant ratio of approximation that cannot be attained even in time 2 n 1−ɛ , unless the Exponential Time Hypothesis fails.

Let $G$ be a graph and $T_1,T_2$ be two spanning trees of $G$. We say that $T_1$ can be transformed into $T_2$ via an edge flip if there exist two edges $e \in T_1$ and $f$ in $T_2$ such that $T_2= (T_1 \setminus e) \cup f$. Since spanning trees form a matroid, one can indeed transform a spanning tree into any other via a sequence of edge flips, as observed by Ito et al. We investigate the problem of determining, given two spanning trees $T_1,T_2$ with an additional property $Π$, if there exists an edge flip transformation from $T_1$ to $T_2$ keeping property $Π$ all along. First we show that determining if there exists a transformation from $T_1$ to $T_2$ such that all the trees of the sequence have at most $k$ (for any fixed $k \ge 3$) leaves is PSPACE-complete. We then prove that determining if there exists a transformation from $T_1$ to $T_2$ such that all the trees of the sequence have at least $k$ leaves (where $k$ is part of the input) is PSPACE-complete even restricted to split, bipartite or planar graphs. We complete this result by showing that the problem becomes polynomial for cographs, interval graphs and when $k=n-2$.

Given a graph G and an integer k, a token addition and removal (TAR for short) reconfiguration sequence between two dominating sets D_s and D_t of size at most k is a sequence S = ⟨ D₀ = D_s, D₁ …, D_𝓁 = D_t ⟩ of dominating sets of G such that any two consecutive dominating sets differ by the addition or deletion of one vertex, and no dominating set has size bigger than k. We first improve a result of Haas and Seyffarth [R. Haas and K. Seyffarth, 2017], by showing that if k = Γ(G)+α(G)-1 (where Γ(G) is the maximum size of a minimal dominating set and α(G) the maximum size of an independent set), then there exists a linear TAR reconfiguration sequence between any pair of dominating sets. We then improve these results on several graph classes by showing that the same holds for K_𝓁-minor free graph as long as k ≥ Γ(G)+O(𝓁 √(log 𝓁)) and for planar graphs whenever k ≥ Γ(G)+3. Finally, we show that if k = Γ(G)+tw(G)+1, then there also exists a linear transformation between any pair of dominating sets.

Let $k$ and $d$ be such that $k \ge d+2$. Consider two $k$-colorings of a $d$-degenerate graph $G$. Can we transform one into the other by recoloring one vertex at each step while maintaining a proper coloring at any step? Cereceda et al. answered that question in the affirmative, and exhibited a recolouring sequence of exponential length. If $k=d+2$, we know that there exists graphs for which a quadratic number of recolorings is needed. And when $k=2d+2$, there always exists a linear transformation. In this paper, we prove that, as long as $k \ge d+4$, there exists a transformation of length at most $f(Δ) \cdot n$ between any pair of $k$-colorings of chordal graphs (where $Δ$ denotes the maximum degree of the graph). The proof is constructive and provides a linear time algorithm that, given two $k$-colorings $c_1,c_2$ computes a linear transformation between $c_1$ and $c_2$.

Maximum Independent Set (MIS for short) is in general graphs the paradigmatic $W[1]$-hard problem. In stark contrast, polynomial-time algorithms are known when the inputs are restricted to structured graph classes such as, for instance, perfect graphs (which includes bipartite graphs, chordal graphs, co-graphs, etc.) or claw-free graphs. In this paper, we introduce some variants of co-graphs with parameterized noise, that is, graphs that can be made into disjoint unions or complete sums by the removal of a certain number of vertices and the addition/deletion of a certain number of edges per incident vertex, both controlled by the parameter. We give a series of FPT Turing-reductions on these classes and use them to make some progress on the parameterized complexity of MIS in $H$-free graphs. We show that for every fixed $t \geqslant 1$, MIS is FPT in $P(1,t,t,t)$-free graphs, where $P(1,t,t,t)$ is the graph obtained by substituting all the vertices of a four-vertex path but one end of the path by cliques of size $t$. We also provide randomized FPT algorithms in dart-free graphs and in cricket-free graphs. This settles the FPT/W[1]-hard dichotomy for five-vertex graphs $H$.

We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a flip operation exchanges the edges in an alternating cycle of length four. We are interested in the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem is PSPACE-complete even for split graphs and for bipartite graphs of bounded bandwidth with maximum degree five. We then investigate polynomial-time solvable cases. Specifically, we prove that the problem is solvable in polynomial time for strongly orderable graphs (that include interval graphs and strongly chordal graphs), for outerplanar graphs, and for cographs (also known as P_4-free graphs). Furthermore, for each yes-instance from these graph classes, we show that a linear number of flip operations is sufficient and we can exhibit a corresponding sequence of flip operations in polynomial time.

We propose a polynomial-time algorithm which takes as input a finite set of points of R^3 and computes, up to arbitrary precision, a maximum subset with diameter at most 1. More precisely, we give the first randomized EPTAS and deterministic PTAS for Maximum Clique in unit ball graphs. Our approximation algorithm also works on disk graphs with arbitrary radii, in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for Maximum Clique on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics '90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. Recently, it was shown that the disjoint union of two odd cycles is never the complement of a disk graph [Bonnet, Giannopoulos, Kim, Rzazewski, Sikora; SoCG '18]. This enabled the authors to derive a QPTAS and a subexponential algorithm for Max Clique on disk graphs. In this paper, we improve the approximability to a randomized EPTAS (and a deterministic PTAS). More precisely, we obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. We then address the question of computing Max Clique for disks in higher dimensions. We show that intersection graphs of unit balls, like disk graphs, do not admit the complement of two odd cycles as an induced subgraph. This, in combination with the first result, straightforwardly yields a randomized EPTAS for Max Clique on unit ball graphs. In stark contrast, we show that on ball graphs and unit 4-dimensional disk graphs, Max Clique is NP-hard and does not admit an approximation scheme even in subexponential-time, unless the Exponential Time Hypothesis fails.

In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of H-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains NP-hard for most graphs H, we study its fixed-parameter tractability and make progress towards a dichotomy between FPT and W[1]-hard cases. We first show that MIS remains W[1]-hard in graphs forbidding simultaneously K_{1, 4}, any finite set of cycles of length at least 4, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of Dabrowski et al. concerning C_4-free graphs. Then we extend the polynomial algorithm of Alekseev when H is a disjoint union of edges to an FPT algorithm when H is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of iterative expansion accompanied by the extraction of a particular structure using Ramsey's theorem. Iterative expansion is a maximization version of the so-called iterative compression. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs H.

Let $G=(V,E)$ be a graph on $n$ vertices and $R$ be a set of pairs of vertices in $V$ called requests. A multicut is a subset $F$ of $E$ such that every request $xy$ of $R$ is separated by $F$, i.e., every $xy$-path of $G$ intersects $F$. We show that there exists an $O(f(k)n^c)$ algorithm which decides if there exists a multicut of size at most $k$. In other words, the Multicut problem parameterized by the solution size $k$ is fixed-parameter tractable (FPT).

Since the 1990s spectrum auctions have been implemented world-wide. This has provided for a practical examination of an assortment of auction mechanisms and, amongst these, two simultaneous ascending price auctions have proved to be extremely successful. These are the simultaneous multiround ascending auction (SMRA) and the combinatorial clock auction (CCA). It has long been known that, for certain classes of valuation functions, the SMRA provides good theoretical guarantees on social welfare. However, no such guarantees were known for the CCA. In this paper, we show that CCA does provide strong guarantees on social welfare provided the price increment and stopping rule are well-chosen. This is very surprising in that the choice of price increment has been used primarily to adjust auction duration and the stopping rule has attracted little attention. The main result is a polylogarithmic approximation guarantee for social welfare when the maximum number of items demanded by a bidder is fixed. Specifically, we show that either the revenue of the CCA is at least an -fraction of the optimal welfare or the welfare of the CCA is at least an -fraction of the optimal welfare, where n is the number of bidders and m is the number of items. As a corollary, the welfare ratio – the worst case ratio between the social welfare of the optimum allocation and the social welfare of the CCA allocation – is at most O( 2 · log n·· log2 m). We emphasize that this latter result requires no assumption on bidders valuation functions. Finally, we prove that such a dependence on is necessary. In particular, we show that the welfare ratio of the CCA is at least .

Erdös and Hajnal conjectured that for every graph $H$, there exists a constant $c_H$ such that every graph $G$ on $n$ vertices which does not contain an induced copy of $H$ has a clique or a stable set of size $n^{c_H}$. We prove that for every $k$ there exists $c_k>0$ such that every graph $G$ on $n$ vertices not inducing a cycle of length at least $k$ nor its complement contains a clique or a stable set of size at least $n^{c_k}$.

We examine cooperative games where the viability of a coalition is determined by whether or not its members have the ability to communicate amongst themselves independently of non-members. This necessary condition for viability was proposed by Myerson [1977] and is modeled via an interaction graph G=(V,E); a coalition S ⊆ V is then viable if and only if the induced graph G[S] is connected. The non-emptiness of the core of a coalition game can be tested by a well-known covering LP. Moreover, the integrality gap of its dual packing LP defines exactly the multiplicative least-core and the relative cost of stability of the coalition game. This gap is upper bounded by the packing-covering ratio which, for graphical coalition games, is known to be at most the treewidth of the interaction graph plus one [Meir et al. 2013].

The simultaneous multiple-round auction (SMRA) and the combinatorial clock auction (CCA) are the two primary mechanisms used to sell bandwidth. Recently, it was shown that the CCA provides good welfare guarantees for general classes of valuation functions [7]. This motivates the question of whether similar welfare guarantees hold for the SMRA in the case of general valuation functions. We show the answer is no. But we prove that good welfare guarantees still arise if the degree of complementarities in the bidder valuations are bounded. In particular, if bidder valuations functions are $$\alpha $$ -near-submodular then, under truthful bidding, the SMRA has a welfare ratio (the worst case ratio between the social welfare of the optimal allocation and the auction allocation) of at most $$(1+\alpha )$$ . However, for $$\alpha >1$$ , this is a bicriteria guarantee, to obtain good welfare under truthful bidding requires relaxing individual rationality. We prove this bicriteria guarantee is asymptotically (almost) tight. Finally, we examine what strategies are required to ensure individual rationality in the SMRA with general valuation functions. First, we provide a weak characterization, namely secure bidding, for individual rationality. We then show that if the bidders use a profit-maximizing secure bidding strategy the welfare ratio is at most $$1+\alpha $$ . Consequently, by bidding securely, it is possible to obtain the same welfare guarantees as truthful bidding without the loss of individual rationality.

An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbors within the code. We show a dichotomy for the size of the smallest identifying code in classes of graphs closed under induced subgraphs. Our dichotomy is derived from the VC-dimension of the considered class $\mathcal{C}$, that is, the maximum VC-dimension over the hypergraphs formed by the closed neighborhoods of elements of $\mathcal{C}$. We show that hereditary classes with infinite VC-dimension have infinitely many graphs with an identifying code of size logarithmic in the number of vertices, while classes with finite VC-dimension have a polynomial lower bound. We then turn to approximation algorithms. We show that Min Id Code (the problem of finding a smallest identifying code in a given graph from some class $\mathcal{C}$) is log-APX-hard for any hereditary class of infinite VC-dimension. For hereditary classes of finite VC-dimension, the only known previous results show that we can approximate Min Id Code within a constant factor in some particular classes, e.g., line graphs, planar graphs, and unit interval graphs. We prove that Min Id Code can be approximate within a factor 6 for interval graphs. In contrast, we show that Min Id Code on $C_4$-free bipartite graphs (a class of finite VC-dimension) cannot be approximated to within a factor of $c \log(|V|)$ for some $c>0$.

We discuss three equivalent forms of the same problem arising in communication complexity, constraint satisfaction problems, and graph coloring. Some partial results are discussed.

Let G=(V,E) be a graph on n vertices and R be a set of pairs of vertices in V called requests. A multicut is a subset F of E such that every request xy of R is cut by F, i.e. every xy-path of G intersects F. We show that there exists an O(f(k)nc) algorithm which decides if there exists a multicut of size at most k. In other words, the Multicut problem parameterized by the solution size k is Fixed-Parameter Tractable.

The {\sc Multicut In Trees} problem consists in deciding, given a tree, a set of requests (i.e. paths in the tree) and an integer $k$, whether there exists a set of $k$ edges cutting all the requests. This problem was shown to be FPT by Guo and Niedermeyer (2005). They also provided an exponential kernel. They asked whether this problem has a polynomial kernel. This question was also raised by Fellows (2006). We show that {\sc Multicut In Trees} has a polynomial kernel.