Search

The complexity of graph isomorphism (GraphIso) is a famous problem in computer science. For graphs G and H , it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph isomorphism (ListIso) is NP -complete: for each u ∈ V (G) , we are given a list L (u) ⊆ V (H) of possible images of u. After 35 years, we revive the study of this problem and consider which results for GraphIso can be modified to solve ListIso. We prove: 1) Under certain conditions, GI -completeness of a class of graphs implies NP -completeness of ListIso. 2) Several combinatorial algorithms for GraphIso can be modified to solve ListIso : for trees, planar graphs, interval graphs, circle graphs, permutation graphs, and bounded treewidth graphs. 3) ListIso is NP -complete for cubic colored graphs with sizes of color classes bounded by 8 with all lists of size at most 3. [ABSTRACT FROM AUTHOR]

The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph G and a partial representation R′ giving some predrawn chords that represent an induced subgraph of G. The question is whether one can extend R′ to a representation R of the entire graph G, that is, whether one can draw the remaining chords into a partially predrawn representation to obtain a representation of G. Our main result is an O(n3) time algorithm for partial representation extension of circle graphs, where n is the number of vertices. To show this, we describe the structure of all representations of a circle graph using split decomposition. This can be of independent interest. [ABSTRACT FROM AUTHOR]

We study the computational complexity of graph planarization via edge contraction. The problem Contract asks whether there exists a set S of at most k edges that when contracted produces a planar graph. We work with a more general problem called P - RestrictedContract in which S , in addition, is required to satisfy a fixed MSOL formula P ( S , G ) . We give an FPT algorithm in time O ( n 2 f ( k ) ) which solves P - RestrictedContract , where n is number of vertices of the graph and P ( S , G ) is (i) inclusion-closed and (ii) inert contraction-closed (where inert edges are the edges non-incident to any inclusion-minimal solution S ). As a specific example, we can solve the ℓ -subgraph contractibility problem in which the edges of the set S are required to form disjoint connected subgraphs of size at most ℓ . This problem can be solved in time O ( n 2 f ′ ( k , ℓ ) ) using the general algorithm. We also show that for ℓ ≥ 2 the problem is NP -complete. [ABSTRACT FROM AUTHOR]