Search

Abstract: Let G = ( V , E ) be a finite, simple, and connected graph. The closed interval I [ S ] of a set S ⊆ V is the set of all vertices lying on a shortest path between any pair of vertices of S. The set S is geodetic if I [ S ] = V. The eccentricity of a vertex v is the number of edges in the greatest shortest path between v and any vertex w of G. A vertex v is a contour vertex if no neighbor of v has eccentricity greater than v. The contour C t ( G ) of G is the set formed by the contour vertices of G. We consider two problems: ( a ) the problem of determining whether the contour of a graph class is geodetic; ( b ) the problem of determining if there exists a graph such that I [ C t ( G ) ] is not geodetic. We obtain a sufficient condition that is useful for both problems; we prove a realization theorem related to problem ( a ) and show two infinite families such that C t ( G ) is not geodetic. Using computational tools, we establish the minimum graphs for which C t ( G ) is not geodetic; and show that all graphs with | V | < 13, and all bipartite graphs with | V | < 18, are such that I [ C t ( G ) ] is geodetic. [ABSTRACT FROM AUTHOR]

The Π graph sandwich problem asks, for a pair of graphs G 1 = ( V , E 1 ) and G 2 = ( V , E 2 ) with E 1 ⊆ E 2 , whether there exists a graph G = ( V , E ) that satisfies property Π and E 1 ⊆ E ⊆ E 2 . We consider the property of being F -free, where F is a fixed graph. We show that the claw-free graph sandwich and the bull-free graph sandwich problems are both NP-complete, but the paw-free graph sandwich problem is polynomial. This completes the study of all cases where F has at most four vertices. A skew partition of a graph G is a partition of its vertex set into four nonempty parts A , B , C , D such that each vertex of A is adjacent to each vertex of B , and each vertex of C is nonadjacent to each vertex of D . We prove that the skew partition sandwich problem is NP-complete, establishing a computational complexity non-monotonicity. [ABSTRACT FROM AUTHOR]

Abstract: A generalized split partition is a vertex set partition into at most k independent sets and l cliques. We prove that the (2, 1) partitioned probe problem is in P whereas the (2, 2) partitioned probe is NP-complete. The full complexity dichotomy into polynomial time and NP-complete for the class of generalized split partitioned probe problems establishes (2, 2) as the first NP-complete self-complementary partitioned probe problem, and answers negatively the PGC conjecture by finding a polynomial time recognition problem whose partitioned probe version is NP-complete. [Copyright &y& Elsevier]

Abstract: 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 -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 -partition problem to several external constraint 4 nonempty part sandwich problems, defining a class of -hard problems. Finally, we discuss the complexity of the Skew Partition Sandwich Problem. [Copyright &y& Elsevier]

Abstract: We classify into polynomial time or -complete all three nonempty part sandwich problems. This solves the polynomial dichotomy into polynomial time and -complete for this class of graph partition problems. [Copyright &y& Elsevier]

Abstract: A graph is -partitionable if its vertex set can be partitioned into four nonempty parts , , , such that each vertex of is adjacent to each vertex of , and each vertex of is adjacent to each vertex of . Determining whether an arbitrary graph is -partitionable is the only vertex-set partition problem into four nonempty parts according to external constraints whose computational complexity is open. We establish that the -partition problem parameterized by minimum degree is fixed-parameter tractable. We also show that for -free graphs, circular-arc graphs, spiders, -sparse graphs, and bipartite graphs the -partition problem can be solved in polynomial time. [Copyright &y& Elsevier]

Abstract: The -sparse Graph Sandwich Problem asks, given two graphs and , whether there exists a graph such that and is -sparse. In this paper we present a polynomial-time algorithm for solving the Graph Sandwich Problem for -sparse graphs. [Copyright &y& Elsevier]

Abstract: A graph is 2K 2-partitionable if its vertex set can be partitioned into four nonempty parts A, B, C, D such that each vertex of A is adjacent to each vertex of B, and each vertex of C is adjacent to each vertex of D. Determining whether an arbitrary graph is 2K 2-partitionable is the only vertex-set partition problem into four nonempty parts according to external constraints whose computational complexity is open. We show that for C 4-free graphs, circular-arc graphs, spiders, P 4-sparse graphs, and bipartite graphs the 2K 2-partition problem can be solved in polynomial time. [Copyright &y& Elsevier]

Abstract: We classify into polynomial time or NP-complete all three nonempty part sandwich problems. This solves the polynomial dichotomy for this class of problems. [Copyright &y& Elsevier]

A graph G is (k,l) if its vertex set can be partitioned into at most k independent sets and l cliques. The (k,l)-Graph Sandwich Problem asks, given two graphs G1=(V,E1) and G2=(V,E2), whether there exists a graph G=(V,E) such that E1⊆E⊆E2 and G is (k,l). In this paper, we prove that the (k,l)-Graph Sandwich Problem is NP-complete for the cases k=1 and l=2; k=2 and l=1; or k=l=2. This completely classifies the complexity of the (k,l)-Graph Sandwich Problem as follows: the problem is NP-complete, if k+l>2; the problem is polynomial otherwise. We consider the degree Δ constraint subproblem and completely classify the problem as follows: the problem is polynomial, for k⩽2 or Δ⩽3; the problem is NP-complete otherwise. In addition, we propose two optimization versions of graph sandwich problem for a property Π: MAX-Π-GSP and MIN-Π-GSP. We prove that MIN-(2,1)-GSP is a Max-SNP-hard problem, i.e., there is a positive constant #x03B5;, such that the existence of an #x03B5;-approximative algorithm for MIN-(2,1)-GSP implies P=NP. [Copyright &y& Elsevier]