Search

The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk is compatible if all pairs of consecutive edges on the walk are permitted. Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics. A widely-studied special case are edge-colored graphs, where a compatible walk is forbidden to take two edges of the same color in a row. We initiate the study of fundamental problems on finding paths, cycles and walks in forbidden-transition graphs from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph-width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph is W[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth). On the other hand, we show an algebraic trick that yields tractability when parameterized by treewidth for finding a compatible Hamiltonian cycle in the edge-colored graph setting.

A 2-edge-coloured graph G is supereulerian if G contains a spanning closed trail in which the edges alternate in colours. We show that for general 2-edge-coloured graphs it is NP-complete to decide whether the graph is supereulerian. An eulerian factor of a 2-edge-coloured graph is a collection of vertex-disjoint induced subgraphs which cover all the vertices of G such that each of these subgraphs is supereulerian. We give a polynomial algorithm to test whether a 2-edge-coloured graph has an eulerian factor and to produce one when it exists. A 2-edge-coloured graph is (trail-)colour-connected if it contains a pair of alternating (u, v)-paths ((u, v)-trails) whose union is an alternating closed walk for every pair of distinct vertices u, v. We prove that a 2-edge-coloured complete bipartite graph is supereulerian if and only if it is colour-connected and has an eulerian factor. A 2-edge-coloured graph is M-closed if xz is an edge of G whenever some vertex u is joined to both x and z by edges of the same colour. M-closed 2-edge-coloured graphs, introduced in Contreras-Balbuena et al. (Discret Math Theoret Comput Sci 21:1, 2019), form a rich generalization of 2-edge-coloured complete graphs. We show that if G is obtained from an M-closed 2-edge-coloured graph H by substituting independent sets for the vertices of H, then G is supereulerian if and only if G is trail-colour-connected and has an eulerian factor. Finally we discuss 2-edge-coloured complete multipartite graphs and show that such a graph may not be supereulerian even if it is trail-colour-connected and has an eulerian factor.

We construct an infinite family of counterexamples to Thomassen’s conjecture that the vertices of every 3-connected, cubic graph on at least 8 vertices can be colored blue and red such that the blue subgraph has maximum degree at most 1 and the red subgraph minimum degree at least 1 and contains no path on 4 vertices.

The weak 2-linkage problem for digraphs asks for a given digraph and vertices s 1 , s 2 , t 1 , t 2 whether D contains a pair of arc-disjoint paths P 1 , P 2 such that P i is an ( s i , t i ) -path. This problem is NP-complete for general digraphs but polynomially solvable for acyclic digraphs [8] . Recently it was shown [3] that if D is equipped with a weight function w on the arcs which satisfies that all edges have positive weight, then there is a polynomial algorithm for the variant of the weak-2-linkage problem when both paths have to be shortest paths in D. In this paper we consider the unit weight case and prove that for every pair of constants k 1 , k 2 , there is a polynomial algorithm which decides whether the input digraph D has a pair of arc-disjoint paths P 1 , P 2 such that P i is an ( s i , t i ) -path of length no more than d ( s i , t i ) + k i , for i = 1 , 2 , where d ( s i , t i ) denotes the length of the shortest ( s i , t i ) -path. We prove that, unless the exponential time hypothesis (ETH) fails, there is no polynomial algorithm for deciding the existence of a solution P 1 , P 2 to the weak 2-linkage problem where each path P i has length at most d ( s i , t i ) + c log 1 + ϵ ⁡ n for some constant c.

The dichromatic number $\overrightarrow{\chi}(D)$ of a digraph $D$ is the minimum number of colors needed to color the vertices of $D$ such that each color class induces an acyclic subdigraph of $D$. A digraph $D$ is $k$-critical if $\overrightarrow{\chi}(D) = k$ but $\overrightarrow{\chi}(D') < k$ for all proper subdigraphs $D'$ of $D$. We examine methods for creating infinite families of critical digraphs, the Dirac join and the directed and bidirected Hajós join. We prove that a digraph $D$ has dichromatic number at least $k$ if and only if it contains a subdigraph that can be obtained from bidirected complete graphs on $k$ vertices by directed Hajós joins and identifying non-adjacent vertices. Building upon that, we show that a digraph $D$ has dichromatic number at least $k$ if and only if it can be constructed from bidirected $K_k$'s by using directed and bidirected Hajós joins and identifying non-adjacent vertices (so called Ore joins), thereby transferring a well-known result of Urquhart to digraphs. Finally, we prove a Gallai-type theorem that characterizes the structure of the low vertex subdigraph of a critical digraph, that is, the subdigraph, which is induced by the vertices that have in-degree $k-1$ and out-degree $k-1$ in $D$.

This paper studies the problem of proper-walk connection number: given an undirected connected graph, our aim is to colour its edges with as few colours as possible so that there exists a properly coloured walk between every pair of vertices of the graph i.e. a walk that does not use consecutively two edges of the same colour. The problem was already solved on several classes of graphs but still open in the general case. We establish that the problem can always be solved in polynomial time in the size of the graph and we provide a characterization of the graphs that can be properly connected with $k$ colours for every possible value of $k$., Comment: 25 pages, 9 figures

A forbidden transition graph is a graph defined together with a set of permitted transitions i.e. unordered pair of adjacent edges that one may use consecutively in a walk in the graph. In this paper, we look for the smallest set of transitions needed to be able to go from any vertex of the given graph to any other. We prove that this problem is NP-hard and study approximation algorithms. We develop theoretical tools that help to study this problem.

The maximal density of a measurable subset of $${{\mathbb {R}}}^n$$ avoiding Euclidean distance 1 is unknown except in the trivial case of dimension 1. In this paper, we consider the case of a distance associated to a polytope that tiles space, where it is likely that the sets avoiding distance 1 are of maximal density $$2^{-n}$$ , as conjectured by Bachoc and Robins. We prove that this is true for $$n=2$$ , and for the Voronoi regions of the lattices $$A_n$$ , $$n\ge 2$$ .

International audience; This paper studies the problem of traffic monitoring which consists of differentiating a set of walks on a directed graph by placing sensors on as few arcs as possible. The problem of characterising a set of individuals by testing as few attributes as possible is already well-known, but traffic monitoring presents new challenges that the previous models of separation fall short from modelling such as taking into account the multiplicity and order of the arcs in a walk. We introduce a new and stronger model of separation based on languages that generalises the traffic monitoring problem. We study three subproblems with practical applications and develop methods to solve them by combining integer linear programming, separating codes and language theory.

This paper studies the problem of traffic monitoring which consists in differentiating a set of walks on a directed graphs by placing sensors on as few arcs as possible. The problem of characterising a set of individuals by testing as few attributes as possible is already well-known but traffic monitoring presents new challenges that the previous models of separation fall short at modelling such as taking into account the multiplicity and order of the arcs in a walk. We therefore introduce a new stronger model of separation based on languages that generalises the traffic monitoring problem. We study two subproblems that we think are especially relevant for practical applications and develop methods to solve them combining integer linear programming, separating codes and language theory.

Genomic structural variations play key roles in genetic diversity and disease. Despite recent advances in structural variation discovery, many variants are yet to be discovered. Midsize insertions and deletions pose particularly involved algorithmic challenges. The recent CLEVER algorithm addressed these challenges with a statistical model on cliques in a graph whose nodes are read alignments and whose edges arise from a statistical test on length and overlap of read alignments. However, the resulting read alignment clusters tend to be too small and are heavily overlapping, which leads to losses in recall performance rates. Here we present a model based on weighted cluster editing, which alleviates these issues: clusters are provably non-overlapping and tend to be larger. In order to render the inherent optimization problem tractable on all read alignments of a genome, we present a novel, principled heuristic, which runs in time linear in the length of the genome. The heuristic is based on an exact polynomial-time algorithm for weighted cluster editing in one-dimensional point graphs. We demonstrate that the new model improves recall rates achieved by CLEVER.