Mariana Escalante
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Mariana Escalante has a total of 23 co-authors. Here are the top co-authors by number of shared publications:
- Annegret K. Wagler
Université Clermont-Auvergne CNRS Mines de Saint-Étienne Clermont-Auvergne-INP LIMOS 63000 Clermont-Ferrand France
4 shared publications - Graciela Nasini
FCEIA Universidad Nacional de Rosario Rosario Argentina
4 shared publications Néstor E. Aguilera
Univ Nacl Litoral, Santa Fe, Argentina
3 shared publications- Silvia Bianchi
Universidad Nacional de Rosario
3 shared publications - Diego Delle Donne
ESSEC Business School
2 shared publications - G. Nasini
Universidad Nacional de Rosario, Rosario, Argentina
2 shared publications
Latest Publications
- Open Access
- 5 May 2026
- Published by Elsevier in SSRN Electronic Journal
The Minimum Chromatic Violation Problem: Complexity on Some Graph Classes
We consider a generalization of the classical vertex coloring problem on graphs (VCP), in which the edge set of the graph is partitioned into strong and weak edges. Given a number 𝑘 of available colors, the minimum chromatic violation problem (MCVP) asks for a vertex coloring such that no strong edge has its endpoints assigned to the same color; while minimizing the number of weak edges whose endpoints share the same color. In this work, we focus on the computational complexity of MCVP over several graph families such as interval and unit-interval graphs, among others. We show that MCVPisNP-hard even if the graph obtained by removing the weak edges is unit interval, trivially perfect or distance hereditary. On the other hand, we provide a polynomial-time algorithm that solves MCVP when the graph is a unit-interval graph without triangles with two or more weak edges. Furthermore, we provide an algorithm to solve MCVPon a graph 𝐺 when the set of weak edges 𝐹 includes only cut edges of 𝐺, and we show that in these cases, the algorithm finds an optimal solution in which no weak edge is violated or proves that the problem is infeasible. We show that the provided algorithm runs in polynomial time, whenever VCPcan be solved in polynomial time in the graph 𝐺 −𝐹, i.e., the graph obtained by removing the weak edges. Finally, we provide a polyhedral characterization of the chromatic violation polytope for block graphs when weak edges are cut edges, giving a theoretical counterpart to our algorithmic findings.
- 5 May 2026
- Published by Elsevier in SSRN Electronic Journal
Open AccessThe Minimum Chromatic Violation Problem: Complexity on Some Graph Classes
We consider a generalization of the classical vertex coloring problem on graphs (VCP), in which the edge set of the graph is partitioned into strong and weak edges. Given a number 𝑘 of available colors, the minimum chromatic violation problem (MCVP) asks for a vertex coloring such that no strong edge has its endpoints assigned to the same color; while minimizing the number of weak edges whose endpoints share the same color. In this work, we focus on the computational complexity of MCVP over several graph families such as interval and unit-interval graphs, among others. We show that MCVPisNP-hard even if the graph obtained by removing the weak edges is unit interval, trivially perfect or distance hereditary. On the other hand, we provide a polynomial-time algorithm that solves MCVP when the graph is a unit-interval graph without triangles with two or more weak edges. Furthermore, we provide an algorithm to solve MCVPon a graph 𝐺 when the set of weak edges 𝐹 includes only cut edges of 𝐺, and we show that in these cases, the algorithm finds an optimal solution in which no weak edge is violated or proves that the problem is infeasible. We show that the provided algorithm runs in polynomial time, whenever VCPcan be solved in polynomial time in the graph 𝐺 −𝐹, i.e., the graph obtained by removing the weak edges. Finally, we provide a polyhedral characterization of the chromatic violation polytope for block graphs when weak edges are cut edges, giving a theoretical counterpart to our algorithmic findings.
The Minimum Clique Routing Problem on Cycles
In the minimum clique routing problem on cycles mcrpc, we are given a cycle together with a set of demands (weighted terminals pairs) and the goal is to route all the pairs minimizing the maximum weight clique of the intersection graph induced by the routing. The nodes of this graph are the demands with their corresponding weights and two demands are adjacent when their routes share at least one arc. In this work, we are not only interested in the mcrpc but also in two natural subproblems. First, we consider the situation where the demands are disjoint, in the sense that every two demands do not share any of their corresponding terminals. Second, we analyze the subproblem where the weights of the routes are all equal. We first show that the problem is NP‐hard even in the subproblem of disjoint demands. For the case of arbitrary weights, we exhibit a simple combinatorial 2‐approximation algorithm and a ‐approximation algorithm based on rounding a solution of a relaxation of an integer linear programming formulation of our problem. Finally, we give a fixed parameter tractable algorithm for the case of uniform weights, whose parameter is the maximum number of demands for which a demand exists whose terminals alternate in the cycle with the terminals of each of them.
The Minimum Clique Routing Problem on Cycles
In the minimum clique routing problem on cycles mcrpc, we are given a cycle together with a set of demands (weighted terminals pairs) and the goal is to route all the pairs minimizing the maximum weight clique of the intersection graph induced by the routing. The nodes of this graph are the demands with their corresponding weights and two demands are adjacent when their routes share at least one arc. In this work, we are not only interested in the mcrpc but also in two natural subproblems. First, we consider the situation where the demands are disjoint, in the sense that every two demands do not share any of their corresponding terminals. Second, we analyze the subproblem where the weights of the routes are all equal. We first show that the problem is NP‐hard even in the subproblem of disjoint demands. For the case of arbitrary weights, we exhibit a simple combinatorial 2‐approximation algorithm and a ‐approximation algorithm based on rounding a solution of a relaxation of an integer linear programming formulation of our problem. Finally, we give a fixed parameter tractable algorithm for the case of uniform weights, whose parameter is the maximum number of demands for which a demand exists whose terminals alternate in the cycle with the terminals of each of them.
- 22 May 2024
- Published by Springer Nature
- p. 71-84
1-Persistency of the Clique Relaxation of the Stable Set Polytope
- 22 May 2024
- Published by Springer Nature
- p. 71-84
1-Persistency of the Clique Relaxation of the Stable Set Polytope
- 11 February 2023
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 332, 70-86
Lovász–Schrijver PSD-operator and the stable set polytope of claw-free graphs
- 11 February 2023
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 332, 70-86
Lovász–Schrijver PSD-operator and the stable set polytope of claw-free graphs
- Open Access
Lovász-Schrijver PSD-operator on Claw-Free Graphs
The subject of this work is the study of $\LS_+$-perfect graphs defined as those graphs $G$ for which the stable set polytope $\stab(G)$ is achieved in one iteration of Lov\'asz-Schrijver PSD-operator $\LS_+$, applied to its edge relaxation $\estab(G)$. In particular, we look for a polyhedral relaxation of $\stab(G)$ that coincides with $\LS_+(\estab(G))$ and $\stab(G)$ if and only if $G$ is $\LS_+$-perfect. An according conjecture has been recently formulated ($\LS_+$-Perfect Graph Conjecture); here we verify it for the well-studied class of claw-free graphs.Open AccessLovász-Schrijver PSD-operator on Claw-Free Graphs
The subject of this work is the study of $\LS_+$-perfect graphs defined as those graphs $G$ for which the stable set polytope $\stab(G)$ is achieved in one iteration of Lov\'asz-Schrijver PSD-operator $\LS_+$, applied to its edge relaxation $\estab(G)$. In particular, we look for a polyhedral relaxation of $\stab(G)$ that coincides with $\LS_+(\estab(G))$ and $\stab(G)$ if and only if $G$ is $\LS_+$-perfect. An according conjecture has been recently formulated ($\LS_+$-Perfect Graph Conjecture); here we verify it for the well-studied class of claw-free graphs. - Open Access
- 10 June 2016
- Published by Springer Nature in Mathematical Programming
- Vol. 162 (1-2) , 201-223
Lovász–Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
- 10 June 2016
- Published by Springer Nature in Mathematical Programming
- Vol. 162 (1-2) , 201-223
Open AccessLovász–Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
- 21 March 2016
- Published by Wiley in International Transactions in Operational Research
- Vol. 24 (1-2) , 325-337
Characterizing ‐perfect line graphs
- 21 March 2016
- Published by Wiley in International Transactions in Operational Research
- Vol. 24 (1-2) , 325-337
Characterizing ‐perfect line graphs
- 7 June 2015
- Published by Springer Nature in Annals of Operations Research
- Vol. 235 (1) , 233-258
The single-item lot-sizing polytope with continuous start-up costs and uniform production capacity
- 7 June 2015
- Published by Springer Nature in Annals of Operations Research
- Vol. 235 (1) , 233-258
The single-item lot-sizing polytope with continuous start-up costs and uniform production capacity
- Open Access
Characterizing N+-perfect line graphs
The subject of this contribution is the study of the Lov\'asz-Schrijver PSD-operator N+ applied to the edge relaxation of the stable set polytope of a graph. We are particularly interested in the problem of characterizing graphs for which N+ generates the stable set polytope in one step, called N+-perfect graphs. It is conjectured that the only N+-perfect graphs are those whose stable set polytope is described by inequalities with near-bipartite support. So far, this conjecture has been proved for near-perfect graphs, fs-perfect graphs, and webs. Here, we verify it for line graphs, by proving that in an N+-perfect line graph the only facet-defining graphs are cliques and odd holes.
Open AccessCharacterizing N+-perfect line graphs
The subject of this contribution is the study of the Lov\'asz-Schrijver PSD-operator N+ applied to the edge relaxation of the stable set polytope of a graph. We are particularly interested in the problem of characterizing graphs for which N+ generates the stable set polytope in one step, called N+-perfect graphs. It is conjectured that the only N+-perfect graphs are those whose stable set polytope is described by inequalities with near-bipartite support. So far, this conjecture has been proved for near-perfect graphs, fs-perfect graphs, and webs. Here, we verify it for line graphs, by proving that in an N+-perfect line graph the only facet-defining graphs are cliques and odd holes.
- Open Access
Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
We study the Lov\'asz-Schrijver lift-and-project operator ($LS_+$) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the $LS_+$-operator generates the stable set polytope in one step has been open since 1990. We call these graphs $LS_+$-perfect. In the current contribution, we pursue a full combinatorial characterization of $LS_+$-perfect graphs and make progress towards such a characterization by establishing a new, close relationship among $LS_+$-perfect graphs, near-bipartite graphs and a newly introduced concept of full-support-perfect graphs.
Open AccessLovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
We study the Lov\'asz-Schrijver lift-and-project operator ($LS_+$) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the $LS_+$-operator generates the stable set polytope in one step has been open since 1990. We call these graphs $LS_+$-perfect. In the current contribution, we pursue a full combinatorial characterization of $LS_+$-perfect graphs and make progress towards such a characterization by establishing a new, close relationship among $LS_+$-perfect graphs, near-bipartite graphs and a newly introduced concept of full-support-perfect graphs.