Sobre o Número de Orientação Própria de Grafos Cordais

• Júlio Araújo UFC
• Alexandre Cezar UFC
• Carlos V. G. C. Lima UFCA
• Vinicius F. dos Santos UFMG
• Ana Silva UFC

DOI: https://doi.org/10.5753/etc.2021.16384

Resumo

Uma orientação $D$ de um grafo simples $G=(V,E)$ é própria se os vértices~$u$ e~$v$ possuem graus de entrada distintos, sempre que~$uv \in E$. O número de orientação de um grafo $G$ é o menor inteiro positivo $k$ tal que $G$ tem uma orientação própria $D$ com maior grau de entrada igual a $k$, denotado por $\po(G)$. Mostramos que decidir se $\po(G) \le k$ é~\FPT, parametrizado por $k$, quando restrito a grafos cordais, apresentamos um kernel exponencial para esta classe de grafos e mostramos que não existe kernel polinomial a menos que $\NP \subseteq \coNP/\poly$. Apresentamos também kernels melhores para grafos split e cobipartidos. Além disto, apresentamos limitantes para subclasses de grafos cordais como grafos blocos, periplanares cordais e para cografos.

Palavras-chave: orientação própria, grafos cordais, complexidade

Referências

Ahadi, A. and Dehghan, A. (2013). The complexity of the proper orientation number.Information Processing Letters, 113(19):799–803.

Araujo, J., Cezar, A., Lima, C., dos Santos, V., and Silva, A. S. (2020a). Proper orien-tations of chordal graphs. InAnais do V Encontro de Teoria da Computação, pages21–24, Porto Alegre, RS, Brasil. SBC.

Araujo, J., Cezar, A., Lima, C. V. G. C., dos Santos, V. F., and Silva, A. (2020b). On the proper orientation number of chordal graphs.

Araujo, J., Cohen, N., de Rezende, S. F., Havet, F., and Moura, P. F. (2015). On the proper orientation number of bipartite graphs. Theoretical Computer Science, 566(0):59–75.

Araujo, J., Havet, F., Sales, C. L., and Silva, A. (2016). Proper orientation of cacti.Theoretical Computer Science, 639:14–25.

Araujo, J., Sales, C. L., Sau, I., and Silva, A. (2019). Weighted proper orientations oftrees and graphs of bounded treewidth.Theoretical Computer Science, 771:39–48.

Bondy, J. A. and Murty, U. S. R. (2008).Graph theory, volume 244 ofGraduate Texts inMathematics. Springer-Verlag London.

Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk,M., and Saurabh, S. (2015).Parameterized Algorithms. Springer Publishing Company, Incorporated, 1st edition.

Drucker, A. (2012). New limits to classical and quantum instance compression. In53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 609–618. IEEE Computer Society.

Fomin, F. V., Lokshtanov, D., Saurabh, S., and Zehavi, M. (2019).Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press.

Garey, M. R. and Johnson, D. S. (1979).Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.

Knox, F., Matsumoto, N., de la Maza, S. G. H., Mohar, B., and Sales, C. L. (2017). Proper orientations of planar bipartite graphs. Graphs and Combinatorics, 33:1189–1194.