
Carbonnel, C., Romero, M., & Zivny, S. (2022). The Complexity of GeneralValued Constraint Satisfaction Problems Seen from the Other Side. SIAM J. Comput., 51(1), 19–69.
Abstract: The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted lefthandside structures, the results of Dalmau, Languages and Programming, Springer, New York, 2007, pp. 279290] establish the precise borderline of polynomialtime solvability (subject to complexitytheoretic assumptions) and of solvability by boundedconsistency algorithms (unconditionally) as bounded treewidth modulo homomorphic equivalence. The generalvalued constraint satisfaction problem (VCSP) is a generalization of the CSP concerned with homomorphisms between two valued structures. For VCSPs with restricted lefthandside valued structures, we establish the precise borderline of polynomialtime solvability (subject to complexitytheoretic assumptions) and of solvability by the kth level of the SheraliAdams LP hierarchy (unconditionally). We also obtain results on related problems concerned with finding a solution and recognizing the tractable cases; the latter has an application in database theory.



Kosowski, A., Li, B., Nisse, N., & Suchan, K. (2015). kChordal Graphs: From Cops and Robber to Compact Routing via Treewidth. Algorithmica, 72(3), 758–777.
Abstract: Cops and robber games, introduced by Winkler and Nowakowski (in Discrete Math. 43(23), 235239, 1983) and independently defined by Quilliot (in J. Comb. Theory, Ser. B 38(1), 8992, 1985), concern a team of cops that must capture a robber moving in a graph. We consider the class of kchordal graphs, i.e., graphs with no induced (chordless) cycle of length greater than k, ka parts per thousand yen3. We prove that k1 cops are always sufficient to capture a robber in kchordal graphs. This leads us to our main result, a new structural decomposition for a graph class including kchordal graphs. We present a polynomialtime algorithm that, given a graph G and ka parts per thousand yen3, either returns an induced cycle larger than k in G, or computes a treedecomposition of G, each bag of which contains a dominating path with at most k1 vertices. This allows us to prove that any kchordal graph with maximum degree Delta has treewidth at most (k1)(Delta1)+2, improving the O(Delta(Delta1) (k3)) bound of Bodlaender and Thilikos (Discrete Appl. Math. 79(13), 4561, 1997. Moreover, any graph admitting such a treedecomposition has small hyperbolicity). As an application, for any nvertex graph admitting such a treedecomposition, we propose a compact routing scheme using routing tables, addresses and headers of size O(klog Delta+logn) bits and achieving an additive stretch of O(klog Delta). As far as we know, this is the first routing scheme with O(klog Delta+logn)routing tables and small additive stretch for kchordal graphs.



Li, B., Moataz, F. Z., Nisse, N., & Suchan, K. (2018). Minimum size treedecompositions. Discret Appl. Math., 245, 109–127.
Abstract: We study in this paper the problem of computing a treedecomposition of a graph with width at most k and minimum number of bags. More precisely, we focus on the following problem: given a fixed k >= 1, what is the complexity of computing a treedecomposition of width at most k with minimum number of bags in the class of graphs with treewidth at most k? We prove that the problem is NPcomplete for any fixed k >= 4 and polynomial for k <= 2; for k = 3, we show that it is polynomial in the class of trees and 2connected outerplanar graphs. (C) 2017 Elsevier B.V. All rights reserved.



Liedloff, M., Montealegre, P., & Todinca, I. (2019). Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques. Algorithmica, 81(3), 986–1005.
Abstract: Let P(G,X) be a property associating a boolean value to each pair (G,X) where G is a graph and X is a vertex subset. Assume that P is expressible in counting monadic second order logic (CMSO) and let t be an integer constant. We consider the following optimization problem: given an input graph G=(V,E), find subsets XFV such that the treewidth of G[F] is at most t, property P(G[F],X) is true and X is of maximum size under these conditions. The problem generalizes many classical algorithmic questions, e.g., Longest Induced Path, Maximum Induced Forest, IndependentHPacking, etc. Fomin et al. (SIAM J Comput 44(1):5487, 2015) proved that the problem is polynomial on the class of graph Gpoly, i.e. the graphs having at most poly(n) minimal separators for some polynomial poly. Here we consider the class Gpoly+kv, formed by graphs of Gpoly to which we add a set of at most k vertices with arbitrary adjacencies, called modulator. We prove that the generic optimization problem is fixed parameter tractable on Gpoly+kv, with parameter k, if the modulator is also part of the input.

