The Complexity of Surjective Homomorphism Problems -- a Survey
---
paper_title: Computing Role Assignments of Chordal Graphs

paper_content:

In social network theory, a simple graph G is called k-role assignable if there is a surjective mapping that assigns a number from {1,...,k} called a role to each vertex of G such that any two vertices with the same role have the same sets of roles assigned to their neighbors. The decision problem whether such a mapping exists is called the k-ROLE ASSIGNMENT problem. This problem is known to be NP-complete for any fixed k ≥ 2. In this paper we classify the computational complexity of the k-Role Assignment problem for the class of chordal graphs. We show that for this class the problem becomes polynomially solvable for k = 2, but remains NP-complete for any k ≥ 3. This generalizes results of Sheng and answers his open problem.
---
paper_title: The stubborn problem is stubborn no more: a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem

paper_content:

One of the driving problems in the CSP area is the Dichotomy Conjecture, formulated in 1993 by Feder and Vardi [STOC'93], stating that for any fixed relational structure G the Constraint Satisfaction Problem CSP(G) is either NP--complete or polynomial time solvable. A large amount of research has gone into checking various specific cases of this conjecture. One such variant which attracted a lot of attention in the recent years is the LIST MATRIX PARTITION problem. In 2004 Cameron et al. [SODA'04] classified almost all LIST MATRIX PARTITION variants for matrices of size at most four. The only case which resisted the classification became known as the STUBBORN PROBLEM. In this paper we show a result which enables us to finish the classification - thus solving a problem which resisted attacks for the last six years. Our approach is based on a combinatorial problem known to be at least as hard as the STUBBORN PROBLEM - the 3-COMPATIBLE COLOURING problem. In this problem we are given a complete graph with each edge assigned one of 3 possible colours and we want to assign one of those 3 colours to each vertex in such a way that no edge has the same colour as both of its endpoints. The tractability of the 3-COMPATIBLE COLOURING problem has been open for several years and the best known algorithm prior to this paper is due to Feder et al. [SODA'05] - a quasipolynomial algorithm with a n^O(log n / log log n) time complexity. In this paper we present a polynomial-time algorithm for the 3-COMPATIBLE COLOURING problem and consequently we prove a dichotomy for the k-COMPATIBLE COLOURING problem.
---
paper_title: The Complexity of the List Partition Problem for Graphs

paper_content:

The $k$-partition problem is as follows: Given a graph $G$ and a positive integer $k$, partition the vertices of $G$ into at most $k$ parts $A_1, A_2, \ldots , A_k$, where it may be specified that $A_i$ induces a stable set, a clique, or an arbitrary subgraph, and pairs $A_i, A_j (i \neq j)$ be completely nonadjacent, completely adjacent, or arbitrarily adjacent. The list $k$-partition problem generalizes the $k$-partition problem by specifying for each vertex $x$, a list $L(x)$ of parts in which it is allowed to be placed. Many well-known graph problems can be formulated as list $k$-partition problems: e.g., 3-colorability, clique cutset, stable cutset, homogeneous set, skew partition, and 2-clique cutset. We classify, with the exception of two polynomially equivalent problems, each list 4-partition problem as either solvable in polynomial time or NP-complete. In doing so, we provide polynomial-time algorithms for many problems whose polynomial-time solvability was open, including the list 2-clique cutset problem. This also allows us to classify each list generalized 2-clique cutset problem and list generalized skew partition problem as solvable in polynomial time or NP-complete.
---
paper_title: List Partitions

paper_content:

List partitions generalize list colorings and list homomorphisms. (We argue that they may be called list "semihomomorphisms.") Each symmetric matrix M over 0,1,* defines a list partition problem. Different choices of the matrix M lead to many well-known graph theoretic problems, often related to graph perfection, including the problem of recognizing split graphs, finding homogeneous sets, clique cutsets, stable cutsets, and so on. The recent proof of the strong perfect graph theorem employs three kinds of decompositions that can be viewed as list partitions. ::: We develop tools which allow us to classify the complexity of many list partition problems and, in particular, yield the complete classification for small matrices M. Along the way, we obtain a variety of specific results, including generalizations of Lovasz's communication bound on the number of clique-versus-stable-set separators, polynomial time algorithms to recognize generalized split graphs, a polynomial algorithm for the list version of the clique cutset problem, and the first subexponential algorithm for the skew cutset problem of Chvatal. We also show that the dichotomy (NP-complete versus polynomial time solvable), conjectured for certain graph homomorphism problems, would, if true, imply a slightly weaker dichotomy (NP-complete versus quasi-polynomial) for our list partition problems.
---
paper_title: A complete complexity classification of the role assignment problem

paper_content:

In social network theory a society is often represented by a simple graph G, where vertices stand for individuals and edges represent relationships between those individuals. The description of the social network is tried to be simplified by assigning roles to the individuals, such that the neighborhood relation is preserved. Formally, for a fixed graph R we ask for a vertex mapping r: VG → VR, such that r(NG(u)) = NR(r(u)) for all u ∈ VG.If such a mapping exists the graph G is called R-role assignable and the corresponding decision problem is called the R-role assignment problem. Kristiansen and Telle conjectured that the R-role assignment problem is an NP-complete problem for any simple connected graph R on at least three vertices. In this paper we prove their conjecture. In addition, we determine the computational complexity of the role assignment problem for nonsimple and disconnected role graphs, as these are considered in social network theory as well.
---
paper_title: Tractable conservative constraint satisfaction problems

paper_content:

In a constraint satisfaction problem (CSP), the aim is to find an assignment of values to a given set of variables, subject to specified constraints. The CSP is known to be NP-complete in general. However, certain restrictions on the form of the allowed constraints can lead to problems solvable in polynomial time. Such restrictions are usually imposed by specifying a constraint language. The principal research direction aims to distinguish those constraint languages, which give rise to tractable CSPs from those which do not. We achieve this goal for the widely used variant of the CSP, in which the set of values for each individual variable can be restricted arbitrarily. Restrictions of this type can be expressed by including in a constraint language all possible unary constraints. Constraint languages containing all unary constraints will be called conservative. We completely characterize conservative constraint languages that give rise to CSP classes solvable in polynomial time. In particular, this result allows us to obtain a complete description of those (directed) graphs H for which the List H-Coloring problem is polynomial time solvable.
---
paper_title: Tractable cases of the extended global cardinality constraint

paper_content:

We study the consistency and domain consistency problem for extended global cardinality (EGC) constraints. An EGC constraint consists of a set X of variables, a set D of values, a domain $D(x) \subseteq D$ for each variable x, and a "cardinality set" K(d) of non-negative integers for each value d. The problem is to instantiate each variable x with a value in D(x) such that for each value d, the number of variables instantiated with d belongs to the cardinality set K(d). It is known that this problem is NP-complete in general, but solvable in polynomial time if all cardinality sets are intervals. First we pinpoint connections between EGC constraints and general factors in graphs. This allows us to extend the known polynomial-time case to certain non-interval cardinality sets. Second we consider EGC constraints under restrictions in terms of the treewidth of the value graph (the bipartite graph representing variable-value pairs) and the cardinality-width (the largest integer occurring in the cardinality sets). We show that EGC constraints can be solved in polynomial time for instances of bounded treewidth, where the order of the polynomial depends on the treewidth. We show that (subject to the complexity theoretic assumption FPT???W[1]) this dependency cannot be avoided without imposing additional restrictions. If, however, also the cardinality-width is bounded, this dependency gets removed and EGC constraints can be solved in linear time.
---
paper_title: On the Algebraic Structure of Combinatorial Problems

paper_content:

Abstract We describe a general algebraic formulation for a wide range of combinatorial problems including Satisfiability, Graph Colorability and Graph Isomorphism In this formulation each problem instance is represented by a pair of relational structures, and the solutions to a given instance are homomorphisms between these relational structures. The corresponding decision problem consists of deciding whether or not any such homomorphisms exist. We then demonstrate that the complexity of solving this decision problem is determined in many cases by simple algebraic properties of the relational structures involved. This result is used to identify tractable subproblems of Satisfiability , and to provide a simple test to establish whether a given set of Boolean relations gives rise to one of these tractable subproblems.
---
paper_title: The Complexity of Rooted Phylogeny Problems

paper_content:

Several computational problems in phylogenetic reconstruction can be formulated as restrictions of the following general problem: given a formula in conjunctive normal form where the literals are rooted triples, is there a rooted binary tree that satisfies the formula? If the formulas do not contain disjunctions, the problem becomes the famous rooted triple consistency problem, which can be solved in polynomial time by an algorithm of Aho, Sagiv, Szymanski, and Ullman. If the clauses in the formulas are restricted to disjunctions of negated triples, Ng, Steel, and Wormald showed that the problem remains NP-complete. We systematically study the computational complexity of the problem for all such restrictions of the clauses in the input formula. For certain restricted disjunctions of triples we present an algorithm that has sub-quadratic running time and is asymptotically as fast as the fastest known algorithm for the rooted triple consistency problem. We also show that any restriction of the general rooted phylogeny problem that does not fall into our tractable class is NP-complete, using known results about the complexity of Boolean constraint satisfaction problems. Finally, we present a pebble game argument that shows that the rooted triple consistency problem (and also all generalizations studied in this paper) cannot be solved by Datalog.
---
paper_title: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory

paper_content:

This paper starts with the project of finding a large subclass of NP which exhibits a dichotomy. The approach is to find this subclass via syntactic prescriptions. While the paper does not achieve this goal, it does isolate a class (of problems specified by) "monotone monadic SNP without inequality" which may exhibit this dichotomy. We justify the placing of all these restrictions by showing, essentially using Ladner's theorem, that classes obtained by using only two of the above three restrictions do not show this dichotomy. We then explore the structure of this class. We show that all problems in this class reduce to the seemingly simpler class CSP. We divide CSP into subclasses and try to unify the collection of all known polytime algorithms for CSP problems and extract properties that make CSP problems NP-hard. This is where the second part of the title, "a study through Datalog and group theory," comes in. We present conjectures about this class which would end in showing the dichotomy.
---
paper_title: CLASSIFYING THE COMPLEXITY OF CONSTRAINTS USING FINITE ALGEBRAS∗

paper_content:

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. Here we show that any set of relations used to specify the allowed forms of constraints can be associated with a finite universal algebra and we explore how the computational complexity of the corresponding constraint satisfaction problem is connected to the properties of this algebra. Hence, we completely translate the problem of classifying the complexity of restricted constraint satisfaction problems into the language of universal algebra. ::: We introduce a notion of "tractable algebra," and investigate how the tractability of an algebra relates to the tractability of the smaller algebras which may be derived from it, including its subalgebras and homomorphic images. This allows us to reduce significantly the types of algebras which need to be classified. Using our results we also show that if the decision problem associated with a given collection of constraint types can be solved efficiently, then so can the corresponding search problem. We then classify all finite strictly simple surjective algebras with respect to tractability, obtaining a dichotomy theorem which generalizes Schaefer's dichotomy for the generalized satisfiability problem. Finally, we suggest a possible general algebraic criterion for distinguishing the tractable and intractable cases of the constraint satisfaction problem.
---
paper_title: Tractable conservative constraint satisfaction problems

paper_content:

In a constraint satisfaction problem (CSP), the aim is to find an assignment of values to a given set of variables, subject to specified constraints. The CSP is known to be NP-complete in general. However, certain restrictions on the form of the allowed constraints can lead to problems solvable in polynomial time. Such restrictions are usually imposed by specifying a constraint language. The principal research direction aims to distinguish those constraint languages, which give rise to tractable CSPs from those which do not. We achieve this goal for the widely used variant of the CSP, in which the set of values for each individual variable can be restricted arbitrarily. Restrictions of this type can be expressed by including in a constraint language all possible unary constraints. Constraint languages containing all unary constraints will be called conservative. We completely characterize conservative constraint languages that give rise to CSP classes solvable in polynomial time. In particular, this result allows us to obtain a complete description of those (directed) graphs H for which the List H-Coloring problem is polynomial time solvable.
---
paper_title: Complexity Classifications of Boolean Constraint Satisfaction Problems

paper_content:

Preface 1. Introduction 2. Complexity Classes 3. Boolean Constraint Satisfaction Problems 4. Characterizations of Constraint Functions 5. Implementation of Functions and Reductions 6. Classification Theorems for Decision, Counting and Quantified Problems 7. Classification Theorems for Optimization Problems 8. Input-Restricted Constrained Satisfaction Problems 9. The Complexity of the Meta-Problems 10. Concluding Remarks Bibliography Index.
---
paper_title: List Homomorphisms and Circular Arc Graphs

paper_content:

, H, and lists \(\), a list homomorphism of G to Hwith respect to the listsL is a mapping \(\), such that \(\) for all \(\), and \(\) for all \(\). The list homomorphism problem for a fixed graph H asks whether or not an input graph G together with lists \(\), \(\), admits a list homomorphism with respect to L. We have introduced the list homomorphism problem in an earlier paper, and proved there that for reflexive graphs H (that is, for graphs H in which every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP-complete otherwise. Here we consider graphs H without loops, and find that the problem is closely related to circular arc graphs. We show that the list homomorphism problem is polynomial time solvable if the complement of H is a circular arc graph of clique covering number two, and is NP-complete otherwise. For the purposes of the proof we give a new characterization of circular arc graphs of clique covering number two, by the absence of a structure analogous to Gallai's asteroids. Both results point to a surprising similarity between interval graphs and the complements of circular arc graphs of clique covering number two.
---
paper_title: RETRACTIONS TO PSEUDOFORESTS

paper_content:

For a fixed graph $H$, let $\textsc{Ret}(H)$ denote the problem of deciding whether a given input graph is retractable to $H$. We classify the complexity of $\textsc{Ret}(H)$ when $H$ is a graph (with loops allowed) where each connected component has at most one cycle, i.e., a pseudoforest. In particular, this result extends the known complexity classifications of $\textsc{Ret}(H)$ for reflexive and irreflexive cycles to general cycles. Our approach is based mainly on algebraic techniques from universal algebra that previously have been used for analyzing the complexity of constraint satisfaction problems.
---
paper_title: Compaction, Retraction, and Constraint Satisfaction

paper_content:

In this paper, we show a very close relationship among the compaction, retraction, and constraint satisfaction problems in the context of reflexive and bipartite graphs. The compaction and retraction problems are special graph coloring problems, and the constraint satisfaction problem is well known to have an important role in artificial intelligence. The relationships we present provide evidence that, similar to %as for the retraction problem, it is likely to be difficult to determine whether for every fixed reflexive or bipartite graph, the compaction problem is polynomial time solvable or NP-complete. In particular, the relationships that we present relate to a long-standing open problem concerning the equivalence of the compaction and retraction problems.
---
paper_title: Undirected connectivity in log-space

paper_content:

We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log4/3(ṡ) obtained by Armoni, Ta-Shma, Wigderson and Zhou (JACM 2000). As undirected st-connectivity is complete for the class of problems solvable by symmetric, nondeterministic, log-space computations (the class SL), this algorithm implies that SL = L (where L is the class of problems solvable by deterministic log-space computations). Independent of our work (and using different techniques), Trifonov (STOC 2005) has presented an O(log n log log n)-space, deterministic algorithm for undirected st-connectivity. ::: Our algorithm also implies a way to construct in log-space a fixed sequence of directions that guides a deterministic walk through all of the vertices of any connected graph. Specifically, we give log-space constructible universal-traversal sequences for graphs with restricted labeling and log-space constructible universal-exploration sequences for general graphs.
---
paper_title: CLASSIFYING THE COMPLEXITY OF CONSTRAINTS USING FINITE ALGEBRAS∗

paper_content:

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. Here we show that any set of relations used to specify the allowed forms of constraints can be associated with a finite universal algebra and we explore how the computational complexity of the corresponding constraint satisfaction problem is connected to the properties of this algebra. Hence, we completely translate the problem of classifying the complexity of restricted constraint satisfaction problems into the language of universal algebra. ::: We introduce a notion of "tractable algebra," and investigate how the tractability of an algebra relates to the tractability of the smaller algebras which may be derived from it, including its subalgebras and homomorphic images. This allows us to reduce significantly the types of algebras which need to be classified. Using our results we also show that if the decision problem associated with a given collection of constraint types can be solved efficiently, then so can the corresponding search problem. We then classify all finite strictly simple surjective algebras with respect to tractability, obtaining a dichotomy theorem which generalizes Schaefer's dichotomy for the generalized satisfiability problem. Finally, we suggest a possible general algebraic criterion for distinguishing the tractable and intractable cases of the constraint satisfaction problem.
---
paper_title: The complexity of colouring by semicomplete digraphs

paper_content:

The following problem, known as the H-colouring problem, is studied. An H-colouring of a directed graph D is a mapping $f:V( D ) \to V( H )$ such that $( f( x ),f( y ) )$ is an edge of H whenever $( x,y )$ is an edge of D. The H-colouring problem is the following. Instance: A directed graph D. Question: Does there exist an H-colouring of D? In this paper it is shown that for semicomplete digraphs T the T-colouring problem is NP-complete when T has more than one directed cycle, and polynomially decidable otherwise.
---
paper_title: Compaction, Retraction, and Constraint Satisfaction

paper_content:

In this paper, we show a very close relationship among the compaction, retraction, and constraint satisfaction problems in the context of reflexive and bipartite graphs. The compaction and retraction problems are special graph coloring problems, and the constraint satisfaction problem is well known to have an important role in artificial intelligence. The relationships we present provide evidence that, similar to %as for the retraction problem, it is likely to be difficult to determine whether for every fixed reflexive or bipartite graph, the compaction problem is polynomial time solvable or NP-complete. In particular, the relationships that we present relate to a long-standing open problem concerning the equivalence of the compaction and retraction problems.
---
paper_title: Tractable conservative constraint satisfaction problems

paper_content:

In a constraint satisfaction problem (CSP), the aim is to find an assignment of values to a given set of variables, subject to specified constraints. The CSP is known to be NP-complete in general. However, certain restrictions on the form of the allowed constraints can lead to problems solvable in polynomial time. Such restrictions are usually imposed by specifying a constraint language. The principal research direction aims to distinguish those constraint languages, which give rise to tractable CSPs from those which do not. We achieve this goal for the widely used variant of the CSP, in which the set of values for each individual variable can be restricted arbitrarily. Restrictions of this type can be expressed by including in a constraint language all possible unary constraints. Constraint languages containing all unary constraints will be called conservative. We completely characterize conservative constraint languages that give rise to CSP classes solvable in polynomial time. In particular, this result allows us to obtain a complete description of those (directed) graphs H for which the List H-Coloring problem is polynomial time solvable.
---
paper_title: List Homomorphisms and Circular Arc Graphs

paper_content:

, H, and lists \(\), a list homomorphism of G to Hwith respect to the listsL is a mapping \(\), such that \(\) for all \(\), and \(\) for all \(\). The list homomorphism problem for a fixed graph H asks whether or not an input graph G together with lists \(\), \(\), admits a list homomorphism with respect to L. We have introduced the list homomorphism problem in an earlier paper, and proved there that for reflexive graphs H (that is, for graphs H in which every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP-complete otherwise. Here we consider graphs H without loops, and find that the problem is closely related to circular arc graphs. We show that the list homomorphism problem is polynomial time solvable if the complement of H is a circular arc graph of clique covering number two, and is NP-complete otherwise. For the purposes of the proof we give a new characterization of circular arc graphs of clique covering number two, by the absence of a structure analogous to Gallai's asteroids. Both results point to a surprising similarity between interval graphs and the complements of circular arc graphs of clique covering number two.
---
paper_title: On disconnected cuts and separators

paper_content:

Abstract For a connected graph G = ( V , E ) , a subset U ⊆ V is called a disconnected cut if U disconnects the graph, and the subgraph induced by U is disconnected as well. A natural condition is to impose that for any u ∈ U , the subgraph induced by ( V ∖ U ) ∪ { u } is connected. In that case, U is called a minimal disconnected cut. We show that the problem of testing whether a graph has a minimal disconnected cut is NP -complete. We also show that the problem of testing whether a graph has a disconnected cut separating two specified vertices, s and t , is NP -complete.
---
paper_title: FINDING H-PARTITIONS EFFICIENTLY ∗

paper_content:

We study the concept of an H-partition of the vertex set of a graph G, which includes all vertex partitioning problems into four parts which we require to be nonempty with only external constraints according to the structure of a model graph H, with the exception of two cases, one that has already been classified as polynomial, and the other one remains unclassified. In the context of more general vertex-partition problems, the problems addressed in this paper have these properties: non-list, 4-part, external constraints only (no internal constraints), each part non-empty. We describe tools that yield for each problem considered in this paper a simple and low complexity polynomial-time algorithm. Mathematics Subject Classification. 05C85, 68R10.
---
paper_title: Covering graphs with few complete bipartite subgraphs

paper_content:

We consider computational problems on covering graphs with bicliques (complete bipartite subgraphs). Given a graph and an integer k, the biclique cover problem asks whether the edge-set of the graph can be covered with at most k bicliques; the biclique partition problem is defined similarly with the additional condition that the bicliques are required to be mutually edge-disjoint. The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most k bicliques, the biclique vertex-partition problem is defined similarly with the additional condition that the bicliques are required to be mutually vertex-disjoint. All these four problems are known to be NP-complete even if the given graph is bipartite. In this paper, we investigate them in the framework of parameterized complexity: do the problems become easier if k is assumed to be small? We show that, considering k as the parameter, the first two problems are fixed-parameter tractable, while the latter two problems are not fixed-parameter tractable unless P=NP.
---
paper_title: The external constraint 4 nonempty part sandwich problem

paper_content:

List partitions generalize list colourings. Sandwich problems generalize recognition problems. The polynomial dichotomy (NP-complete versus polynomial) of list partition problems is solved for 4-dimensional partitions with the exception of one problem (the list stubborn problem) for which the complexity is known to be quasipolynomial. Every partition problem for 4 nonempty parts and only external constraints is known to be polynomial with the exception of one problem (the 2K"2-partition problem) for which the complexity of the corresponding list problem is known to be NP-complete. The present paper considers external constraint 4 nonempty part sandwich problems. We extend the tools developed for polynomial solutions of recognition problems obtaining polynomial solutions for most corresponding sandwich versions. We extend the tools developed for NP-complete reductions of sandwich partition problems obtaining the classification into NP-complete for some external constraint 4 nonempty part sandwich problems. On the other hand and additionally, we propose a general strategy for defining polynomial reductions from the 2K"2-partition problem to several external constraint 4 nonempty part sandwich problems, defining a class of 2K"2-hard problems. Finally, we discuss the complexity of the Skew Partition Sandwich Problem.
---
paper_title: Tractable conservative constraint satisfaction problems

paper_content:

In a constraint satisfaction problem (CSP), the aim is to find an assignment of values to a given set of variables, subject to specified constraints. The CSP is known to be NP-complete in general. However, certain restrictions on the form of the allowed constraints can lead to problems solvable in polynomial time. Such restrictions are usually imposed by specifying a constraint language. The principal research direction aims to distinguish those constraint languages, which give rise to tractable CSPs from those which do not. We achieve this goal for the widely used variant of the CSP, in which the set of values for each individual variable can be restricted arbitrarily. Restrictions of this type can be expressed by including in a constraint language all possible unary constraints. Constraint languages containing all unary constraints will be called conservative. We completely characterize conservative constraint languages that give rise to CSP classes solvable in polynomial time. In particular, this result allows us to obtain a complete description of those (directed) graphs H for which the List H-Coloring problem is polynomial time solvable.
---
paper_title: Parameterizing cut sets in a graph by the number of their components

paper_content:

For a connected graph G=(V,E), a subset U?V is a disconnected cut if U disconnects G and the subgraph GU induced by U is disconnected as well. A cut U is a k-cut if GU contains exactly k(?1) components. More specifically, a k-cut U is a (k,?)-cut if V?U induces a subgraph with exactly ?(?2) components. The Disconnected Cut problem is to test whether a graph has a disconnected cut and is known to be NP-complete. The problems k-Cut and (k,?)-Cut are to test whether a graph has a k-cut or (k,?)-cut, respectively. By pinpointing a close relationship to graph contractibility problems we show that (k,?)-Cut is in P for k=1 and any fixed constant ??2, while it is NP-complete for any fixed pair k,??2. We then prove that k-Cut is in P for k=1 and NP-complete for any fixed k?2. On the other hand, for every fixed integer g?0, we present an FPT algorithm that solves (k,?)-Cut on graphs of Euler genus at most g when parameterized by k+?. By modifying this algorithm we can also show that k-Cut is in FPT for this graph class when parameterized by k. Finally, we show that Disconnected Cut is solvable in polynomial time for minor-closed classes of graphs excluding some apex graph.
---
paper_title: The Computational Complexity of Disconnected Cut and 2K2-Partition

paper_content:

For a connected graph G=(V,E), a subset U of V is called a disconnected cut if U disconnects the graph and the subgraph induced by U is disconnected as well. We show that the problem to test whether a graph has a disconnected cut is NP-complete. This problem is polynomially equivalent to the following problems: testing if a graph has a 2K2-partition, testing if a graph allows a vertex-surjective homomorphism to the reflexive 4-cycle and testing if a graph has a spanning subgraph that consists of at most two bicliques. Hence, as an immediate consequence, these three decision problems are NP-complete as well. This settles an open problem frequently posed in each of the four settings.
---
paper_title: Coloring Mixed Hypertrees

paper_content:

A mixed hypergraph is a hypergraph with edges classified as of type 1 or type 2. A vertex coloring is strict if no edge of type 1 is totally multicolored, and no edge of type 2 monochromatic. The chromatic spectrum of a mixed hypergraph is the set of integers k for which there exists a strict coloring using exactly k different colors. A mixed hypertree is a mixed hypergraph in which every hyperedge induces a subtree of the given underlying tree. We prove that mixed hypertrees have continuous spectra (unlike general hypergraphs, whose spectra may contain gaps [cf. Jiang et al.: The chromatic spectrum of mixed hypergraphs, submitted]. We prove that determining the upper chromatic number (the maximum of the spectrum) of mixed hypertrees is NP-hard, and we identify several polynomially solvable classes of instances of the problem.
---
paper_title: A dichotomy theorem for constraint satisfaction problems on a 3-element set

paper_content:

The Constraint Satisfaction Problem (CSP) provides a common framework for many combinatorial problems. The general CSP is known to be NP-complete; however, certain restrictions on a possible form of constraints may affect the complexity and lead to tractable problem classes. There is, therefore, a fundamental research direction, aiming to separate those subclasses of the CSP that are tractable and those which remain NP-complete.Schaefer gave an exhaustive solution of this problem for the CSP on a 2-element domain. In this article, we generalise this result to a classification of the complexity of the CSP on a 3-element domain. The main result states that every subproblem of the CSP is either tractable or NP-complete, and the criterion separating them is that conjectured in Bulatov et al. [2005] and Bulatov and Jeavons [2001b]. We also characterize those subproblems for which standard constraint propagation techniques provide a decision procedure. Finally, we exhibit a polynomial time algorithm which, for a given set of allowed constraints, outputs if this set gives rise to a tractable problem class. To obtain the main result and the algorithm, we extensively use the algebraic technique for the CSP developed in Jeavons [1998b], Bulatov et al.[2005], and Bulatov and Jeavons [2001b].
---
paper_title: Algorithms for partition of some class of graphs under compaction

paper_content:

The compaction problem is to partition the vertices of an input graph G onto the vertices of a fixed target graph H, such that adjacent vertices of G remain adjacent in H, and every vertex and nonloop edge of H is covered by some vertex and edge of G respectively, i.e., the partition is a homomorphism of G onto H (except the loop edges). Various computational complexity results, including both NPcompleteness and polynomial time solvability, have been presented earlier for this problem for various class of target graphs H. In this paper, we pay attention to the input graphs G, and present polynomial time algorithms for the problem for some class of input graphs, keeping the target graph H general as any reflexive or irreflexive graph. Our algorithms also give insight as for which instances of the input graphs, the problem could possibly be NP-complete for certain target graphs. With the help of our results, we are able to further refine the structure of the input graph that would be necessary for the problem to be possibly NP-complete, when the target graph is a cycle. Thus, when the target graph is a cycle, we enhance the class of input graphs for which the problem is polynomial time solvable.
---
paper_title: The approximability of three-valued MAX CSP

paper_content:

In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given domain to the variables so as to maximize the number (or the total weight, for the weighted case) of satisfied constraints. This problem is NP-hard in general, and, therefore, it is natural to study how restricting the allowed types of constraints affects the approximability of the problem. It is known that every Boolean (that is, two-valued) Max CSP problem with a finite set of allowed constraint types is either solvable exactly in polynomial time or else APX-complete (and hence can have no polynomial time approximation scheme unless P=NP. It has been an open problem for several years whether this result can be extended to non-Boolean Max CSP, which is much more difficult to analyze than the Boolean case. In this paper, we make the first step in this direction by establishing this result for Max CSP over a three-element domain. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description uses the well-known algebraic combinatorial property of supermodularity. We also show that every hard three-valued Max CSP problem contains, in a certain specified sense, one of the two basic hard Max CSP problems which are the Maximum k-colourable subgraph problems for k=2,3.
---
paper_title: Complexity Classifications of Boolean Constraint Satisfaction Problems

paper_content:

Preface 1. Introduction 2. Complexity Classes 3. Boolean Constraint Satisfaction Problems 4. Characterizations of Constraint Functions 5. Implementation of Functions and Reductions 6. Classification Theorems for Decision, Counting and Quantified Problems 7. Classification Theorems for Optimization Problems 8. Input-Restricted Constrained Satisfaction Problems 9. The Complexity of the Meta-Problems 10. Concluding Remarks Bibliography Index.
---
paper_title: Approximation for Maximum Surjective Constraint Satisfaction Problems

paper_content:

Maximum surjective constraint satisfaction problems (Max-Sur-CSPs) are computational problems where we are given a set of variables denoting values from a finite domain B and a set of constraints on the variables. A solution to such a problem is a surjective mapping from the set of variables to B such that the number of satisfied constraints is maximized. We study the approximation performance that can be acccchieved by algorithms for these problems, mainly by investigating their relation with Max-CSPs (which are the corresponding problems without the surjectivity requirement). Our work gives a complexity dichotomy for Max-Sur-CSP(B) between PTAS and APX-complete, under the assumption that there is a complexity dichotomy for Max-CSP(B) between PO and APX-complete, which has already been proved on the Boolean domain and 3-element domains.
---

Title: The Complexity of Surjective Homomorphism Problems -- a Survey

Section 1: Introduction
Description 1: Provide an overview of surjective homomorphism problems, their significance, related problems, and the main goals of the survey.

Section 2: Preliminaries
Description 2: Introduce basic concepts, definitions, and notations related to homomorphisms and surjective homomorphisms in mathematics and computer science.

Section 3: Relationship between the problems
Description 3: Explain the interconnections and reductions among different types of homomorphism problems, including surjective homomorphisms, retraction, and compaction.

Section 4: Further simple classifications
Description 4: Discuss specific classifications and reductions that help determine the complexity of various surjective homomorphism problems.

Section 5: Difficulty of a full classification
Description 5: Explore the challenges and reasons why a full complexity classification of surjective homomorphisms is difficult to achieve.

Section 6: A renaissance in foresting
Description 6: Discuss recent advancements and results in the classification of surjective homomorphism problems for specific graph types.

Section 7: Recent work on Sur-Hom(C_Ref)
Description 7: Present recent studies and results on specific surjective homomorphism problems, particularly Sur-Hom(C_Ref).

Section 8: The no-rainbow-colouring problem
Description 8: Introduce and analyze the no-rainbow-colouring problem and its relation to surjective homomorphism problems.

Section 9: Final Remarks
Description 9: Conclude the survey with an overview of ongoing research, open questions, and future directions in the study of surjective homomorphism problems.