Generalisations of matrix partitions: Complexity and obstructions

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10488015" target="_blank" >RIV/00216208:11320/24:10488015 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=eJ8X5ouR1f" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=eJ8X5ouR1f</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2024.114652" target="_blank" >10.1016/j.tcs.2024.114652</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Generalisations of matrix partitions: Complexity and obstructions

Popis výsledku v původním jazyce

A trigraph is a graph where each pair of vertices is labelled either 0 (a non -arc), 1 (an arc) or * (both an arc and a non -arc). In a series of papers, Hell and co-authors (see for instance [P. Hell, 2014 [21]]) proposed to study the complexity of homomorphisms from graphs to trigraphs, called Matrix Partition Problems , where arcs and non -arcs can be both mapped to *-arcs, while a non -arc cannot be mapped to an arc, and vice -versa. Even though Matrix Partition Problems are generalisations of Constraint Satisfaction Problems (CSPs) , they share with them the property of being &quot;intrinsically&quot; combinatorial. So, the question of a possible P -time vs NP -complete dichotomy is a very natural one and was raised in Hell et al.&apos;s papers. We propose a generalisation of Matrix Partition Problems to relational structures and study them with respect to the question of a dichotomy. We first show that trigraph homomorphisms and Matrix Partition Problems are P -time equivalent, and then prove that one can also restrict (with respect to having a dichotomy) to relational structures with a single relation. Failing in proving that Matrix Partition Problems on directed graphs are not P -time equivalent to Matrix Partitions on relational structures, we give some evidence that it might be unlikely by formalising the reductions used in the case of CSPs and by showing that such reductions cannot work for the case of Matrix Partition Problems. We then turn our attention to Matrix Partition problems that can be described by finite sets of (inducedsubgraph) obstructions. We show, in particular, that any such problem has finitely many minimal obstructions if and only if it has finite duality. We conclude by showing that on trees (seen as trigraphs) it is NP -complete to decide whether a given tree has a homomorphism to another input trigraph. The latter shows a notable difference on tractability between CSP and Matrix Partition Problems as it is well-known that CSP is tractable on the class of trees.

Název v anglickém jazyce

Generalisations of matrix partitions: Complexity and obstructions

Popis výsledku anglicky

A trigraph is a graph where each pair of vertices is labelled either 0 (a non -arc), 1 (an arc) or * (both an arc and a non -arc). In a series of papers, Hell and co-authors (see for instance [P. Hell, 2014 [21]]) proposed to study the complexity of homomorphisms from graphs to trigraphs, called Matrix Partition Problems , where arcs and non -arcs can be both mapped to *-arcs, while a non -arc cannot be mapped to an arc, and vice -versa. Even though Matrix Partition Problems are generalisations of Constraint Satisfaction Problems (CSPs) , they share with them the property of being &quot;intrinsically&quot; combinatorial. So, the question of a possible P -time vs NP -complete dichotomy is a very natural one and was raised in Hell et al.&apos;s papers. We propose a generalisation of Matrix Partition Problems to relational structures and study them with respect to the question of a dichotomy. We first show that trigraph homomorphisms and Matrix Partition Problems are P -time equivalent, and then prove that one can also restrict (with respect to having a dichotomy) to relational structures with a single relation. Failing in proving that Matrix Partition Problems on directed graphs are not P -time equivalent to Matrix Partitions on relational structures, we give some evidence that it might be unlikely by formalising the reductions used in the case of CSPs and by showing that such reductions cannot work for the case of Matrix Partition Problems. We then turn our attention to Matrix Partition problems that can be described by finite sets of (inducedsubgraph) obstructions. We show, in particular, that any such problem has finitely many minimal obstructions if and only if it has finite duality. We conclude by showing that on trees (seen as trigraphs) it is NP -complete to decide whether a given tree has a homomorphism to another input trigraph. The latter shows a notable difference on tractability between CSP and Matrix Partition Problems as it is well-known that CSP is tractable on the class of trees.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

R - Projekt Ramcoveho programu EK

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

1879-2294

Svazek periodika

1007

Číslo periodika v rámci svazku

29. července 2024

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

19

Strana od-do

114652

Kód UT WoS článku

001251156300001

EID výsledku v databázi Scopus

2-s2.0-85195093129