| 9:30 - 10:15 |
Dieter Kratsch
Convex Recoloring Revisited: Complexity and Exact Algorithms
We take a new look at the Convex Path Recoloring (CPR),
Convex Tree Recoloring (CTR), and Convex Leaf
Recoloring (CLR) problems through the eyes of the
independent set problem. This connection allows us to give a complete
characterization of the complexity of all these problems in terms of
the number of occurrences of each color in the input instance, and
consequently, to present simpler NP-hardness proofs for them than
those given earlier. For example, we show that the CLR problem
on instances in which the number of leaves of each color is at most 3,
is solvable in polynomial time, by reducing it to the independent
set problem on chordal graphs, and becomes NP-complete on instances
in which the number of leaves of each color is at most 4.
This connection also allows us to develop improved exact algorithms
for the problems under consideration. For instance,
we show that the CPR problem on instances in which the number of
vertices of each color is at most 2, denoted 2-CPR, proved to be
NP-complete in the current paper, is solvable in time
$2^{n/4}n^{O(1)}$ ($n$ is the number of vertices on the path) by
reducing it after $2^{n/4}$ enumerations to the weighted independent
set problem on interval graphs, which is solvable in polynomial time.
Then, using an exponential-time reduction from CPR to
2-CPR, we show that CPR is solvable in time $2^{4n/9}n^{O(1)}$.
We also present exact algorithms for CTR and CLR running
in time $2^{0.454n}n^{O(1)}$ and $2^{n/3}n^{O(1)}$, respectively.
|
| 14:45 - 15:30 |
Ioan Todinca
Sur un algorithme exact pour le calcul d'un plus grand sous-graphe induit de largeur arborescente fixée
Je présenterai un résultat récent de Fomin et Villanger (Finding Induced Subgraphs via Minimal Triangulations, STACS 2010) qui résout le problème suivant : étant donné un graphe G et une constante t, quel est le plus grand sous-graphe induit F de G, de sorte que tw(F)<=t? Comme d'habitude tw(F) dénote la largeur arborescente du graphe F. La complexité de l'algorithme est O*(1.735^n), où la notation O* cache un polynôme en n --- en occurrence n^{t+3}. En particulier cet algorithme exact est le plus rapide connu pour le problème du coupe-cycle minimum (feedback vertex set), ce qui correspond au cas t=1.
L'approche est assez surprenante car elle consiste à faire une programmation dynamique simulant une prise en compte de toutes les décompositions arborescentes minimales (a.k.a. triangulations minimales) du graphe G. J'évoquerai quelques questions algorithmiques et combinatoires ouvertes (ou réactualisées) par ce travail.
|