Sesión Matemática DiscretaGrafos cuyo cuadrado de línea es libre de $P_k$*
Martina Vergara
Departamento de Matemática, UNS e INMABB, UNS-CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
El grafo de línea de un grafo $G$, denotado $L(G)$, tiene un vértice por cada arista de $G$ y dos vértices de $L(G)$ son adyacentes si y solo si corresponden a aristas que comparten un extremo. El cuadrado de un grafo $G$, denotado $G^2$, tiene los mismos vértices que $G$ y dos vértices de $G^2$ son adyacentes si y solo si están unidos en $G$ por un camino de longitud a lo sumo $2$. Denotamos por $P_k$ al camino sin cuerdas con $k$ vértices. Un grafo es libre de $P_k$ si no contiene $P_k$ como subgrafo inducido.
Dos aristas se dicen independientes si no comparten extremos ni son ambas incidentes a una arista en común. El problema del Matching Inducido Máximo consiste en encontrar un conjunto de aristas independientes dos a dos de cardinalidad máxima. El problema del Conjunto Independiente Máximo consiste en hallar un conjunto de vértices no adyacentes dos a dos de máxima cardinalidad. Claramente, resolver el problema de Matching Inducido Máximo en un grafo $G$ es equivalente a resolver el problema de Conjunto Independiente Máximo en $L(G)^2$. Este hecho implica que el problema de Matching Inducido Máximo puede resolverse en tiempo polinomial (resp. cuasipolinomial) en la clase de todos los grafos $G$ tales que $L(G)^2\in\mathcal H$, para cada clase de grafos $\mathcal H$ en la cual el problema de Conjunto Independiente Máximo puede resolverse en tiempo polinomial (resp. cuasipolinomial).
Por ejemplo, una clase de grafos $\mathcal H$ en la cual el problema de Conjunto Independiente Máximo puede resolverse en tiempo polinomial es la clase de los grafos cordales [2]. Luego, el problema del Matching Inducido Máximo puede resolverse en tiempo polinomial en la clase de los grafos $G$ tales que $L(G)^2$ es cordal. Una caracterización de la clase de tales grafos $G$, por subgrafos inducidos prohibidos minimales, fue dada por Scheidweiler y Wiederrecht [4].
Una clase de grafos $\mathcal H$ en la cual el problema de Conjunto Independiente Máximo puede resolverse en tiempo cuasipolinomial es la clase de los grafos libres de $P_k$, para cada $k$ [1]. En consecuencia, si $\mathcal G_k$ es la clase de los grafos $G$ tales que $L(G)^2$ es libre de $P_k$ entonces el problema de Matching Inducido Máximo puede resolverse en tiempo cuasipolinomial en $\mathcal G_k$, cualquiera sea $k$. Hatzel y Wiederrecht [3] estudiaron el problema de caracterizar la clase $\mathcal G_k$ por subgrafos inducidos prohibidos. Sin embargo, su caracterización no es por subgrafos inducidos prohibidos minimales, pues algunos de los subgrafos prohibidos contienen a otros como subgrafos inducidos propios.
En este trabajo, obtenemos una caracterización por subgrafos inducidos prohibidos minimales de la clase $\mathcal G_k$, para cada $k$. Cada familia de subgrafos inducidos prohibidos minimales queda caracterizada mediante un conjunto de cadenas aceptadas por un autómata finito determinista.
*Este trabajo fue financiado parcialmente por el subsidio PGI 24/L115 de la Universidad Nacional del Sur. M.D. Safe fue financiado parcialmente por el subsidio PIBAA 28720210101185CO del CONICET.
Trabajo en conjunto con: Martín D. Safe (Departamento de Matemática, UNS e INMABB, UNS-CONICET).
Referencias
[1] P. Gartland and D. Lokshtanov. Independent set on Pk-free graphs in quasi-polynomial time. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pages 613–624. IEEE Computer Soc., Los Alamitos, CA, 2020.
[2] F. Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput., 1(2):180–187, 1972.
[3] M. Hatzel and S. Wiederrecht. On perfect linegraph squares. In Graph-theoretic Concepts in Computer Science, volume 11159 of Lecture Notes in Comput. Sci., pages 252–265. Springer, Cham, 2018.
[4] R. Scheidweiler and S. Wiederrecht. On chordal graph and line graph squares. Discrete Appl. Math., 243:239–247, 2018.