New answers tagged graph-algorithms
5
Yes, this problem is FPT. We showed this in the paper "Parameterized Edge Hamiltonicity" (Lampis, Makino, Mitsou, and Uno, DAM 2018).
In particular, in this paper we state the result for Hamiltonian Path, but things doesn't change much if you want to consider Hamiltonian Cycle. In the conference version (and the slightly outdated version on the arxiv) we ...
2
distance-2 coloring is coloring in the square (d(x,y) <= 2 implies xy an edge in the square). If a graph has tw k, its square has bounded clique-width (see Gurski-Wanke and Suchan-Todinca). See Oum et al. for algorithms as in Proskurowski-Telle for graphs of bounded clique-width.
2
Yes. By Proposition 2.3 of [1], all elementary fractional extreme points of the LP correspond to subgraphs that contain odd cycles, and therefore if the graph contains no odd cycles, the LP has an optimal solution that takes on only integer values.
[1] G. L. Nemhauser and L. E. Trotter Jr. Properties of vertex packing and independence system polyhedra. ...
1
Starting with 5,7,$f$ and $g$ is correct. In order to complete the maximum independent you can proceed as follows. First, delete the vertices that are reachable from an unmatched vertex via an alternating path (in your example 5,6,7,$e$,$f$,$g$). This leaves a balanced bipartite graph (that is, it has the same number of vertices on each side), and you can ...
Top 50 recent answers are included
