Author name cluster

Stéphane Vialette

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.

15 papers

2 author rows

MFCS Conference 2024 Conference Paper

Generalizing Roberts' Characterization of Unit Interval Graphs

Virginia Ardévol Martínez
Romeo Rizzi
Abdallah Saffidine
Florian Sikora
Stéphane Vialette

For any natural number d, a graph G is a (disjoint) d-interval graph if it is the intersection graph of (disjoint) d-intervals, the union of d (disjoint) intervals on the real line. Two important subclasses of d-interval graphs are unit and balanced d-interval graphs (where every interval has unit length or all the intervals associated to a same vertex have the same length, respectively). A celebrated result by Roberts gives a simple characterization of unit interval graphs being exactly claw-free interval graphs. Here, we study the generalization of this characterization for d-interval graphs. In particular, we prove that for any d ⩾ 2, if G is a K_{1, 2d+1}-free interval graph, then G is a unit d-interval graph. However, somehow surprisingly, under the same assumptions, G is not always a disjoint unit d-interval graph. This implies that the class of disjoint unit d-interval graphs is strictly included in the class of unit d-interval graphs. Finally, we study the relationships between the classes obtained under disjoint and non-disjoint d-intervals in the balanced case and show that the classes of disjoint balanced 2-intervals and balanced 2-intervals coincide, but this is no longer true for d > 2.

Details

TCS Journal 2024 Journal Article

The Maximum Zero-Sum Partition problem

Guillaume Fertin
Oscar Fontaine
Géraldine Jean
Stéphane Vialette

We study the Maximum Zero-Sum Partition problem (or MZSP), defined as follows: given a multiset S = { a 1, a 2, …, a n } of integers a i ∈ Z ⁎ (where Z ⁎ denotes the set of non-zero integers) such that ∑ i = 1 n a i = 0, find a maximum cardinality partition { S 1, S 2, …, S k } of S such that, for every 1 ≤ i ≤ k, ∑ a j ∈ S i a j = 0. Solving MZSP is useful in genomics for computing evolutionary distances between pairs of species. Our contributions are a series of algorithmic results concerning MZSP, in terms of complexity, (in)approximability, with a particular focus on the fixed-parameter tractability of MZSP with respect to either (i) the size k of the solution, (ii) the number of negative (resp. positive) values in S and (iii) the largest integer in S.

Details DOI

TCS Journal 2023 Journal Article

On recognising words that are squares for the shuffle product

Romeo Rizzi
Stéphane Vialette

The shuffle of two words u and v of A ⁎ is the language u ⧢ v consisting of all words u 1 v 1 u 2 v 2 … u k v k, where k ≥ 0 and the u i and v i are words of A ⁎ such that u = u 1 u 2 … u k and v = v 1 v 2 … v k. In other words, u ⧢ v is the finite set of all words obtainable from merging the words u and v from left to right, but choosing the next symbol arbitrarily from u or v. A word u ∈ A ⁎ is a square for the shuffle product if it is the shuffle of two identical words (i. e. , u ∈ v ⧢ v for some v ∈ A ⁎ ). Whereas it can be decided in polynomial-time whether or not u ∈ v 1 ⧢ v 2 for given words u, v 1 and v 2 (J. -C. Spehner, 1986 [19]), we show in this paper that it is NP-complete to determine whether or not a word u is a square for the shuffle product. The novelty in our approach lies in representing words as linear graphs, in which deciding whether or not a given word is a square for the shuffle product reduces to computing some inclusion-free perfect matching. Finally, we prove that it is NP-complete to determine whether or not an input word is in the shuffle of a word with its reverse.

Details DOI

TCS Journal 2023 Journal Article

On shuffled-square-free words

Laurent Bulteau
Vincent Jugé
Stéphane Vialette

A word u is a shuffle of words v and w, which we denote by u ∈ v ⧢ w, if u can be obtained by mixing the letters from v and w in a way that preserves the left-to-right ordering of the letters from v and w. In case u ∈ v ⧢ v for some word v, the word u is called a shuffled-square. A word u is shuffled-square-free if it does not have a non-empty factor (i. e. , non-empty sequence of adjacent letters) that is a shuffled-square. Our contribution in this context is two-fold. First, we prove that there exist arbitrarily long shuffled-square-free words in any alphabet with six letters or more, thereby improving on a previous result of Guégan and Ochem. Furthermore, we show that recognizing shuffled-square-free words on arbitrary alphabets is NP -complete.

Details DOI

TCS Journal 2020 Journal Article

Recognizing binary shuffle squares is NP-hard

Laurent Bulteau
Stéphane Vialette

A shuffle of two words is formed by interleaving the characters into a new word, keeping the characters of each word in order. A word is a shuffle square if it is a shuffle of two identical words. Deciding whether a word is a shuffle square has been proved to be NP-complete independently by Buss and Soltys [5] and Rizzi and Vialette [20], the former proving the result for alphabets as small as 9 letters. We prove in this paper that deciding whether a binary word is a shuffle square is NP-complete.

Details DOI

TCS Journal 2018 Journal Article

Algorithmic and algebraic aspects of unshuffling permutations

Samuele Giraudo
Stéphane Vialette

A permutation is said to be a square if it can be obtained by shuffling two order-isomorphic patterns. The definition is intended to be the natural counterpart to the ordinary shuffle of words and languages. In this paper, we tackle the problem of recognizing square permutations from both the point of view of algebra and algorithms. On the one hand, we present some algebraic and combinatorial properties of the shuffle product of permutations. We follow an unusual line consisting in defining the shuffle of permutations by means of an unshuffling operator, known as a coproduct. This strategy allows to obtain easy proofs for algebraic and combinatorial properties of our shuffle product. We besides exhibit a bijection between square ( 213, 231 ) -avoiding permutations and square binary words. On the other hand, by using a pattern avoidance criterion on directed perfect matchings, we prove that recognizing square permutations is NP-complete.

Details DOI

TCS Journal 2013 Journal Article

Finding approximate and constrained motifs in graphs

Riccardo Dondi
Guillaume Fertin
Stéphane Vialette

One of the most relevant topics in the analysis of biological networks is the identification of functional motifs inside a network. A recent approach introduced in literature, called Graph Motif, represents the network as a vertex-colored graph, and the motif M as a multiset of colors. An occurrence of a motif M in a vertex-colored graph G is a connected induced subgraph of G whose vertex set is colored exactly as M. In this paper we investigate three different variants of the Graph Motif problem. The first two variants, Minimum Adding Motif (Min-Add Graph Motif) and Minimum Substitution Motif (Min-Sub Graph Motif), deal with approximate occurrences of a motif in the graph, while the third variant, Constrained Graph Motif (CGM), constrains the motif to contain a given set of vertices. We investigate the computational and parameterized complexity of the three problems. We show that Min-Add Graph Motifand Min-Sub Graph Motifare both NP-hard, even when M is a set, and the graph is a tree with maximum degree 4 in which each color appears at most twice. Then, we show that Min-Sub Graph Motifis fixed-parameter tractable when parameterized by the size of M. Finally, we consider the parameterized complexity of the CGMproblem; we give a fixed-parameter algorithm for graphs of bounded treewidth, and show that the problem is W[2]-hard when parameterized by ∣ M ∣, even if the input graph has diameter 2.

Details DOI

TCS Journal 2010 Journal Article

Complexity issues in color-preserving graph embeddings

Gaëlle Brevier
Romeo Rizzi
Stéphane Vialette

In the context of comparative analysis of protein–protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex (pattern graph) in the protein–protein interaction graph (target graph) of another species with respect to (w. r. t.) orthologous proteins. We give an efficient exponential-time randomized algorithm in case the occurrence of the pattern graph in the target graph is required to be exact. For approximate occurrences, we prove a tight inapproximability result and give four approximation algorithms that deal with bounded degree graphs, small ortholog numbers, linear forests and very simple yet hard instances, respectively.

Details DOI

TCS Journal 2010 Journal Article

Finding common structured patterns in linear graphs

Guillaume Fertin
Danny Hermelin
Romeo Rizzi
Stéphane Vialette

A linear graph is a graph whose vertices are linearly ordered. This linear ordering allows pairs of disjoint edges to be either preceding (<), nesting ( ⊏ ) or crossing ( ≬ ). Given a family of linear graphs, and a non-empty subset R ⊆ { <, ⊏, ≬ }, we are interested in the Maximum Common Structured Pattern (MCSP) problem: find a maximum size edge-disjoint graph, with edge pairs all comparable by one of the relations in R, that occurs as a subgraph in each of the linear graphs of the family. The MCSP problem generalizes many structure-comparison and structure-prediction problems that arise in computational molecular biology. We give tight hardness results for the MCSP problem for { <, ≬ } -structured patterns and { ⊏, ≬ } -structured patterns. Furthermore, we prove that the problem is approximable within ratios: (i) 2 ℋ ( k ) for { <, ≬ } -structured patterns, (ii) k 1 / 2 for { ⊏, ≬ } -structured patterns, and (iii) O ( k log k ) for { <, ⊏, ≬ } -structured patterns, where k is the size of the optimal solution and ℋ ( k ) = ∑ i = 1 k 1 / i is the k th harmonic number. Also, we provide combinatorial results concerning different types of structured patterns that are of independent interest in their own right.

Details DOI

TCS Journal 2009 Journal Article

On the parameterized complexity of multiple-interval graph problems

Michael R. Fellows
Danny Hermelin
Frances Rosamond
Stéphane Vialette

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to multiple-interval graphs, often allowing for more robustness in the modeling of the specific application. With this motivation in mind, a recent systematic study of optimization problems in multiple-interval graphs was initiated. In this sequel, we study multiple-interval graph problems from the perspective of parameterized complexity. The problems under consideration are k -Independent Set, k -Dominating Set, and k -Clique, which are all known to be W[1]-hard for general graphs, and NP-complete for multiple-interval graphs. We prove that k -Clique is in FPT, while k -Independent Set and k -Dominating Set are both W[1]-hard. We also prove that k -Independent Dominating Set, a hybrid of the two above problems, is also W[1]-hard. Our hardness results hold even when each vertex is associated with at most two intervals, and all intervals have unit length. Furthermore, as an interesting byproduct of our hardness results, we develop a useful technique for showing W[1]-hardness via a reduction from the k -Multicolored Clique problem, a variant of k -Clique. We believe this technique has interest in its own right, as it should help in simplifying W[1]-hardness results which are notoriously hard to construct and technically tedious.

Details DOI

TCS Journal 2008 Journal Article

Approximating the 2-interval pattern problem

Maxime Crochemore
Danny Hermelin
Gad M. Landau
Dror Rawitz
Stéphane Vialette

We address the issue of approximating the 2-Interval Pattern problem over its various models and restrictions. This problem, motivated by RNA secondary structure prediction, asks to find a maximum cardinality subset of a 2-interval set with respect to some prespecified geometric constraints. We present several constant factor approximation algorithms whose performance guarantee depends on the different possible restrictions imposed on the input 2-interval set. In addition, we show that our results extend to the weighted variant of the problem.

Details DOI

I&C Journal 2008 Journal Article

The Minimum Substring Cover problem

Danny Hermelin
Dror Rawitz
Romeo Rizzi
Stéphane Vialette

In this paper, we consider the problem of covering a set of strings S with a set C of substrings in S, where C is said to cover S if every string in S can be written as a concatenation of the substrings in C. We discuss applications for the problem that arise in the context of computational biology and formal language theory. We then proceed to show several hardness of approximation results for the problem, and in the main part of the paper, we focus on devising approximation algorithms using two generic paradigms—the local-ratio technique and linear programming rounding.

Details DOI

TCS Journal 2007 Journal Article

Extracting constrained 2-interval subsets in 2-interval sets

Guillaume Blin
Guillaume Fertin
Stéphane Vialette

2-interval sets were used in [S. Vialette, Pattern matching over 2-intervals sets, in: Proc. 13th Annual Symposium Combinatorial Pattern Matching, CPM 2002, in: Lecture Notes in Computer Science, vol. 2373, Springer-Verlag, 2002, pp. 53–63; S. Vialette, On the computational complexity of 2-interval pattern matching, Theoret. Comput. Sci. 312 (2–3) (2004) 223–249] for establishing a general representation for macroscopic describers of RNA secondary structures. In this context, we have a 2-interval for each legal local fold in a given RNA sequence, and a constrained pattern made of disjoint 2-intervals represents a putative RNA secondary structure. We focus here on the problem of extracting a constrained pattern in a set of 2-intervals. More precisely, given a set of 2-intervals D and a model R describing if two disjoint 2-intervals in a solution can be in precedence order (<), be allowed to nest ( ⊏ ) and/or be allowed to cross ( ≬ ), we consider the problem of finding a maximum cardinality subset D ′ ⊆ D of disjoint 2-intervals such that any two 2-intervals in D ′ agree with R. The different combinations of restrictions on model R alter the computational complexity of the problem, and need to be examined separately. In this paper, we improve the time complexity of [S. Vialette, On the computational complexity of 2-interval pattern matching, Theoret. Comput. Sci. 312 (2–3) (2004) 223–249] for model R = { ⊏ } by giving an optimal O ( n log n ) time algorithm, where n is the cardinality of the 2-interval set D. We also give a graph-like relaxation for model R = { ⊏, ≬ } that is solvable in O ( n 2 n ) time. Finally, we prove that the considered problem is NP-completefor model R = { <, ≬ } even for same-length intervals, and give a fixed-parameter tractability result based on the crossing structure of D.

Details DOI

MFCS Conference 2005 Conference Paper

Finding Exact and Maximum Occurrences of Protein Complexes in Protein-Protein Interaction Graphs

Guillaume Fertin
Romeo Rizzi
Stéphane Vialette

Abstract In the context of comparative analysis of protein-protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex G in the protein-protein interaction graph H of another species with respect to (w. r. t.) orthologous proteins. Two problems are considered: the Exact -( μ G, μ H )- Matching problem and the Max -( μ G, μ H ) problem, where μ G (resp. μ H ) denotes in both problems the maximum number of orthologous proteins in H (resp. G ) of a protein in G (resp. H ). Following [FLV04], the Exact -( μ G, μ H )- Matching problem asks for an injective homomorphism of G to H w. r. t. orthologous proteins. The optimization version is called the Max -( μ G, μ H )- Matching problem and is concerned with finding an injective mapping of a graph G to a graph H w. r. t. orthologous proteins that matches as many edges of G as possible. For both problems, the emphasis here is clearly on bounded degree graphs and extremal small values of parameters μ G and μ H.

Details

TCS Journal 2004 Journal Article

On the computational complexity of 2-interval pattern matching problems

Stéphane Vialette

The focus of this paper is on the computational complexity of pattern matching problems over set of 2-intervals. These problems occur in the context of molecular biology when a structured pattern, i. e. , a RNA secondary structure given in the form of a 2-interval pattern, has to be found in a sequence database. We show that finding a 2-interval pattern in a set of 2-intervals is a NP-complete problem even if no 2-interval of the pattern precedes the other, but can be solved in polynomial time for several interesting special cases. In particular, it is shown that the pseudo-knot free RNA secondary structure case is polynomial time solvable in our 2-interval formalism. Also, we investigate the computational complexity of finding the longest 2-interval pattern in a set of 2-intervals and prove several NP-completeness results as well as polynomial time solvable special cases.

Details DOI