Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
MFCS Conference 2023 Conference Paper
Kempe changes were introduced in 1879 in an attempt to prove the 4-colour theorem. They are a convenient if not crucial tool to prove various colouring theorems. Here, we consider how to navigate from a colouring to another through Kempe changes. When is it possible? How fast?
SODA Conference 2023 Conference Paper
A graph is O k -free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We show that MAXIMUM INDEPENDENT SET and 3-COLORING in O k -free graphs can be solved in quasi-polynomial time. As a main technical result, we establish that “sparse” (here, not containing large complete bipartite graphs as subgraphs) O k -free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is proven sharp as there is an infinite family of O 2 -free graphs without K 3, 3 -subgraph and whose treewidth is (at least) logarithmic. Other consequences include that most of the central NP-complete problems (such as MAXIMUM INDEPENDENT SET, MINIMUM VERTEX COVER, MINIMUM DOMINATING SET, MINIMUM COLORING) can be solved in polynomial time in sparse O k -free graphs, and that deciding the O k -freeness of sparse graphs is polynomial time solvable. * This work was supported by the ANR projects DISTANCIA (ANR-17-CE40-0015), DIGRAPHS (ANR-19-CE48-0013-01), and TWIN-WIDTH (ANR-21-CE48-0014-01), by the LabEx PERSYVAL-lab (ANR-11-LABX-0025), and by the Vanier Canada Graduate Scholarships program. † The full version of the paper can be accessed at https: //arxiv. org/abs/2206. 00594
STOC Conference 2021 Conference Paper
We construct asymptotically optimal adjacency labelling schemes for every hereditary class containing 2 Ω( n 2 ) n -vertex graphs as n → ∞. This regime contains many classes of interest, for instance perfect graphs or comparability graphs, for which we obtain an adjacency labelling scheme with labels of n /4+ o ( n ) bits per vertex. This implies the existence of a reachability labelling scheme for digraphs with labels of n /4+ o ( n ) bits per vertex and comparability labelling scheme for posets with labels of n /4+ o ( n ) bits per element. All these results are best possible, up to the lower order term.
TCS Journal 2020 Journal Article
Given a k-coloring of a graph G, a Kempe-change for two colors a and b produces another k-coloring of G, as follows: first choose a connected component in the subgraph of G induced by the two color classes of a and b, and then swap the colors a and b in the component. Two k-colorings are called Kempe-equivalent if one can be transformed into the other by a sequence of Kempe-changes. We consider two problems, defined as follows: First, given two k-colorings of a graph G, Kempe Reachability asks whether they are Kempe-equivalent; and second, given a graph G and a positive integer k, Kempe Connectivity asks whether any two k-colorings of G are Kempe-equivalent. We analyze the complexity of these problems from the viewpoint of graph classes. We prove that Kempe Reachability is PSPACE -complete for any fixed k ≥ 3, and that it remains PSPACE -complete even when restricted to three colors and planar graphs of maximum degree six. Furthermore, we show that both problems admit polynomial-time algorithms on chordal graphs, bipartite graphs, and cographs. For each of these graph classes, we give a non-trivial upper bound on the number of Kempe-changes needed in order to certify that two k-colorings are Kempe-equivalent.
SODA Conference 2020 Conference Paper
An adjacency labeling scheme for a given class of graphs is an algorithm that for every graph G from the class, assigns bit strings (labels) to vertices of G so that for any two vertices u, v, whether u and v are adjacent can be determined by a fixed procedure that examines only their labels. It is known that planar graphs with n vertices admit a labeling scheme with labels of bit length (2 + o (1)) log n. In this work we improve this bound by designing a labeling scheme with labels of bit length ( + o (1)) log n. In graph-theoretical terms, this implies an explicit construction of a graph on n 4/3+ o (1) vertices that contains all planar graphs on n vertices as induced subgraphs, improving the previous best upper bound of n 2+ o (1). Our scheme generalizes to graphs of bounded Euler genus with the same label length up to a second-order term. All the labels of the input graph can be computed in polynomial time, while adjacency can be decided from the labels in constant time.
MFCS Conference 2019 Conference Paper
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.
FOCS Conference 2018 Conference Paper
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.
MFCS Conference 2017 Conference Paper
We continue research into a well-studied family of problems that ask if the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a graph from some specified graph class G. We let G be the class of k-degenerate graphs. The problem is known to be polynomial-time solvable if k=0 (bipartite graphs) and NP-complete if k=1 (near-bipartite graphs) even for graphs of diameter 4, as shown by Yang and Yuan, who also proved polynomial-time solvability for graphs of diameter 2. We show that recognizing near-bipartite graphs of diameter 3 is NP-complete resolving their open problem. To answer another open problem, we consider graphs of maximum degree D on n vertices. We show how to find A and B in O(n) time for k=1 and D=3, and in O(n^2) time for k >= 2 and D >= 4. These results also provide an algorithmic version of a result of Catlin [JCTB, 1979] and enable us to complete the complexity classification of another problem: finding a path in the vertex colouring reconfiguration graph between two given k-colourings of a graph of bounded maximum degree.
TCS Journal 2016 Journal Article
We show a kernel of at most 13k vertices for the Feedback Vertex Set problem restricted to planar graphs, i. e. , a polynomial-time algorithm that transforms an input instance ( G, k ) to an equivalent instance with at most 13k vertices. To this end we introduce a few new reduction rules. However, our main contribution is an application of the region decomposition technique in the analysis of the kernel size. We show that our analysis is tight, up to a constant additive term.