Arrow Research search

Author name cluster

Pavol Hell

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.

13 papers
2 author rows

Possible papers

13

TCS Journal 2024 Journal Article

List homomorphisms to separable signed graphs

  • Jan Bok
  • Richard Brewster
  • Tomás Feder
  • Pavol Hell
  • Nikola Jedličková

The complexity of the list homomorphism problem for signed graphs appears difficult to classify. Existing results focus on special classes of signed graphs, such as trees [4] and reflexive signed graphs [25]. Irreflexive signed graphs are in a certain sense the heart of the problem, as noted by a recent paper of Kim and Siggers. We focus on a special class of irreflexive signed graphs, namely those in which the unicoloured edges form a spanning path or cycle, which we call separable signed graphs. We classify the complexity of list homomorphisms to these separable signed graphs; we believe that these signed graphs will play an important role for the general resolution of the irreflexive case. We also relate our results to a conjecture of Kim and Siggers concerning the special case of semi-balanced irreflexive signed graphs; we have proved the conjecture in another paper, and the present results add structural information to that topic.

Details DOI

MFCS Conference 2020 Conference Paper

List Homomorphism Problems for Signed Graphs

  • Jan Bok
  • Richard C. Brewster
  • Tomás Feder
  • Pavol Hell
  • Nikola Jedlicková

We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph (G, σ), equipped with lists L(v) ⊆ V(H), v ∈ V(G), of allowed images, to a fixed target signed graph (H, π). The complexity of the similar homomorphism problem without lists (corresponding to all lists being L(v) = V(H)) has been previously classified by Brewster and Siggers, but the list version remains open and appears difficult. Both versions (with lists or without lists) can be formulated as constraint satisfaction problems, and hence enjoy the algebraic dichotomy classification recently verified by Bulatov and Zhuk. By contrast, we seek a combinatorial classification for the list version, akin to the combinatorial classification for the version without lists completed by Brewster and Siggers. We illustrate the possible complications by classifying the complexity of the list homomorphism problem when H is a (reflexive or irreflexive) signed tree. It turns out that the problems are polynomial-time solvable for certain caterpillar-like trees, and are NP-complete otherwise. The tools we develop will be useful for classifications of other classes of signed graphs, and we mention some follow-up research of this kind; those classifications are surprisingly complex.

Details

MFCS Conference 2018 Conference Paper

Interval-Like Graphs and Digraphs

  • Pavol Hell
  • Jing Huang 0007
  • Ross M. McConnell
  • Arash Rafiey

We unify several seemingly different graph and digraph classes under one umbrella. These classes are all, broadly speaking, different generalizations of interval graphs, and include, in addition to interval graphs, adjusted interval digraphs, threshold graphs, complements of threshold tolerance graphs (known as `co-TT' graphs), bipartite interval containment graphs, bipartite co-circular arc graphs, and two-directional orthogonal ray graphs. (The last three classes coincide, but have been investigated in different contexts.) This common view is made possible by introducing reflexive relationships (loops) into the analysis. We also show that all the above classes are united by a common ordering characterization, the existence of a min ordering. We propose a common generalization of all these graph and digraph classes, namely signed-interval digraphs, and show that they are precisely the digraphs that are characterized by the existence of a min ordering. We also offer an alternative geometric characterization of these digraphs. For most of the above graph and digraph classes, we show that they are exactly those signed-interval digraphs that satisfy a suitable natural restriction on the digraph, like having a loop on every vertex, or having a symmetric edge-set, or being bipartite. For instance, co-TT graphs are precisely those signed-interval digraphs that have each edge symmetric. We also offer some discussion of future work on recognition algorithms and characterizations.

Details

TCS Journal 2015 Journal Article

Influence diffusion in social networks under time window constraints

  • Luisa Gargano
  • Pavol Hell
  • Joseph G. Peters
  • Ugo Vaccaro

We study a combinatorial model of the spread of influence in networks that generalizes existing schemata recently proposed in the literature. In our model, agents change behaviours/opinions on the basis of information collected from their neighbours in a time interval of bounded size whereas agents are assumed to have unbounded memory in previously studied scenarios. In our mathematical framework, one is given a network G = ( V, E ), an integer value t ( v ) for each node v ∈ V, and a time window size λ. The goal is to determine a small set of nodes (target set) that influences the whole graph. The spread of influence proceeds in rounds as follows: initially all nodes in the target set are influenced; subsequently, in each round, any uninfluenced node v becomes influenced if the number of its neighbours that have been influenced in the previous λ rounds is greater than or equal to t ( v ). We prove that the problem of finding a minimum cardinality target set that influences the whole network G is hard to approximate within a polylogarithmic factor. On the positive side, we design exact polynomial time algorithms for paths, rings, and trees.

Details DOI

TCS Journal 2014 Journal Article

H-coloring degree-bounded (acyclic) digraphs

  • Pavol Hell
  • Aurosish Mishra

An NP-complete coloring or homomorphism problem may become polynomial time solvable when restricted to graphs with degrees bounded by a small number, but remain NP-complete if the bound is higher. We investigate an analogous phenomenon for digraphs, focusing on the three smallest digraphs H with NP-complete H-colorability problems. It turns out that in all three cases the H-coloring problem is polynomial time solvable for digraphs with in-degrees at most 1, regardless of the out-degree bound (respectively with out-degrees at most 1, regardless of the in-degree bound). On the other hand, as soon as both in- and out-degrees are bounded by constants greater than or equal to 2, all three problems are again NP-complete. Interestingly, the situation changes when we further restrict the inputs to be acyclic digraphs. In two of the three cases the NP-complete problems remain NP-complete. In the third case, the H-coloring problem turns out to be polynomial time solvable for acyclic digraphs with in-degrees at most 2, regardless of the out-degree bound (respectively with out-degrees at most 2, regardless of the in-degree bound). We also show that in this case as soon as both in- and out-degrees are bounded by constants greater than or equal to 3, the H-coloring problem is once again NP-complete, even for acyclic digraphs. A conjecture proposed for graphs H by Feder, Hell and Huang states that any variant of the H-coloring problem which is NP-complete without degree constraints is also NP-complete with degree constraints, provided the degree bounds are high enough. It has been verified for H-coloring of digraphs, but the degree bounds are quite high, and are stated in terms of the sum of in- and out-degrees. Our results confirm the conjecture with the best possible bounds that are needed for NP-completeness; moreover, they underscore the fact that the bound must apply separately to both the in-degrees and the out-degrees.

Details DOI

SODA Conference 2014 Conference Paper

Space complexity of list H -colouring: a dichotomy

  • László Egri
  • Pavol Hell
  • Benoît Larose
  • Arash Rafiey

The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states that every CSP is in P or is NP-complete (Feder-Vardi, 1993). It has been verified for conservative problems (also known as list homomorphism problems) by Bulatov (2003). We augment this result by showing that for digraph templates H, every conservative CSP, denoted LHOM( H ), is solvable in logspace or is hard for NL. More precisely, we introduce a digraph structure we call a circular N, and prove the following dichotomy: if H contains no circular N then LHOM( H ) admits a logspace algorithm, and otherwise LHOM( H ) is hard for NL. Our algorithm operates by reducing the lists in a complex manner based on a novel decomposition of an auxiliary digraph, combined with repeated applications of Reingold's algorithm for undirected reachability (2005). We also prove an algebraic version of this dichotomy: the digraphs without a circular N are precisely those that admit a finite chain of conservative polymorphisms satisfying the Hagemann-Mitschke identities. This confirms a conjecture of Larose and Tesson (2007) for LHOM( H ). Moreover, we show that the presence of a circular N can be decided in time polynomial in the size of H.

Details

TCS Journal 2005 Journal Article

List matrix partitions of chordal graphs

  • Tomás Feder
  • Pavol Hell
  • Sulamita Klein
  • Loana Tito Nogueira
  • Fábio Protti

It is well known that a clique with k + 1 vertices is the only minimal obstruction to k -colourability of chordal graphs. A similar result is known for the existence of a cover by ℓ cliques. Both of these problems are in fact partition problems, restricted to chordal graphs. The first seeks partitions into k independent sets, and the second is equivalent to finding partitions into ℓ cliques. In an earlier paper we proved that a chordal graph can be partitioned into k independent sets and ℓ cliques if and only if it does not contain an induced disjoint union of ℓ + 1 cliques of size k + 1. (A linear time algorithm for finding such partitions can be derived from the proof.) In this paper we expand our focus and consider more general partitions of chordal graphs. For each symmetric matrix M over 0, 1, *, the M -partition problem seeks a partition of the input graph into independent sets, cliques, or arbitrary sets, with certain pairs of sets being required to have no edges, or to have all edges joining them, as encoded in the matrix M. Moreover, the vertices of the input chordal graph can be equipped with lists, restricting the parts to which a vertex can be placed. Such (list) partitions generalize (list) colourings and (list) homomorphisms, and arise frequently in the theory of graph perfection. We show that many M -partition problems that are NP-complete in general become solvable in polynomial time for chordal graphs, even in the presence of lists. On the other hand, we show that there are M -partition problems (without lists) that remain NP-complete for chordal graphs. It is not known whether or not each list M -partition problem is NP-complete or polynomial, but it has been shown that each is NP-complete or quasi-polynomial ( n O ( log n ) ). For chordal graphs even this ‘quasi-dichotomy’ is not known, but we do identify large families of matrices M for which dichotomy, or at least quasi-dichotomy, holds. We also discuss forbidden subgraph characterizations of graphs admitting an M -partition. Such characterizations have recently been investigated for partitions of perfect graphs, and we focus on highlighting the improvements one can obtain for the class of chordal, rather than just perfect, graphs.

Details DOI